В М6 приехали 54 ребёнка. Среди любых трёх какие-то двое знают друг друга. Докажите, что кто-то знает хотя бы 26 других. В М6 приехали 54 ребёнка. Среди любых трёх какие-то двое знают друг друга. Докажите, что кто-то знает хотя бы 26 других.
В М6 приехали 54 ребёнка. Среди любых трёх какие-то двое знают друг друга. Докажите, что кто-то знает хотя бы 26 других. В М6 приехали 54 ребёнка. Среди любых трёх какие-то двое знают друг друга. Докажите, что кто-то знает хотя бы 26 других.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Допустим противное – никто из этих 54 детей не знает 26 других. Тогда каждый ребенок знает не более 25 других детей. Таким образом, если мы взять любого ребенка, он не знает 29 детей (54 - 25 = 29).
Но у нас есть 54 детей, каждый из которых знает хотя бы 2 других детей (так как среди любых трех какие-то двое знают друг друга). Значит, суммарно будет знакомых детей более, чем 54*2 = 108. Противоречие.
Следовательно, как минимум один ребенок должен знать более чем 25 других детей.