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