Задача 98230

Темы:    [ Принцип Дирихле (прочее) ] [ Теория графов (прочее) ]

Сложность: 4- Классы: 7,8,9

Условие

Автор: Шаповалов А.В.

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

Решение

  Рассмотрим любого школьника A и двух его дедов X, Y. Если не все школьники – внуки одного из них (в этом случае доказывать нечего), то существует школьник B, который не приходится внуком X (тогда он непременно внук Y), и школьник C, который не внук Y (следовательно, внук X). У школьников B и C есть общий дед Z.
  Никаких других дедов, кроме X, Y и Z у школьников нет: внук такого деда не имел бы общего деда с одним из трёх школьников A, B, C. На трёх дедов приходится 20 внуков, поэтому (считая по два деда на внука) хотя бы у одного было не менее  ⅔·20,  то есть не менее 14 внуков.

Замечания

5 баллов

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

олимпиада
Название	Турнир им.Ломоносова
год/номер
Номер	17
Дата	1994
задача
Номер	03
Кружок
Название	ВМШ 57 школы
класс
Класс	7
год
Место проведения	57 школа
Год	2005/06
занятие
Номер	3
Название	Принцип Дирихле
Тема	Принцип Дирихле
задача
Номер	6
олимпиада
Название	Турнир городов
Турнир
Номер	16
Дата	1994/1995
вариант
Вариант	осенний тур, тренировочный вариант, 8-9 класс
Задача
Номер	4