На слет приехало 66 человек. Известно, что среди любых четверых человек найдутся трое попарно знакомых. Доказать, что можно составить 2018 различных пар знакомых друг с другом людей.

Предыдущий
вопрос Следующий
вопрос

Предположим, что в группе из 66 человек есть хотя бы один человек, который не знаком ни с кем. Тогда число знакомых пар будет не больше, чем число сочетаний из 65 по 2, то есть 65*64/2 = 2080.

Теперь докажем, что в группе из 66 человек обязательно найдется хотя бы одна пара знакомых. Рассмотрим произвольного человека. Он либо знаком со всеми остальными (тогда мы нашли пару знакомых), либо он знаком не со всеми. Во втором случае у него есть хотя бы один знакомый человек (иначе он не знаком ни с кем), скажем, это человек А. Теперь рассмотрим человека А. Если он знаком со всеми остальными, то снова нашли пару знакомых. Иначе у него есть хотя бы один не знакомый человек, скажем, это человек Б. Теперь рассмотрим человека Б и так далее. В итоге мы либо обязательно найдем пару знакомых, либо придем к противоречию, что у нас в группе есть человек, который не знаком ни с кем.

Таким образом, общее число знакомых пар в группе из 66 человек не меньше, чем 2018 (так как число знакомых пар не превышает 2080, а найдется хотя бы одна пара знакомых). А значит, можно составить 2018 различных пар знакомых друг с другом людей.