Олимпиадная задача о разбиении представителей стран за круглым столом — индукция, алгебра, 8–11 классы

Лемма.Пусть есть n непересекающихся пар знакомых – представителей n стран по двое от страны. Тогда можно разбить их на 2 группы, в каждой из которых по одному представителю от страны и нет знакомых.

Выберем любого представителя страны 1, поместим его в первую группу, второго представителя этой же страны поместим во вторую группу, его знакомого (представителя, скажем, i -й страны) – снова в первую, второго представителя i -й страны – во вторую и т.д. Этот процесс завершится, когда очередной знакомый уже распределен; это возможно только если этот знакомый – изначальный представитель первой страны, тогда он помещен в первую группу, что от него и требовалось. Если еще остались нераспределенные люди, осталось повторить процесс, начиная с любого нераспределенного человека. Лемма доказана.

Теперь разобьем четырех представителей страны X на двух представителей страны X' и двух – страны X'' , и так поступим со всеми странами.

Разобьем всех сидящих на 50 пар сидящих рядом и объявим людей из одной пары знакомыми. Тогда, в силулеммы, можно разбить этих людей на две группы по 50 человек, среди которых нет знакомых и есть по одному представителю новых стран (или по 2 представителя старых).

Но тогда в каждой группе вместе с любым человеком присутствует не более одного его соседа. Тогда мы можем в каждой группе разбить людей на пары знакомых так, чтобы соседи оказались знакомыми, и снова применить лемму, разбив нашу группу на 2 подгруппы, без знакомых, т.е. без соседей.

Ответ задачи отсутствует