Высшая проба 2021, 8 класс, задача 6
( баллов) В ряд стоят домов различных цветов, причем для любого цвета найдутся стоящих подряд домов, среди которых домов этого цвета строго больше, чем домов любого другого цвета. При каком наибольшем это возможно, если: а) ? б) ?
Ответ: цвета в обоих пунктах. Решение:
Пример для пункта а) на цвета:
Назовем -блоком подряд идущих домов, у которых любую пару домов на расстоянии мы покрасили в уникальный цвет (то есть среди всех домов нет других домов такого цвета).
Назовём -блоком пару домов, которую мы покрасили в уникальный цвет.
Теперь покрасим дома так: -блок, -блок, -блок, -блок, -блок, -блок.
домов тоже можно покрасить в цвета, добавив в конец два дома, цвет которых совпадает с последним -блоком.
Оценка в пункте а):
Для каждого цвета должно быть хотя бы дома домов максимум .
Оценка в пункте б):
Пусть мы смогли покрасить домов в цвета, то есть каждый цвет использован раза.
Пронумеруем цвета в порядке появления при обходе домов, то есть для цвета в него были покрашены дома с номерами и , причём , .
Заметим, что тогда и , так как если , , то , но тогда любой отрезок, содержащий оба дома -го цвета содержит и оба дома -го цвета.
Теперь вместо раскраски домов рассмотрим последовательность букв и , где вместо домов, номер которых имеет вид ( - где ).
Из первых букв ровно одна , ведь для -ого цвета отрезок может быть только с первого по сотый дом.
(То есть первый цвет в нём встречается два раза, а любой другой - максимум ).
Значит среди первых букв ашек. Значит среди букв от до как минимум бшек.
(Так как есть чисел , для которых , но , так как ).
Тогда среди первых домов максимум ашек, то есть .
Аналогично, среди последних домов максимум бшек, , то есть
Теперь рассмотрим сотню для и . Либо она содержит , тогда она содержит и , либо она содержит , а тогда и .
Тогда эта сотня содержит и дома другого цвета, противоречие
Правильное решение:Проверять правильный пример не требуется, пример в пункте б) отдельно не оценивается + Пункт а) (пример плюс простая оценка).
Только пример.