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