Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ15

Конкурсная задача ММ15 (9 баллов)

В качестве вводной предлагается задачка из конкурса 'Кенгуру' 1998 года:
Мама печет 6 пирогов: сначала пирог с абрикосами (А), потом с брусникой (Б), с вишней (В), с грибами (Г), с джемом (Д) и с ежевикой (Е). Пока она этим занимается, на кухню иногда забегают дети и каждый раз съедают самый горячий пирог. В каком порядке не могли быть съедены пироги?
1) АБВГДЕ; 2) АБДГВЕ; 3) ВБДГЕА; 4) ГДЕБВА; 5) ЕДГВБА. (1 балл)

А теперь основная часть задачи:
Назовем перестановку множества {1,2,…,n} возможной, если она удовлетворяет условию вводной задачки. Сколько возможных перестановок для n=20? (8 баллов)

Решение

Ответ на первый вопрос задачи очевиден: невозможна последовательность ГДЕБВА. После съедения пирога Е, согласно условию, должен был быть съеден пирог В.

Рассмотрим основную часть задачи.
Для тех, кто знаком с числами Каталана (и сумеет разглядеть их в условии), задача ММ15 является достаточно легкой. В самом деле, по условию задачи чем позднее приготовлен каждый из n пирогов (скобка открылась), тем раньше он съеден (скобка закрылась), что соответствует правильной расстановке n пар скобок. Таким образом, количество возможных перестановок на множестве {1,2,…n} равно количеству правильных расстановок n пар скобок, которое, в свою очередь есть n-ое число Каталана.

Приведу более громоздкое, но зато явное (в лоб) решение 15-й задачи:
Рассмотрим количество возможных перестановок для небольших значений n. При этом отдельно посчитаем перестановки, начинающиеся с 1, 2, … n. Результаты занесем в таблицу.

n\i 1 2 3 4 5 6
1 1
2 1 1
3 2 2 1
4 5 5 3 1
5 14 14 9 4 1
6 42 42 28 14 5 1

Обозначим через A(n,i) количество возможных перестановок множества {1,2,..,n}, начинающихся с i. Из таблицы легко просматривается рекуррентная формула A(n+1,i+1) = sum{j=i}{n}A(n,j).

Для того, чтобы убедиться в справедливости этой формулы, заметим, что между возможными перестановками n-элементного множества, начинающимися с элемента не меньшего i, и возможными перестановками n+1-элементного множества, начинающимися в точности с элемента i+1 существует биекция. Эта биекция строится так: к перестановке n-элементного множества приписывается слева элемент i+1, а остальные элементы переписываются, причем элементы большие i увеличиваются на 1. Продолжив приведенную выше таблицу до 20-й строки и просуммировав элементы этой строки (разумеется, эти действия совсем не обязательно производить вручную), получим ответ - 6564120420 (двадцатое число Каталана).

Обсуждение

Для чисел Каталана Cn можно получить целых ряд явных и рекуррентных соотношений:

C_{n+1} = {4n+2}/{n+2}C_n;

C_n = 1/{n+1}(matrix{2}{1}{{2n}{n}});

C_0 = 1, C_{n+1} = sum{i=0}{n}{C_i C_{n-i}}.

Награды

За правильное решение этой задачи Борис Бух получает 9 призовых баллов.


 

 


Страница: [[marathon:problem_15]]

marathon/problem_15.txt · Последние изменения: 2019/07/24 10:00 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006