Question

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

Answer 1

Ответ:

это не сложно, принцип дирихле

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

допустим это не так, тогда у первого - 0 знакомых, у второго - 1, у третьего - 2 и тд...

тогда у первого будет 0 знакомых, а у последнего - 19 (все)

но если последний знаком со всеми то он должен быть знаком и с первым, а это невозможно так как первый не знаком ни с кем

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

тогда у последнего будет 20 знакомых, при том что максимум - 19 (ты не можешь быть знаком сам с собой, это так не работает)

значит что всегда будет 2 человека у которых одинаковое количество знакомых

Answer 2

Для доказательства этого утверждения можно воспользоваться принципом Дирихле, также известным как принцип ящика и шаров. Этот принцип помогает доказать существование двух человек с одинаковым количеством знакомых.

В данной задаче мы можем рассматривать знакомства между людьми как отношение, которое может быть либо "знаком" (1) либо "незнаком" (0). У нас есть 20 человек, и каждый человек может быть знаком или незнаком с остальными 19 человеками.

Давайте предположим, что ни одна пара людей не имеет одинаковое количество знакомых. Это значит, что каждый человек имеет разное количество знакомых. Однако у каждого человека может быть от 0 до 19 знакомых (20 возможных вариантов), и, таким образом, нам нужно разделить 20 человек на 20 разных вариантов количества знакомых.

Это означает, что первый человек знаком с 19 другими (20 минус он сам), второй человек знаком с 18 другими (20 минус он сам и первый человек), третий человек знаком с 17 другими, и так далее.

Однако если мы сложим количество знакомых у всех 20 человек, мы получим:

19 + 18 + 17 + ... + 3 + 2 + 1

Это сумма арифметической прогрессии, которая равна (20 * 19) / 2 = 190.

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

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