Всесиб 2024, отборочный этап, 7 класс, задача 5
( баллов) На доске написана фраза из русских букв, причём каждая из букв встречается хотя бы раз. Оказалось, что среди любых подряд идущих букв есть хотя бы различных. Докажите, что среди каких-то подряд идущих букв встретятся все буквы.
(Подробно обоснуйте свои рассуждения.)
Ответ
Решение. Подчеркнём в нашей фразе самую левую букву «А», самую левую «Б», ..., самую левую «Я». Рассмотрим самую правую из подчёркнутых букв. Пусть без ограничения общности это буква «Ы».
Если она стоит не дальше -й позиции слева, то среди первых букв встречаются все (потому что там стоят все подчёркнутые буквы).
Если же первая «Ы» находится после -й позиции, то рассмотрим букв перед ней. По условию среди них хотя бы различных. При этом «Ы» среди них нет, поэтому, добавив эту букву к предыдущим, получим искомую сотню, содержащую все буквы.