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