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