Question

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

Answer 1

Ответ:

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

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

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

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

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

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

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

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