Question

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

Answer 1

Пронумеруем людей от 1 до 64. Возьмём первого человека, он знаком не более, чем с 8 другими, следовательно, остаётся не менее 64 − 8 − 1 = 55 людей, с которыми он не знаком. Возьмем второго человека из этих 55, он знаком не более, чем с 8 другими, следовательно, остаётся не менее 55 − 8 − 1 = 46 людей, с которыми он не знаком (среди них есть и первый). Будем повторять тот же процесс с оставшимися на предыдущем шаге людьми. На каждом шаге выбирается один человек, который не знаком ни с одним из предыдущих по построению. На третьем шаге людей, не знакомых с выбранными, останется 37, на четвёртом 28, на пятом 19, на шестом 10, на седьмом 1. Таким образом, после 7-го шага останется один человек, не знакомый ни с одним из 7 выбранных. Мы получили 8 попарно незнакомых людей