|
|
 |
Условие
Среди 49 школьников каждый знаком не менее чем с 25 другими.
Докажите, что можно их разбить на группы из двух или трёх человек так, чтобы каждый был знаком со всеми в своей группе.
Решение
Представим, что сначала все 49 школьников стоят в коридоре, и будем постепенно запускать их в класс. При этом будем делать это так, чтобы в классе в любой момент времени дети были разбиты на требуемые группы. Пусть в коридоре стоит школьник Фёдор. Если он знаком с каким-то другим школьником, стоящим в коридоре, то просто запустим их двоих в класс. Иначе все знакомые Фёдора уже в классе. Так как в классе менее 50 школьников, они разбиты менее чем на 25 групп. Значит, среди знакомых Фёдора какие-то двое находятся в одной группе. Если это группа из двух школьников, то впустим Фёдора в класс, добавив его к этой группе. Если же это группа из трёх школьников, то попросим одного из знакомых Фёдора образовать с ним группу, а оставшихся школьников оставим вдвоём.
Так, постепенно впуская школьников в класс, мы добьёмся того, что все школьники будут разделены на требуемые группы.Замечания
8 баллов
