В М6 приехали 54 ребёнка. Среди любых трёх какие-то двое знают друг друга. Докажите, что кто-то знает хотя бы 26 других. В М6 приехали 54 ребёнка. Среди любых трёх какие-то двое знают друг друга. Докажите, что кто-то знает хотя бы 26 других.

Предыдущий
вопрос Следующий
вопрос

Допустим противное – никто из этих 54 детей не знает 26 других. Тогда каждый ребенок знает не более 25 других детей. Таким образом, если мы взять любого ребенка, он не знает 29 детей (54 - 25 = 29).

Но у нас есть 54 детей, каждый из которых знает хотя бы 2 других детей (так как среди любых трех какие-то двое знают друг друга). Значит, суммарно будет знакомых детей более, чем 54*2 = 108. Противоречие.

Следовательно, как минимум один ребенок должен знать более чем 25 других детей.