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