Question

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

Answer 1

Пошаговое объяснение:

Допустим, что среди этих 20 человек нет людей с одинаковым количеством знакомств.

Отметим тот факт, что максимальное число знакомств среди этих 20ти равно 19 (ибо учитывать знакомство человека с самим собой в данном случае некорректно).

Минимальное же число знакомств равно 0 (если человек ни с кем не знаком, и его никто не знает)

Заметим что

различных чисел от 0 до 19 ровно 20,

как и людей в клубе.

Следовательно, среди этих 20 человек должно встречаться каждое число знакомств, по одному разу (20 чисел - 20 человек - каждому по числу; если какое-то число отсутствует, значит, другое число дублируется)

Т.е. среди собравшихся

- есть тот, у кого 0 знакомств

- и есть тот, у кого 19 знакомств.

А значит одновременно присутствует человек, которого никто не знает в зале - и человек который знает всех в зале.

Так как знакомство - это парный процесс

(ты знаком с челом <=> чел знаком с тобой)

то получается противоречие.

Следовательно, ситуация когда у всех в зале число знакомств различно, невозможна.

А значит, найдется такая пара людей, у которых число знакомств будет одинаково.

Answer 2

Давайте докажем это утверждение методом от противного.

Предположим, что среди 20 человек нет двоих, у которых количество знакомых разное. Это означает, что у каждой пары людей либо одинаковое количество знакомых, либо ни один из них не знаком с другими.

Посмотрим на первую ситуацию: у каждой пары людей одинаковое количество знакомых. Поскольку любое количество знакомых может быть только целым числом, и у каждой пары оно одинаково, то это означает, что у всех людей в клубе одинаковое количество знакомых. Но это противоречит условию задачи, потому что, по условию, "любые двое либо знакомы либо незнакомы", что означает, что у разных пар должны быть разные количество знакомых. Таким образом, эта ситуация невозможна.

Теперь рассмотрим вторую ситуацию: ни один из членов пары не знаком с другими. Это также невозможно, потому что, если каждый человек не знаком ни с кем, то они все являются незнакомыми друг с другом, что противоречит условию задачи, что в клубе собрались 20 человек, и "любые двое либо знакомы либо незнакомы".

Из обоих ситуаций видно, что невозможно, чтобы у каждой пары в клубе было одинаковое количество знакомых, и невозможно, чтобы ни один из них не был знаком с другими. Таким образом, наша исходная гипотеза оказывается ложной.

Следовательно, среди 20 человек обязательно можно найти двоих, у которых количество знакомых разное.