Выберите подход, который необходимо применить к поиску решения следующей задачи. Задача. На каждой из 15 планет, расстояния между которыми попарно различны, находится по астроному, каждый из которых наблюдает за ближайшей к нему планетой. Докажите, что некоторую планету никто не наблюдает. Варианты: разбор маленьких случаев; принцип крайнего; построение примера; поиск инварианта; принцип Дирихле.

Выберем планету, у которой расстояние до своего астронома максимально среди всех пар «планета — находящийся на ней астроном». Пусть этот астроном наблюдает планету, ближайшую к нему.

Предположим, что выбранную планету кто-то наблюдает. Тогда на ней находится астроном, который наблюдает ближайшую к нему планету. Из-за попарно различных расстояний эта ближайшая планета не может быть той же самой планетой, где находится астроном: иначе наблюдаемая пара имела бы расстояние 0, тогда как выбранная пара имеет положительное расстояние. Значит, астроном на выбранной планете наблюдает другую планету на меньшем расстоянии, чем максимальное.

Но расстояние от этого астронома до наблюдаемой им планеты — это расстояние между двумя планетами. На одной из них находится этот астроном, поэтому оно не обязано сравниваться напрямую с расстоянием от астронома на выбранной планете; однако, поскольку каждый астроном наблюдает ближайшую планету, стандартный аргумент строится через ориентированные рёбра: если планета наблюдается, у неё есть входящее ребро, а у каждой вершины ровно одно исходящее. В конечном ориентированном графе такой структуры существует цикл. Цикл длины 2 невозможен: если A наблюдает B и B наблюдает A, то расстояния от астрономов до этих планет совпадают, что противоречит попарной различности расстояний между планетами. Цикл длины больше 2 также невозможен: в цикле каждое следующее расстояние строго меньше предыдущего, поскольку астроном на очередной планете выбрал ближайшую, а не предыдущую планету цикла; это дало бы строгое убывание по замкнутому циклу.

Следовательно, граф не может содержать цикл, а значит, при конечном числе планет у него есть вершина без входящих рёбер: некоторую планету никто не наблюдает.

Ответ: принцип крайнего.