|
|
 |
Условие
На дне рождения у Васи было 10 ребят (включая Васю). Оказалось, что у каждых двух из этих ребят есть общий дедушка.
Докажите, что у семи из них есть общий дедушка.
Решение
Рассмотрим граф, где вершины соответствуют дедам, а рёбра – общим внукам. Если вершин не более двух, то у каждого деда десять внуков.
Предположим, что вершин ровно три. Они соединены 10 рёбрами. По принципу Дирихле какие-то две вершины соединены не более чем тремя рёбрами. Тогда из третьей вершины выходит не менее семи рёбер. Следовательно, у деда, соответствующего этой вершине, семь внуков.
Предположим, что на вершин более трёх. По условию из каждой вершины выходит хотя бы одно ребро и каждые два ребра имеют общую вершину. Рассмотрим вершину A, из которой выходит хотя бы два ребра AB и AC, и произвольную из оставшихся вершин D. Тогда каждое рёбро из D должно вести в A (иначе найдутся два ребра без общей вершины). Значит, рёбер, соединяющих B с C, нет, и все рёбра выходят из A.
Дед, соответствующий вершине A, будет общим для всех 10 ребят.
