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