Леонард Эйлер атындағы олимпиада,2010-2011 оқу жылы, қорытынды кезеңнің 1-ші туры

Дөңгелек үстелдің бойында 40 адам отыр. Кез келген арасында жұп сан адам отыратын екі адамның ортақ танысы болатындай, ал кез келген арасында тақ сан адам отыратын екі адамның ортақ танысы болмайтындай бола алады ма? ( А. Шаповалов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. Не может.
Решение 1. Заметим, что если между А и В сидят $a$ человек, а между В и Б сидят $b$ человек, то между А и Б сидит $a+b+1$ или $|a - b| -1$ человек. Поэтому если числа $a$ и $b$ имеют одинаковую чётность, то между А и Б сидит нечётное число человек. Допустим, есть человек В, имеющий хотя бы троих знакомых. Тогда среди них найдутся такие знакомые А и Б, что числа $a$ и $b$ имеют одинаковую чётность, и у них будет общий знакомый В, хотя между ними сидит нечётное число человек. Если же у каждого сидящего не более двух знакомых, то для каждого найдутся максимум двое, с которыми у него есть общие знакомые, а по условию таких должно быть 20 человек.

Комментарии от администратора Комментарии от администратора №2.     Решение 2. Предположим противное. Возьмём любого из сидящих. Через четное число человек от него сидит 20 человек. Как было показано в первом решении, между собой эти люди сидят через нечетное число человек, поэтому не могут иметь общих знакомых. Значит, потребуется 20 различных общих знакомых взятого нами человека с этими людьми, то есть у каждого из сидящих есть среди них не меньше 20 знакомых. Но тогда, как легко видеть, у любых двух из сидящих есть общий знакомый — противоречие.