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