. В лесу 2019 сосен. На каждой сидит сова и смотрит на сову на ближайшей сосне. Докажите, что если попарные расстояния между соснами раз¬личны, то найдется сова, на которую никто не смотрит.
Ответы
Пусть в лесу существует сова, на которую смотрят хотя бы две другие. Тогда по принципу Дирихле найдётся сова, на которую никто не смотрит. Значит, на каждую сову смотрит ровно одна другая.
Воспользуемся методом спуска и докажем, что такая сова, на которую никто не смотрит, найдётся. Так как все попарные расстояния между соснами различны, среди этих расстояний найдётся лишь одно наименьшее. Рассмотрим две сосны, между которыми это расстояние взято. Так как это расстояние является наименьшим, совы с этих сосен будут смотреть друг на друга. Так как ни на одну сову не могут смотреть две или больше, на взятую пару сов не смотрит больше ни одна сова. Тогда забудем временно про взятые две сосны. Осталось 2017 сосен. Повторим выбор двух сосен с наименьшим расстоянием между ними ещё 1008 раз. В конце концов осталась одна сосна. Сова, сидящая там, сама на себя смотреть не может, следовательно, на неё никто не смотрит.