|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
СодержаниеММ15Конкурсная задача ММ15 (9 баллов)
В качестве вводной предлагается задачка из конкурса 'Кенгуру' 1998 года:
А теперь основная часть задачи: Решение Ответ на первый вопрос задачи очевиден: невозможна последовательность ГДЕБВА. После съедения пирога Е, согласно условию, должен был быть съеден пирог В.
Рассмотрим основную часть задачи.
Приведу более громоздкое, но зато явное (в лоб) решение 15-й задачи:
Обозначим через A(n,i) количество возможных перестановок множества {1,2,..,n}, начинающихся с i. Из таблицы легко просматривается рекуррентная формула . Для того, чтобы убедиться в справедливости этой формулы, заметим, что между возможными перестановками n-элементного множества, начинающимися с элемента не меньшего i, и возможными перестановками n+1-элементного множества, начинающимися в точности с элемента i+1 существует биекция. Эта биекция строится так: к перестановке n-элементного множества приписывается слева элемент i+1, а остальные элементы переписываются, причем элементы большие i увеличиваются на 1. Продолжив приведенную выше таблицу до 20-й строки и просуммировав элементы этой строки (разумеется, эти действия совсем не обязательно производить вручную), получим ответ - 6564120420 (двадцатое число Каталана). Обсуждение Для чисел Каталана Cn можно получить целых ряд явных и рекуррентных соотношений: ; ; . Награды За правильное решение этой задачи Борис Бух получает 9 призовых баллов.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|