Главное меню

Среди 49 школьников каждый знаком не менее, чем с 25 другими... Как решить?

Автор Ffas, Март 15, 2024, 09:39

« назад - далее »

Ffas

Как это решить Среди 49 школьников каждый знаком не менее, чем с 25 другими... Как решить?.

Udelar

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