Закл (финал) 11 класс

Пример. Рассмотрим все слов, у которых начиная с -ой все буквы Ш, а первые — У или Я. Этот набор слов удовлетворяет условию.

Оценка. Каждому из наших слов сопоставим слов, заменяя каждую букву Ш, на У или Я (всеми возможными способами). Заметим, что полученные слов состоят из букв У и Я и попарно различны (для слов, полученных из одного и того же, это ясно из построения, а для слов, полученных из двух разных, следует из условия). Таким образом, и

______________________________________________________________________________________________________________________________________________________

Замечание. Оценку можно получить по-другому.

Способ 1. Подкинем монетку раз. Для каждого слова рассмотрим такое событие: при всяком если на некоторой позиции стоит буква У, то при -м подбрасывании выпала решка, а если буква Я, то орёл. Вероятность такого события равна и они не совместные, поэтому количество слов не больше чем

Способ 2. Пусть выбрано более слов. Присвоим каждому слову вес Пусть первая буква у слов У, у слов — Я и Удвоим веса всех слов с первой буквой У, и обнулим — с первой буквой Я. Далее посмотрим на вторую букву и т.д. Опишем шаг рассмотрения -ой буквы. Пусть — сумма весов слов, у которых -ая буква У, — сумма весов слов, у которых -ая буква Я. Если удваиваем веса у слов с -й буквой Я и обнуляем — с -й буквой У. Иначе — наоборот. В результате таких операций сумма весов не уменьшается. После операций сумма весов всех слов будет больше В каждом слове только букв У или Я, поэтому вес каждого слова не больше Значит, найдутся два слова с одинаковыми весами. Тогда для них не найдется позиции, в которой у одного У, а у другого Я или наоборот, противоречие.