ВсОШ 2023, региональный этап, 10 класс, задача 9
( баллов) Дано натуральное число . Вдоль дороги стоят столбов через равные промежутки. Миша покрасил их в цветов и для каждой пары одноцветных столбов, между которыми нет других столбов того же цвета, вычислил расстояние между ними. Все эти расстояния оказались различны. При каком наибольшем так могло оказаться?
(М. Тыломиров, Ф. Петров)
Ответ
Ответ. .
Решение. Пронумеруем столбы от до вдоль дороги и примем за расстояние между соседними столбами. Пару одноцветных столбов, между которыми нет других столбов того же цвета, будем называть хорошей.
Оценка. Пусть столбов покрашены так, что условие задачи выполнено. Пусть — количество столбов -го цвета (далее считаем, что , т.е. все цвета присутствуют, иначе можно увеличить , добавив столб нового цвета в конец). Пусть и — номера первого и последнего столбов -го цвета.
Всего у нас есть хороших пар столбов. Поскольку все расстояния между столбами в хороших парах различны, наименьшее из этих расстояний не меньше , следующее — не меньше , и т.д. Так, для суммы расстояний во всех хороших парах получаем оценку .
С другой стороны, сумма всех расстояний для -го цвета равна . Поэтому . Сумма не превышает суммы самых больших среди номеров , а сумма не меньше, чем сумма наименьших среди номеров , поэтому .
Итак, , откуда и .
Пример. Годится, например, покраска
Здесь для цвета единственная хорошая пара, и расстояние между столбами в ней равно . Для всех остальных цветов есть две хорошие пары, при этом для цвета имеем расстояния и , для цвета — расстояния и , и т.д., для цвета — расстояния и .
Замечание. Существуют и другие, более сложные примеры. Например, можно первые столбов покрасить в цвета , а дальше столб с номером , где , окрасить в цвет (скажем, для покраска будет выглядеть так: ). Возможно индуктивное описание подходящих примеров.