Разделы 
Дополнительно
Задача по математике - 2050
2019-01-23 
За круглым столом сидят 100 представителей 25 стран, по 4 представителя от каждой. Докажите, что их можно разбить на 4 группы таким образом, что в каждой группе будет по одному представителю от каждой страны, и никакие двое из одной группы не сидят за столом рядом.
Решение:
Лемма. Пусть есть $n$ непересекающихся пар знакомых - представителей $n$ стран по двое от страны. Тогда можно разбить их на 2 группы, в каждой из которых по одному представителю от страны и нет знакомых.
Доказательство. Выберем любого представителя страны $1$, поместим его в первую группу, второго представителя этой же страны поместим во вторую группу, его знакомого (представителя, скажем, $i$-й страны) - снова в первую, второго представителя $i$-й страны - во вторую и т. д. Этот процесс завершится, когда очередной знакомый уже распределен; это возможно только если этот знакомый - изначальный представитель первой страны, тогда он помещен в первую группу, что от него и требовалось.
Если еще остались нераспределенные люди, осталось повторить процесс, начиная с любого нераспределенного человека. Лемма доказана.
Теперь разобьем четырех представителей страны $X$ на двух представителей страны $X^{\prime}$ и двух - страны $X^{\prime \prime}$, и так поступим со всеми странами. Разобьем всех сидящих на 50 пар сидящих рядом и объявим людей из одной пары знакомыми. Тогда, в силу леммы, можно разбить этих людей на две группы по 50 человек, среди которых нет знакомых и есть по одному представителю «новых» стран (или по 2 представителя «старых»). Но тогда в каждой группе вместе с любым человеком присутствует не более одного его соседа. Тогда мы можем в каждой группе разбить людей на пары знакомых так, чтобы соседи оказались знакомыми, и снова применить лемму, разбив нашу группу на 2 подгруппы, без знакомых, т. е. без соседей.
За круглым столом сидят 100 представителей 25 стран, по 4 представителя от каждой. Докажите, что их можно разбить на 4 группы таким образом, что в каждой группе будет по одному представителю от каждой страны, и никакие двое из одной группы не сидят за столом рядом.
Решение:
Лемма. Пусть есть $n$ непересекающихся пар знакомых - представителей $n$ стран по двое от страны. Тогда можно разбить их на 2 группы, в каждой из которых по одному представителю от страны и нет знакомых.
Доказательство. Выберем любого представителя страны $1$, поместим его в первую группу, второго представителя этой же страны поместим во вторую группу, его знакомого (представителя, скажем, $i$-й страны) - снова в первую, второго представителя $i$-й страны - во вторую и т. д. Этот процесс завершится, когда очередной знакомый уже распределен; это возможно только если этот знакомый - изначальный представитель первой страны, тогда он помещен в первую группу, что от него и требовалось.
Если еще остались нераспределенные люди, осталось повторить процесс, начиная с любого нераспределенного человека. Лемма доказана.
Теперь разобьем четырех представителей страны $X$ на двух представителей страны $X^{\prime}$ и двух - страны $X^{\prime \prime}$, и так поступим со всеми странами. Разобьем всех сидящих на 50 пар сидящих рядом и объявим людей из одной пары знакомыми. Тогда, в силу леммы, можно разбить этих людей на две группы по 50 человек, среди которых нет знакомых и есть по одному представителю «новых» стран (или по 2 представителя «старых»). Но тогда в каждой группе вместе с любым человеком присутствует не более одного его соседа. Тогда мы можем в каждой группе разбить людей на пары знакомых так, чтобы соседи оказались знакомыми, и снова применить лемму, разбив нашу группу на 2 подгруппы, без знакомых, т. е. без соседей.
