Регион до 2015
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В языке племени АУ две буквы — 
и 
Некоторые последовательности этих букв являются словами, причём в каждом слове не больше
букв. Известно, что если написать подряд любые два слова, то полученная последовательность букв не будет словом. Найдите
максимальное возможное количество слов в таком языке.
Источники:
Подсказка 1
Сколько существует слов длины n, которые состоят только из буквы a и у?
Подсказка 2
Верно, 2^n. Может ли в искомом множестве слов не быть слов длины 13?
Подсказка 3
Нет, потому что мы можем взять только слова длины 13, их количество больше, чем количество всех остальных слов. Как это соображение помогает построить пример?
Подсказка 4
Давайте возьмем в множество все слова длины хотя бы 7. Чему равно количество слов? Почему нельзя больше?
Подсказка 5
Количество слов равно 2¹⁴ - 2⁷ . Может ли в искомом множестве не быть слов длины 7?
Подсказка 6
Нет, не может. Пусть так же в языке есть k слов длины не больше 6. Докажите, что тогда количество не превосходит 2¹⁴ - 2⁷ - k.
Если все последовательности, количество букв в которых не меньше 
и не больше 
являются словами, то, очевидно, условие задачи
соблюдается; при этом количество таких слов равно 
Осталось показать, что это количество — наибольшее
возможное.
Общее количество последовательностей длины, не превосходящей 
равно 
Если среди слов в языке нет ни
одного 
-буквенного, то общее количество слов не превосходит 
Пусть, напротив, в языке существует 
-буквенное
слово 
Тогда для каждого слова 
состоящего из 
или менее букв, последовательность букв 
не может являться словом, и все
последовательности вида 
очевидно, различны. Значит, если в языке есть 
слов из 
или менее букв, то количество слов из хотя бы
букв не превосходит 
Значит, общее количество слов не превосходит 
что и требовалось доказать.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
