Теория графов и комбинаторика

По первой задаче:

Удалим одного ученика. В оставшемся графе степень каждой вершины как минимум 24. Для этого графа воспользуемся теоремой Оре:

Теорема Оре.
Пусть G — (конечный и простой) граф с n \geq 3 вершинами. Обозначим через \deg v степень вершины v в G. Теорема Оре утверждает, что если \deg v + \deg w \geq n для любой пары несмежных вершин v и w графа G, то G является гамильтоновым.

По этой теореме, данный граф гамильтонов, так как сумма степеней любых двух несмежных вершин хотя бы количество вершин (24+24=48\geq 48). Тогда в этом графе есть гамильтонов цикл. Рассмотрим его. В нем 48 вершин. Разобьём их на 24 пары.

Теперь вернём удалённую вершину. У нее была степень хотя бы 25. По принципу Дирихле, в какой из этих 24 пар удаленный ученик знает обоих. Значит это тройка учеников знает друг друга. Остальные ученики разбиты по парам. Значит мы добились того чего хотели.

6 симпатий

По задаче 7:

Заметим, что если у человека есть знакомые, сидящие рядом друг с другом (в частности, если он знаком со своим соседом), то этот человек знаком со всеми. Докажем, что такой гость найдётся.

Пусть A и B – двое соседей. Если они не знакомы между собой, то их общий знакомый C знаком со всеми, так как его знакомые сидят без промежутков. В противном случае со всеми знаком человек A (по той же причине).

Итак, пусть X – гость, знакомый со всеми. Тогда его соседи тоже знакомы со всеми, так как они знакомы с X (являющимся для них соседом). Соседи этих соседей также знакомы со всеми, и так далее по кругу.

1 симпатия

Оригинальное решение задачи 6:

Представим, что сначала все 49 школьников стоят в коридоре, и будем постепенно запускать их в класс. При этом будем делать это так, чтобы в классе в любой момент времени дети были разбиты на требуемые группы.

Пусть в коридоре стоит школьник Фёдор. Если он знаком с каким-то другим школьником, стоящим в коридоре, то просто запустим их двоих в класс. Иначе все знакомые Фёдора уже в классе.

Так как в классе менее 50 школьников, они разбиты менее чем на 25 групп. Значит, среди знакомых Фёдора какие-то двое находятся в одной группе.

Если это группа из двух школьников, то впустим Фёдора в класс, добавив его к этой группе. Если же это группа из трёх школьников, то попросим одного из знакомых Фёдора образовать с ним группу, а оставшихся школьников оставим вдвоём. Так, постепенно впуская школьников в класс, мы добьёмся того, что все школьники будут разделены на требуемые группы.

1 симпатия
© 2021 Общественный Фонд «Beyond Curriculum» (CC BY-NC-SA 4.0 International)