2019-04-01
В Простоквашинской начальной школе учится 20 детей. У любых двух из них есть общий дед. Докажите, что у одного из дедов в этой школе учится не менее 14 внуков. (Замечание: любой ребёнок не может иметь более двух дедушек.)
Решение:
Рассмотрим граф, вершины которого обозначают дедов, чьи внуки учатся в этой школе, а рёбра — внуков (всего 20 рёбер). Пусть $A$ и $B$ — деды одного из внуков. Выделим также остальных внуков этих дедов (кратные рёбра, соединяющие вершины $A$ и $B$). По условию любые два ребра имеют общий конец, следовательно, каждое из остальных рёбер выходит либо из вершины $A$, либо из $B$. Если все они выходят из одной вершины, то утверждение задачи очевидно. Иначе же существует третья вершина $C$, где сходятся все эти рёбра. А это означает, что всего имеется ровно три деда! Ясно, что найдутся две вершины из этих трёх, соединеные ребром кратности не более шести (в противном случае граф должен иметь по крайней мере $3 \cdot 7 = 21$ ребро). Тогда у оставшегося деда по крайней мере $20 — 6 = 14$ внуков.