Задача 109822
|
|
 |
Условие
За круглым столом сидят 100 представителей 25 стран, по 4 представителя от каждой. Докажите, что их можно разбить на 4 группы таким образом, что в каждой группе будет по одному представителю от каждой страны, и никакие двое из одной группы не сидят за столом рядом.Решение
Лемма. Пусть есть n непересекающихся пар знакомых – представителей n стран по двое от страны. Тогда можно разбить их на 2 группы, в каждой из которых по одному представителю от страны и нет знакомых.Выберем любого представителя страны 1, поместим его в первую группу, второго представителя этой же страны поместим во вторую группу, его знакомого (представителя, скажем, i -й страны) – снова в первую, второго представителя i -й страны – во вторую и т.д.
Этот процесс завершится, когда очередной знакомый уже распределен; это возможно только если этот знакомый – изначальный представитель первой страны, тогда он помещен в первую группу, что от него и требовалось.
Если еще остались нераспределенные люди, осталось повторить процесс, начиная с любого нераспределенного человека. Лемма доказана.
Теперь разобьем четырех представителей страны X на двух представителей страны X' и двух – страны X'' , и так поступим со всеми странами.
Разобьем всех сидящих на 50 пар сидящих рядом и объявим людей из одной пары знакомыми.
Тогда, в силу леммы, можно разбить этих людей на две группы по 50 человек, среди которых нет знакомых и есть по одному представителю новых стран (или по 2 представителя старых).
Но тогда в каждой группе вместе с любым человеком присутствует не более одного его соседа.
Тогда мы можем в каждой группе разбить людей на пары знакомых так, чтобы соседи оказались знакомыми, и снова применить лемму, разбив нашу группу на 2 подгруппы, без знакомых, т.е. без соседей.
