Комбинаторика и логика на ПВГ

Пусть — это количество слов инопланетят, состоящих из букв.

Заметим, что единственное однобуквенное слово — это слово А. Двухбуквенных слов вообще нет, так как первая и последняя, то есть первая и вторая буквы — это А, но тогда две буквы А стоят рядом, что противоречит определению инопланетного слова. Трёхбуквенное слово тоже только одно — АБА. И четырёхбуквенное слово единственно — АББА. Таким образом,

Рассмотрим теперь какое-нибудь слово длины где Его последняя буква — это точно буква А, так как каждое слово начинается и заканчивается буквой А. Предпоследняя буква — это Б, так как две буквы А не могут идти подряд. Есть два варианта, какой может быть буква перед Б, то есть предпредпоследняя буква слова :

1) Это буква А. Тогда слово имеет вид А...АБА. Рассмотрим строку из первых букв этого слова. Она начинается и заканчивается на А, а так же в ней нет двух букв А подряд или трёх букв Б подряд, так как иначе не было бы словом. А значит эта строка сама является словом.

2) Это буква Б. Тогда перед этой буквой Б стоит буква А, там как три буквы Б не могут идти подряд, и слово имеет вид А...АББА. Аналогично случаю 1, строка, образованная первыми буквами будет являться словом.

Получается, что слово могло быть получено либо приписыванием строки БА в конец какого-нибудь слова из букв, либо приписыванием строки ББА в конец какого-нибудь слова из букв. При этом, приписав в конец каждого из слов длины строку БА, мы получим различных слов длины Аналогично, приписав в конец каждого из слов длины строку ББА, мы получим различных слов длины Отсюда,

Пользуясь этой формулой, найдем для

Итак, в словаре сказочной планеты 86 20-буквенных слов.

Заметим, что треугольники здесь будут только прямоугольные с углом . Кроме того, их гипотенуза лежит на гипотенузе изначального треугольника, поскольку все остальные отрезки проходят только по линиям сетки. Заметим также, что положением гипотенузы задаётся весь треугольник, потому достаточно посчитать количество различных отрезков с концами в целых точках на отрезке длины (так получится, если уменьшить всю гипотенузу в раз). Длины отрезков будет , длины — ,.. длины — . Итого имеем различных треугольников.

Из условия получаем, что чёрных кусочков граничат суммарно с белыми, соответственно белых кусочков граничат с чёрными. То есть число границ между белыми и чёрными кусочками равно с одной стороны а с другой стороны Отсюда находим, что

Самым старшим может быть или Борис, или Виктор. Но Виктор не мог занять второе место, так как он уступил и Антону, и Григорию. Поэтому Борис — второй. Значит, Григорий — первый, Антон — третий, а Виктор четвертый.

Выбор каждого вида игроков осуществляется независимо, поэтому количества способов нужно просто перемножить. Покажем, что число способов выбрать человек из подходящих на эту роль равно

Действительно, сначала рассмотрим все перестановки из человек (которых ), будем брать в команду первых из них. Тогда нам не важен порядок этих человек, то есть нужно поделить на , а также не важен порядок следующих за ними человек, то есть нужно поделить ещё на . Что здесь означает не важен порядок? Если мы его изменим, то выбранная нами команда не поменяется.

В итоге мы показали, что способов Используя эту формулу для всех типов игроков и перемножая результаты, получаем

Сначала определим порядок между книгами, а потом разделим их двумя перегородками на 3 непустых множества (будем рассматривать всевозможные разбиения данного набора книг), например

Первое множество положим на первую полку, второе — на вторую, третье — на третью. Расставить книги в ряд можно способами, для перегородок между книгами мест, тогда количество способов расставить две перегородки равно Получим

Заметим, что на математике, физике и русском было и «учеников» (прогульщиков) соответственно. Суммарно получается но каждый «ученик» здесь посчитан дважды (потому что каждый из них посетил два предмета), то есть на самом деле их А всего ребят в классе тогда Получается, что на русский язык не пришли человек, зато они присутствовали и на физике, и на математике. Добавляя настоящих учеников (которым удалось не прогулять ни один предмет), получаем ответ.

Заметим, что такая укладка карандашей соответствует таблице куда мы ставим числа от до так, чтобы во всех столбцах и строках числа шли по возрастанию (таблица — это коробка, число — это номер карандаша по возрастанию длины: — самый короткий, — самый длинный). Данная формулировка задачи является одним из определений чисел Каталана и очень легко сопоставляется правильной скобочной последовательности: число — номер скобки, положение числа (в верхней строке или в нижней) — открытая это скобка или закрытая, соответственно.