Question

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

Answer 1

Ответ:

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

Рассмотрим граф, вершины которого обозначают дедов, чьи внуки учатся в этой школе, а рёбра — внуков (всего 20 рёбер). Пусть AA и BB — деды одного из внуков. Выделим также остальных внуков этих дедов (кратные рёбра, соединяющие вершины AA и BB). По условию любые два ребра имеют общий конец, следовательно, каждое из остальных рёбер выходит либо из вершины AA, либо из BB. Если все они выходят из одной вершины, то утверждение задачи очевидно. Иначе же существует третья вершина CC, где сходятся все эти рёбра. А это означает, что всего имеется ровно три деда! Ясно, что найдутся две вершины из этих трёх, соединеные ребром кратности не более шести (в противном случае граф должен иметь по крайней мере 3⋅7=213⋅7=21 ребро). Тогда у оставшегося деда по крайней мере 20—6=1420—6=14 внуков.

Answer 2

Давайте докажем это утверждение методом от противного.

Предположим, что ни один из дедов в классе не имеет не менее 14 внуков и внучек. То есть каждый дед имеет менее 14 внуков и внучек. Поскольку у каждого ребенка два деда (от отца и от матери), это означает, что каждый из 20 детей имеет двух дедов, у каждого из которых менее 14 внуков и внучек.

Теперь рассмотрим пару дедов: одного от отца (пусть будет Дед-А) и другого от матери (пусть будет Дед-Б). У каждого из них менее 14 внуков и внучек. Это означает, что в классе есть не менее 7 пар дедов (Дед-А и Дед-Б), у каждой из которых менее 14 внуков и внучек.

Но если мы выберем двух разных дедов из этих пар, то они обязательно будут иметь общего ребенка (одного из 20 детей в классе), так как каждый дед обязательно является дедом хотя бы одного из детей в классе. Это противоречит условию задачи, которое гласит, что у любых двух из 20 детей в классе есть общий дед.

Таким образом, наше предположение о том, что ни один из дедов не имеет не менее 14 внуков и внучек, является ложным. Следовательно, у одного из дедов в классе действительно учится не менее 14 внуков и внучек.