Графы и турниры → .09 Гуляем по графу

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

Ясно, что во время путешествий никакие два богатых туриста (или два бедных) не могли оказаться в одном городе. С другой стороны, условие задачи не запрещает находиться в одном городе одновременно бедному и богатому туристу, важно лишь, чтобы в начальный и в конечный момент в каждом городе было по одному туристу.

Допустим, что среди туристов имеется (или более) «богачей». Нарисуем граф: вершины — это города, из каждого города проведем самый дорогой выходящий путь. Тогда этот граф представляет собой лес, в каждом дереве которого все ребра направлены к корню, за исключением единственного ребра, выходящего из корня, — это ребро в дереве как бы двустороннее. Возьмем богача, который расположен ближе всего к корню своего дерева. Этот богач будет в течение ходов самым близким к корню. Значит, он проедет по городам, в которых еще не было других богачей. Это может быть только если граф — это путь из вершин, богачи занимают первые вершин этого пути (т. е. половину) и гуськом движутся по этому пути в сторону второй половины. Отсюда следует, что богачей не может быть больше а также что количество переездов тоже не превосходит

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

Обозначим города Допустим, что путь

составлен из самых дорогих авиалиний, для определенности пусть цена перелета равна рублей. А «бедный путь» пусть сначала проходит по городам с большими четными номерами, потом — по городам с большими нечетными, а далее — с малыми: сначала с четными, потом с нечетными:

Цены этих авиалинии пусть убывают от до рубля при движении вдоль этого пути. Цены остальных авиалиний назначим произвольно в диапазоне от до рублей.

Предположим так рассадить людей удалось. Занумеруем их по часовой стрелке и заметим, что если номера двух сидящих имеют одинаковую чётность, то между ними сидит нечётное число человек. Возьмём одного из сидящих — Через чётное число человек от сидит человек. Все они сидят на местах одной чётности, поэтому не могут иметь общих знакомых. Значит, имеется различных общих знакомых с этими людьми. У этих последних человек есть общий знакомый то есть все они имеют номера разной чётности. Но это невозможно.

У одноклассников Пети может быть друзей — всего вариантов. Но если кто-то дружит со всеми, то у всех не меньше одного друга. Поэтому либо кто-то дружит со всеми, либо кто-то не дружит ни с кем. В обоих случаях остается вариантов: или

Пусть у больше всего друзей, а у — меньше всего. В первом случае дружит со всеми, а — только с Во втором случае не дружит ни с кем, а — со всеми, кроме В каждом из случаев дружит с Петей, а — нет. Переведём и в другой класс. Как мы уже видели, дружит со всеми из оставшихся, а — ни с кем из оставшихся. Поэтому после перевода у каждого стало на одного друга меньше (среди одноклассников). Значит, у оставшихся Петиных одноклассников снова будет разное число друзей среди одноклассников.

Cнова переведём самого “дружелюбного” и самого “нелюдимого” в другой класс и т. д. Повторяя эти рассуждения раз, мы переведём в другой класс пар школьников, в каждой из которых ровно один Петин друг. Итак, друзей у Пети