Докажите, что среди любого количество людей в некотором зале хотя бы двое имеют одинаковое число знакомых среди присутствующих.
Ответы
Проще всего по индукции. Случай 1-го человека исключаем как вырожденный, а для двух он уже верен.
Пусть утверждение верно для Н и пришел еще один человек.
В зале до этого было 2 человека А и В , знакомые с одинаковым числом людей. Пусть вновь пришедший С не знаком с А и В. Тогда условие выполнено.Все те же А и В знакомы с одинаковым чилом людей. Пусть он знаком с А и В. Тогда условие тоже выполнено. А и В по прежнему удовлетворяют теореме. Пусть С знаком с А и не знаком с В. Тогда выгоним А или В из зала и сведем случай снова к Н.
Чтобы было понятнее покажем переход от Н=2 к Н=3.
Пусть в зале было двое незнакомых А иВ. Пришел 3-й.
Если он знаком с А и В, то они по-прежнму оказываютсяя знакомыми с одинаковым числом людей. Пусть он знаком с А, но не знаком с В. Выгоним одного А или В.
Остались двое одинаково знакомых или незнакомых.
Та же ситуация , если А и В были знакомы.
ну для Н=2 это да, так как они друг на друге замкнуты
Но для других значений это совсем не очевидно
Это может быть, но с оговоркой, что знакомство взаимно. То есть если человек знает кого-то, его тоже знают. Иначе, уже для n=2 очевидно, что один знает другого, а другой нет...
Д-во от противного:
Пусть у всех разное количество знакомых.
Пронумеруем человеков: 1, 2, 3, 4...n
Пусть у первого человека есть k1 знакомых, остается (n-1) возможное количество различных знакомых
тогда у второго должно быть отличное от k1 количество знакомых - k2, остается (n-2) возможных знакомых
у n-ого человека будет (n-n) знакомых, то есть "0". То есть он не знает никого. А раз он не знает никого, его тоже никто не знает - выгоняем его за дверь, тк он не влияет на подсчет.
Пересчитываем знакомых уже (n-1) гостя и получаем, что еще один человек никого не знает. Значит у нас было уже два человека которые никого не знают, то есть имеют одинаковое количество знакомых.