ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64628
Темы:    [ Классическая комбинаторика (прочее) ]
[ Мощность множества. Взаимно-однозначные отображения ]
[ Оценка + пример ]
Сложность: 4-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

В языке племени АУ две буквы – "a" и "y". Некоторые последовательности этих букв являются словами, причём в каждом слове не меньше одной и не больше 13 букв. Известно, что если написать подряд любые два слова, то полученная последовательность букв не будет словом. Найдите максимальное возможное количество слов в таком языке.


Решение

  Если все последовательности, количество букв в которых не меньше 7 и не больше 13, являются словами, то, очевидно, условие задачи соблюдается; при этом количество таких слов равно  27 + ... + 213 = 214 – 27.  Осталось показать, что это количество – наибольшее возможное.

  Первый способ. Общее количество последовательностей длины, не превосходящей 13, равно  2 + 22 + ... + 213 = 214 – 2.  Если среди слов в языке нет ни одного 7-буквенного, то общее количество слов не превосходит  214 – 2 – 27 < 214 – 27.  Пусть, напротив, в языке существует 7-буквенное слово s. Тогда для каждого слова t, состоящего из 6 или менее букв, последовательность букв st не может являться словом, и все последовательности вида st, очевидно, различны. Значит, если в языке есть k слов из 6 или менее букв, то количество слов из хотя бы 7 букв не превосходит
(27 + ... + 213) – k = 214 – 27k.  Следовательно, общее количество слов не превосходит  k + (214 – 27k) = 214 – 27,  что и требовалось доказать.

  Второй способ. Пусть A – множество всех последовательностей из 6 или менее букв, а B – множество всех 7-буквенных последовательностей. Тогда в A всего  2 + 22 + ... + 26 = 27 – 2  последовательностей, а в B всего  27 > 27 – 2  последовательностей. Значит, можно сопоставить каждой последовательности aA последовательность baB так, что все последовательности ba различны. Заметим, что тогда все последовательности вида aba также различны (поскольку различны их 7-буквенные окончания).
  По условию в каждой из  27 – 2  троек  (a, ba, aba)  не больше двух слов языка. Следовательно, хотя бы  27 – 2  последовательностей из 13 или меньше букв не являются словами, и общее количество слов не больше  (214 – 2) – (27 – 2) = 214 – 27.


Ответ

214 – 27 = 16256 слов.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2013-2014
этап
1
Вариант 4
класс
Класс 10
задача
Номер 10.3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .