Коты и кошки на выставке — олимпиадная задача по теории графов, 6–8 кл
На кошачьей выставке в ряд сидят 10 котов и 19 кошек, причём рядом с каждой кошкой сидит более толстый кот.
Докажите, что рядом с каждым котом сидит кошка, которая тоньше него.
Разобрать решение
Проведём к каждой кошке стрелочку от сидящего рядом с ней более толстого, чем она, кота. Число стрелочек – 19: столько, сколько кошек. Но, с другой стороны, от каждого кота не может идти больше двух стрелок, так как стрелки направлены на соседних кошек, да ещё не на всех, а только на более худых. Следовательно, стрелки ведут от всех котов, что и требовалось.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.