Высшая проба 2021, 10 класс, задача 3
( баллов) В ряд стоят домов различных цветов, причем для любого цвета найдутся стоящих подряд домов, среди которых домов этого цвета строго больше, чем домов любого другого цвета. При каком наибольшем это возможно, если а) ? б) ?
Решение
Пункт а). Цветов не может быть больше , иначе есть цвет, в который покрашен только один дом, тогда домов этого цвета ни в каком отрезке не может быть строго больше, чем любого другого. Покажем, как построить пример на цвета, то есть чтобы для каждого цвета в него было покрашено ровно два дома, притом существовал бы отрезок, в который эта пара одноцветных попадает, а любая другая — нет. Назовем -блоком следующую конструкцию: подряд стоят домов, пары домов на расстоянии (т. е. такие, между которыми ровно других домов) покрасим в один цвет, и больше в цвет этой пары не будем красить другие дома (не только в этом блоке, но и вообще из участвующих домов); -блоком назовем стоящие подряд два дома, покрашенные в уникальный цвет. Тогда дома можно раскрасить так: -блок, -блок, -блок, -блок, -блок, -блок. Осталось показать, что этот пример верный. В самом деле, у любого -блока есть соседний -блок, а значит, можно взять домов подряд, у которых -блок является крайним, а все остальные цвета встречаются по одному разу. Для цветов -блока можно взять домов, содержащих оба дома цвета . Тогда домов этого цвета будет два, а все остальные цвета будут встречаться на этом отрезке по одному разу. Пункт б). Этот же пример позволяет реализовать цвета на домах: в конец добавим еще два дома, цвет которых совпадает с последним -блоком. Оценка. Понятно, что в каждый цвет должно быть покрашено хотя бы два дома, значит, ответ для не больше . Если для ответ , то в каждый цвет покрашено ровно два дома. Оценка. Понятно, что в каждый цвет должно быть покрашено хотя бы два дома, значит, ответ для не больше . Если для ответ , то в каждый цвет покрашено ровно два дома. Занумеруем цвета в порядке их появления слева направо, и пусть дома -го цвета имеют номера и , причем . По определению
Докажем, что
Предположим противное, то есть для каких-то оказалось . Вспомнив, что и , получаем , то есть любой отрезок, содержащий , также содержит . Значит, нет отрезка, на котором домов -го цвета больше всего. Противоречие.
Заметим, что должны выполняться еще два неравенства:
и
Среди первых номеров домов есть ровно один номер из множества , это : иначе, если там есть и , среди домов от до есть два дома второго цвета, тогда для первого цвета нет отрезка, в котором его больше чем любого другого. Значит, среди первых домов ровно имеют номера из множества . Тогда среди номеров от до должны присутствовать чисел из множества , следовательно, из множества там может быть максимум один номер, то есть . Мы доказали, что .
Повторив то же самое рассуждение с другого конца, получим, что . Но это противоречит неравенству : мы не сможем найти отрезок из домов для $i=102
3b.
А0 Не объяснено или плохо доказано противоречие для 8 домов и 3 цветов.
А1 Пример (даже без обоснования) без оценки.
А2 Серьёзные ошибки или плохие доказательства в рассуждениях до центральных домов (включая цен- тральные количества, отличные от 8), есть замечание или попытка вывести противоречие из трёх пар в центральной группе.