В клубе собрались 20 человек, как всегда любые двое либо знакомы либо незнакомы. Докажите, что среди людей обязательно можно наити двоих, у которых количество знакомых.
Ответы
Пошаговое объяснение:
Допустим, что среди этих 20 человек нет людей с одинаковым количеством знакомств.
Отметим тот факт, что максимальное число знакомств среди этих 20ти равно 19 (ибо учитывать знакомство человека с самим собой в данном случае некорректно).
Минимальное же число знакомств равно 0 (если человек ни с кем не знаком, и его никто не знает)
Заметим что
различных чисел от 0 до 19 ровно 20,
как и людей в клубе.
Следовательно, среди этих 20 человек должно встречаться каждое число знакомств, по одному разу (20 чисел - 20 человек - каждому по числу; если какое-то число отсутствует, значит, другое число дублируется)
Т.е. среди собравшихся
- есть тот, у кого 0 знакомств
- и есть тот, у кого 19 знакомств.
А значит одновременно присутствует человек, которого никто не знает в зале - и человек который знает всех в зале.
Так как знакомство - это парный процесс
(ты знаком с челом <=> чел знаком с тобой)
то получается противоречие.
Следовательно, ситуация когда у всех в зале число знакомств различно, невозможна.
А значит, найдется такая пара людей, у которых число знакомств будет одинаково.