Высшая проба 2021, 11 класс, задача 3
( баллов) В ряд стоят домов различных цветов, причем для любого цвета найдутся стоящих подряд домов, среди которых домов этого цвета строго больше, чем домов любого другого цвета. При каком наибольшем это возможно, если а) ? б) ?
Решение. Пункт а). Цветов не может быть больше , иначе есть цвет, в который покрашен только один дом, тогда домов этого этого цвета ни в каком отрезке не может быть строго больше, чем любого другого. Покажем пример на цвета, то есть такую раскраску, что для каждого цвета в него было покрашено ровно два дома, притом существует отрезок из домов, в который эта пара одноцветных попадает целиком, а любая другая - нет.
Назовем -блоком следующую конструкцию: подряд стоят домов, пары домов на расстоянии (т.е. такие, между которыми ровно других домов) покрашены в один цвет, и больше этого цвета домов нет (не только в блоке но вообще из участвующих домов); -блоком назовем стоящие подряд два дома, покрашенные в уникальный цвет. дома надо раскрасить так: -блок, -блок, два -блока, -блок, -блок. Осталось доказать, что эта раскраска подходит, мы оставляем это читателю в качестве несложного упражнения (но каждый участник, который оставил это жюри в качестве несложного упражнения, недосчитался одного балла).
Пункт б). Этот же пример позволяет реализовать цвета на домах - в конец добавим еще два дома, цвет которых совпадает с последним -блоком.
Оценка. Понятно что каждого цвета должно быть хотя бы два дома, значит ответ для не больше . Если для ответ , то каждого цвета ровно два дома. Занумеруем цвета в порядке их появления слева направо, и пусть дома -го цвета имеют номера и , причем . По определению . Докажем что .
Предположим противное, т.е. для каких-то оказалось . Вспомнив, что и , видим, что , то есть любой отрезок, содержащий , также содержит , то есть нет отрезка, на котором домов -го цвета больше всего - привели предположение к противоречию.
Докажем еще два полезных неравенства: - иначе нет отрезка из домов, в который попали оба из ; и - иначе каждый отрезок, содержащий , также содержит или или .
Все готово для решения. Среди первых номеров ровно одна -шка, это : иначе, если там есть и , среди домов от до есть два дома второго цвета, тогда для первого цвета нет отрезка, в котором его больше чем любого другого (поскольку только отрезок содержит два дома первого цвета, но он содержит и два дома второго). Значит среди первых домов ровно девятнадцать -шек. Значит из соответствующих им -шек восемнадцать лежат среди номеров от до , то есть там максимум одна -шка, это может быть только . Мы доказали, что . Повторив то же самое рассуждение с другого конца, получим, что . Но это противоречит неравенству (частный случай доказанного выше для
Решение пункта а состоит из.
B1 Доказательства оценки: не приносит баллов но снимаетесли не написано. B2Указаниеверногопримера:стоит(такимобразом,еслиестьB1++:оценка 7) B3Доказательствотого,чтопримеризB2работает.НеможетвстречатьсябезB2,приносит.
С Если пример, работающий для пункта а), написан в пункте б) – оценивается пункт а) как будто пример написан там, (если это больше баллов, чем родной текст пункта а).
пункта б) – только за оценку.
D0 Оценка.
Е0 Любые попытки описания явного вида “единственно возможной” раскраски в 43 цвета, содержащие пропущенный случай.
F1 Доказано, что если бы была покраска в 43 цвета, то центральный отрезок из 8 домов содержал бы для трех цветов оба дома этого цвета.