Задача 4. Столбы на кольцевом шоссе

Сколько путей и какой из них самый длинный

Каждый из $15$ столбов соединён кратчайшим путём с $14$ другими. Произведение $15\cdot 14$ считает каждую пару дважды (путь от $A$ до $B$ и путь от $B$ до $A$ — один и тот же), поэтому путей

Все столбы стоят в разных местах: если бы два столба совпали, их расстояния до третьего были бы одинаковыми. Значит, все $105$ расстояний — разные целые числа, и каждое не меньше $1$.

Пусть длина шоссе $L$ км. Между двумя столбами по шоссе две дороги — по часовой стрелке и против, вместе они составляют всё шоссе. Кратчайший путь — меньшая из двух дорог, а меньшее из двух чисел с суммой $L$ не больше половины $L$. Поэтому каждый кратчайший путь не длиннее $\frac{L}{2}$ км.

Пункт а): не меньше 210 км

Выпишем $105$ разных целых расстояний по возрастанию. Первое не меньше $1$; второе больше первого, значит, не меньше $2$; третье не меньше $3$, и так далее. Поэтому самое длинное, $105$-е, не меньше $105$ км. Но оно не длиннее половины шоссе:

Это верно для любой длины шоссе, даже дробной. Пункт а) доказан.

Если бы шоссе было ровно 210 км

Для пункта б) осталось показать, что ровно $210$ км не бывает. Пусть $L = 210$. Тогда каждое расстояние не больше $105$, а разных расстояний $105$. Разных целых чисел от $1$ до $105$ как раз $105$ — значит, расстояния — это в точности $1, 2, 3, \ldots, 105$, каждое по одному разу. Нечётных среди них

Итак, при $L = 210$ ровно у $53$ пар столбов кратчайший путь — нечётное число километров. Проверим, может ли так быть.

Раскрасим столбы по чётности

Выберем столб $A$ и отметим километры от него по часовой стрелке: $0, 1, 2, \ldots, 209$. Каждый столб стоит на целой отметке: если кратчайший путь от $A$ до столба $P$ равен $d$ км, то $P$ стоит на отметке $d$ или $210 - d$. Покрасим столб в белый цвет, если его отметка чётная (сам $A$ — белый, его отметка $0$), и в чёрный — если нечётная.

Возьмём два столба с отметками $p < q$. Одна дорога между ними — $q - p$ км, другая — $210 - (q - p)$ км. Их сумма $210$ чётна, значит, обе дороги одной чётности, и кратчайший путь имеет ту же чётность, что $q - p$. А разность двух чисел одной чётности чётна, разной — нечётна. Итак:

• между столбами одного цвета кратчайший путь чётный;
• между белым и чёрным столбом — нечётный.

Зачем красить: так мы считаем нечётные пути, не зная, где именно стоят столбы.

Пункт б): противоречие

Пусть белых столбов $w$, чёрных $b$, и $w + b = 15$. Пар «белый — чёрный» ровно $w\cdot b$: каждый из $w$ белых в паре с каждым из $b$ чёрных. По шагу 4 нечётных кратчайших путей ровно $w\cdot b$, а по шагу 3 их $53$:

Но $w + b = 15$ — нечётное число, поэтому одно из чисел $w$, $b$ чётное: если бы оба были нечётными, сумма была бы чётной. Тогда и произведение $w\cdot b$ чётное — оно не может равняться нечётному $53$. Противоречие: шоссе не может быть ровно $210$ км. Вместе с пунктом а) получаем, что длина шоссе больше $210$ км.

Второй вариант

Рассуждение то же, меняются только числа. Пар столбов

все $78$ кратчайших путей — разные целые числа не меньше $1$, поэтому самый длинный не меньше $78$ км. Кратчайший путь не длиннее половины шоссе, значит, $78 \le \frac L2$ и $L \ge 156$ — это пункт а).

Если $L = 156$, то каждое расстояние не больше $78$, и $78$ разных расстояний — это в точности $1, 2, \ldots, 78$. Нечётных среди них $39$. Отметим километры от столба $A$ по часовой стрелке. Каждый столб стоит на целой отметке: если кратчайший путь от $A$ до него равен $d$ км, то его отметка $d$ или $156 - d$. Покрасим столбы по чётности отметок; $156$ чётно, поэтому, как в шаге 4, кратчайший путь нечётен ровно между белым и чёрным столбом, и нечётных путей $w\cdot b$. Но $w + b = 13$ нечётно, одно из чисел $w$, $b$ чётное, и $w\cdot b$ чётно — не равно $39$. Противоречие, значит, $L > 156$.

Отличие от первого варианта: $13$ столбов вместо $15$, граница $156 = 2\cdot 78$ вместо $210 = 2\cdot 105$, нечётных расстояний $39$ вместо $53$. Такие шоссе бывают: например, $13$ столбов встают без повторов на шоссе длиной $168$ км (проверено программой).