ВсОШ 2021, 11 класс, задача 3
В языке три буквы - , и . Словом называется последовательность из букв, ровно из которых - гласные (то есть или ), а остальные - буква . Какое наибольшее количество слов можно выбрать так, чтобы у любых двух выбранных слов хотя бы в одной из ста позиций одновременно стояли гласные, причем различные?
(Ф. Петров)
Ответ
Ответ.
.
Решение.
Пример. Рассмотрим все слов, у которых начиная с -й все буквы , а первые - или . Этот набор слов удовлетворяет условию.
Оценка. Каждому из наших слов сопоставим слов, заменяя каждую букву , на или (всеми возможными способами). Заметим, что полученные слов состоят из букв и и попарно различны (для слов, полученных из одного и того же, это ясно из построения, а для слов, полученных из двух разных, следует из условия). Таким образом, и .
Замечание.
Оценку можно получить по-другому.
Способ 1. Подкинем монетку раз. Для каждого слова рассмотрим такое событие: при всяком если на некоторой позиции стоит буква , то при -м подбрасывании выпала решка, а если буква , то орел. Вероятность такого события равна , и они не совместные, поэтому количество слов не больше чем .
Способ 2. Пусть выбрано более слов. Присвоим каждому слову вес . Пусть первая буква у слов , у слов - и . Удвоим веса всех слов с первой буквой , и обнулим - с первой буквой . Далее посмотрим на вторую букву и т.д. Опишем шаг рассмотрения -ой буквы. Пусть - сумма весов слов, у которых -ая буква , - сумма весов слов, у которых -ая буква . Если , удваиваем веса у слов с -й буквой и обнуляем - с -й буквой . Иначе - наоборот. В результате таких операций сумма весов не уменьшается. После операций сумма весов всех слов будет больше . В каждом слове только букв или , поэтому вес каждого слова не больше . Значит, найдутся два слова с ненулевыми весами. Тогда для них не найдется позиции, в которой у одного , а у другого или наоборот, противоречие.