Задача 88269

Темы:    [ Подсчет двумя способами ] [ Степень вершины ] [ Принцип Дирихле (прочее) ]

Сложность: 3+ Классы: 6,7,8

Условие

На кошачьей выставке в ряд сидят 10 котов и 19 кошек, причём рядом с каждой кошкой сидит более толстый кот.
Докажите, что рядом с каждым котом сидит кошка, которая тоньше него.

Решение

Проведём к каждой кошке стрелочку от сидящего рядом с ней более толстого, чем она, кота. Число стрелочек – 19: столько, сколько кошек. Но, с другой стороны, от каждого кота не может идти больше двух стрелок, так как стрелки направлены на соседних кошек, да ещё не на всех, а только на более худых. Следовательно, стрелки ведут от всех котов, что и требовалось.

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

книга
Автор	Козлова Е.Г.
Название	Сказки и подсказки
задача
Номер	337