Олимпиада имени Леонарда Эйлера2010-2011 учебный год, I тур заключительного этапа

За круглым столом сидят 40 человек. Может ли случиться, что у любых двух из них, между которыми сидит четное число человек, есть за столом общий знакомый, а у любых двух, между которыми сидит нечетное число человек, общего знакомого нет? ( А. Шаповалов )

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

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

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