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