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