ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 115467
Темы:    [ Принцип Дирихле (конечное число точек, прямых и т. д.) ]
[ Теория графов (прочее) ]
Сложность: 4-
Классы: 7,8,9,10
В корзину
Прислать комментарий

Условие

На дне рождения у Васи было 10 ребят (включая Васю). Оказалось, что у каждых двух из этих ребят есть общий дедушка.
Докажите, что у семи из них есть общий дедушка.


Решение

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

Источники и прецеденты использования

олимпиада
Название Окружная олимпиада (Москва)
год
Год 2009
Класс
Класс 8
задача
Номер 06.4.8.6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .