Олимпиадная комбинаторика: от правил подсчёта до формулы БернсайдаВебинар 5. Рекурсии в комбинаторике: от разбиения на случаи до чисел Фибоначчи и Каталана📅 16 ноября в 17:00 Мск
🔗 Страница вебинара на Антитренингах (там анонс + оплата + листок с задачами):
https://antitreningi.ru/pay/shop/F4GAq2b1anao(ссылка может плохо открываться при включённом VPN)
📄 Листок с задачами:
https://mathus.ru/webinars/recurs.pdfСколькими способами можно подняться по лестнице? Как подсчитать количество допустимых слов или расписаний? Сколько существует способов разбить многоугольник на треугольники или соединить точки окружности непересекающимися хордами? На первый взгляд это совершенно разные задачи — но за ними скрываются одни и те же комбинаторные идеи.
Во многих задачах прямой подсчёт оказывается слишком сложным. Но если разбить все возможные варианты на несколько случаев и свести подсчёт к более простым задачам, то возникает рекуррентное соотношение. Так мы приходим к одному из самых универсальных методов комбинаторики, а заодно открываем замечательные числовые последовательности — числа Фибоначчи и Каталана.
📌
На вебинаре разберём:🔹 Как составлять рекуррентные соотношения, разбивая комбинаторные объекты на непересекающиеся случаи.
🔹 Почему числа Фибоначчи возникают в задачах о подъёме по лестнице и как обобщать соответствующую рекурсию.
🔹 Как подсчитывать количество слов и других последовательностей, на которые наложены различные ограничения.
🔹 Как выбирать состояния и составлять системы рекуррентных соотношений, когда одной последовательности недостаточно.
🔹 Как с помощью рекурсий решать задачи о случайных последовательностях, перемещениях по вершинам треугольника и составлении расписаний.
🔹 Как простая задача о прыжках кролика приводит к числам Каталана и как вывести определяющее их рекуррентное соотношение.
🔹 Почему та же рекурсия возникает при разбиении многоугольников на треугольники.
🔹 Как с помощью принципа отражения подсчитать неправильные последовательности прыжков и получить явную формулу для чисел Каталана.
🔹 Как применять числа Каталана в задачах о непересекающихся хордах и в неожиданных олимпиадных задачах на вероятность.
🎯
Главная цель вебинара — научиться самостоятельно находить рекуррентные соотношения. Мы будем учиться правильно разбивать множество объектов на случаи, выбирать удобные состояния и выражать количество сложных объектов через количество более простых. Особое внимание уделим числам Каталана: начав с элементарной задачи о прыжках кролика по лестнице, мы выведем определяющую их рекурсию, обнаружим её в задаче о триангуляции многоугольника, а затем получим явную формулу с помощью принципа отражения.
А завершит вебинар необычная задача AIME о кирпиче и коробке. Из тысячи различных чисел случайным образом выбирают размеры двух прямоугольных параллелепипедов. Какова вероятность того, что один из них можно поместить внутрь другого? Оказывается, и здесь неожиданно возникают числа Каталана!
👥 Вебинар предназначен для школьников 8–11 классов, преподавателей и всех желающих.
💻 Занятие пройдёт в Zoom. Продолжительность — 120+ минут.
🎥 Вебинар будет доступен также и в записи. К видеозаписи прилагаются PDF-файлы решений задач, которые были разобраны мною во время трансляции.
💰
Стоимость вебинара = 500, 1000, 1500, 2000 или 3000 ₽ на ваш выбор. Вы выбираете сумму самостоятельно, исходя из своих возможностей и желания поддержать мою работу.
При любой выбранной сумме вы получаете совершенно одинаковое участие в вебинаре и полный доступ ко всем его материалам (видеозаписи и файлам решений).
Новый список