город Угрюмов

[karzhas]

В городе Угрюмове 2 000 000 жителей, которые мало общаются друг с другом. Тем не менее, среди любых 2 000 жителей найдутся трое попарно знакомых. Докажите, что в городе есть четверо попарно знакомых.

[Shadow]

Разделим жителей на 1000 группы по 2000 человек. В каждох группе будут 3 знакомых. Рассмотрим только их. Берем по 2 человека из каждой группе - получается группа из 2000 чел. Должно быть 3 знакомых.

-- 20.12.2011, 15:44 --

Поспешил кажется

[Dave]

Допустим противное - четырёх попарно знакомых нет. Тогда справедливы следующие утверждения.

Лемма 1. У каждого жителя не более $1999$ знакомых с ним жителей.
Доказательство. Если бы это было не так и у какого-то жителя нашлось бы $2000$ знакомых, то, т.к. среди них есть тройка попарно знакомых, то эта тройка вместе с исходным жителем образовала бы четвёрку попарно знакомых.

Лемма 1. Если $b \geqslant 2000(a-2)+4$, где $a \geqslant 2, b \leqslant 2000000$, то в любой группе из $b$ жителей города найдётся группа из $a$ попарно незнакомых между собой жителей.
Доказательство. Допустим, что это не так и $B$ - некоторая группа из $b$ человек, а $C$ - максимальная подгруппа из попарно незнакомых между собой жителей в ней, состоящая из $c$ человек, где $1 \leqslant c \leqslant a-1$. Условно выбросим из $C$ любого жителя и получим некоторую группу $D$ из $d=c-1$, где $0 \leqslant d \leqslant a-2$, попарно незнакомых между собой человек. Если мы отбросим из $B$ каждого человека из $D$ вместе со всеми его знакомыми (которых по лемме 1 не больше $1999$), то в результате останется не менее $b-2000d \geqslant 2000(a-2)+4-2000d \geqslant 4$ человек, из которых, в силу исходного предположения, всегда можно выбрать двух незнакомых между собой жителей. Дополнив ими группу $D$, получим $d+2=c+1$ попарно незнакомых жителей - противоречие с максимальностью группы $C$.

Теперь, применив лемму 2 c $b=2000000$ и $a=1000$, ко всему городу, получим некоторую группу $T_1$ из $1000$ попарно незнакомых между собой жителей. Применив её ещё раз к оставшимся жителям, $b=1999000$ и $a=1000$, получим другую группу $T_2$ из $1000$ попарно незнакомых между собой жителей. В группе, полученной объединением $T_1$ и $T_2$, по условию найдётся тройка попарно знакомых жителей, из которых минимум двое будут из одной из групп $T_1$ и $T_2$, что противоречит построению этих групп. $\blacksquare$