Задача 64628

Темы:    [ Классическая комбинаторика (прочее) ] [ Мощность множества. Взаимно-однозначные отображения ] [ Оценка + пример ]

Сложность: 4- Классы: 9,10,11

Условие

Автор: Богданов И.И.

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

Решение

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

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

  Второй способ. Пусть A – множество всех последовательностей из 6 или менее букв, а B – множество всех 7-буквенных последовательностей. Тогда в A всего  2 + 2² + ... + 2⁶ = 2⁷ – 2  последовательностей, а в B всего  2⁷ > 2⁷ – 2  последовательностей. Значит, можно сопоставить каждой последовательности a ∈ A последовательность b_a ∈ B так, что все последовательности b_a различны. Заметим, что тогда все последовательности вида ab_a также различны (поскольку различны их 7-буквенные окончания).
  По условию в каждой из  2⁷ – 2  троек  (a, b_a, ab_a)  не больше двух слов языка. Следовательно, хотя бы  2⁷ – 2  последовательностей из 13 или меньше букв не являются словами, и общее количество слов не больше  (2¹⁴ – 2) – (2⁷ – 2) = 2¹⁴ – 2⁷.

Ответ

2¹⁴ – 2⁷ = 16256 слов.

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

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