Divide et impera

Принцип «разделяй и властвуй» хорошо работает не только в большой политике, но и математике и информатике. Мы посмотрим на геометрические задачи о «делении поровну», обслуживающие этот принцип, как классические, так и современные. В рассказе появятся важные математические понятия: класс Эйлера, кривая Веронезе, конфигурационное пространство (что-то явно, что-то неявно).

Для разминки перед лекцией рекомендуется подумать над следующими задачами:
1) всякая плоская фигура может быть разделена двумя прямолинейными разрезами на четыре равные по площади части;
2) не всякая плоская фигура может быть разделена тремя прямолинейными разрезами на семь равных по площади частей.

Лекция: 20 июля (пн), 16:00 (обсуждение в 17:30)
Лектор: Гаянэ Юрьевна Панина (ПОМИ РАН)

Что это вообще?
А это летняя школа «Современная математика» в этом году проходить не будет, зато все желающие могут попасть на прекрасные математические вечера ЛШСМ.
Подробности и анонсы других вечеров: https://www.mccme.ru/dubna/lect2020/

Но это не всё.
Там пишут, что уровень высок, поэтому заранее советуют посмотреть видеозаписи прошлых школ. Вот они, все под рукой, там много интересного: https://mccme.ru/dubna/courses/

#лекции #видео

Вдогонку к спиралям и комплексным числам — есть вот такое четырёхсекундное видео
https://images.math.cnrs.fr/media/51/video.mp4
(отсюда — https://images.math.cnrs.fr/L-effet-Droste.html ; правда, там по-французски, но можно только посмотреть иллюстрации).
И об этом же —
https://twitter.com/i/status/1283275125618442245

http://kvant.mccme.ru/1994/01/podkova_smejla.htm

к сегодняшнему 90-летию Смейла
пусть здесь будет статья в Кванте про подкову Смейла

И вдогонку — брошюра ЛШСМ, заканчивающаяся как раз конструкцией подковы Смейла:
https://www.mccme.ru/free-books/dubna/ilyashenko-smale.pdf

Ну и — соответствующая глава из фильма "Хаос": https://www.chaos-math.org/ru/chaos-vi.html — вот тут показывают, как устроено символическое кодирование для неё: https://youtu.be/LktmWlabav0?t=363 (там есть русские субтитры)

Да, и более короткий ролик с подковой —
https://www.youtube.com/watch?v=SrJm6bkLuPs

По случаю прошедшего юбилея Сергея Константиновича — "байка о трёхглавом драконе".
(У меня, конечно, ещё не закончен рассказ про ренормализацию, но давайте я его чуть-чуть отложу.)

Давайте зададимся тремя вопросами.

Вопрос 1: сколько есть разных способов разложить цикл длины n в произведение (n-1) транспозиции?

Иными словами: мы расставили n статуй по стоящим вокруг площади постаментам, и только закончив работу, обнаружили, что перепутали, откуда надо было начинать. Статуя 1 стоит на постаменте 2, статуя 2 на постаменте 3, и так далее до статуи n, которая стоит на постаменте с подписью 1.

Надо их поставить на места; единственный доступный нам инструмент — "погрузчик", позволяющий поменять местами любые две статуи. Причём погрузчик нас просили вернуть как можно скорее — так что нужно обойтись минимальным числом операций.

Операций нам понадобится (n-1) — что, собственно, часть вопроса, но пока давайте в это поверим. Так вот, вопрос формулируется классическим комбинаторным образом: а сколькими способами мы сможем это сделать — поставить статуи на свои места за (n-1) применение погрузчика?

Вопрос 2: сколько есть разных деревьев с n пронумерованными от 1 до n вершинами?

Рассмотрим наши пронумерованные вершины как вершины полного графа. Тогда дерево с этими вершинами — это остовное дерево такого графа. Поэтому тот же вопрос можно переформулировать как "сколько есть остовных деревьев в полном графе на n вершинах" ?

Вопрос 3: сколько есть многочленов степени n с комплексными коэффициентами и с заданными (n-1) критическими значениями (т.е. значениями в критических точках — там, где производная обращается в 0)?

Понятно, что в такой формулировке ответом будет "бесконечность", потому что если мы сдвинем многочлен, перейдя от P(z) к P(z+a), критические значения от этого не изменятся. Поэтому можно наложить условие, что коэффициент при z^{n-1} равен 0 (как раз любой многочлен в такой можно единственным образом сдвинуть).
И ещё наложим условие, что старший коэффициент равен 1. Опять-таки, любой многочлен с данными критическими значениями к такому виду приводится — только на этот раз заменой w=bz при правильном выборе b. А если никакого условия тут не наложить, то все такие замены нам из одного решения сделают бесконечное количество — что естественно, потому что у нас неизвестных коэффициентов пока n, а условий на критические значения (n-1).

Так что окончательная формулировка третьего вопроса — сколько есть многочленов вида
z^n + a_{n-2}z^{n-2} +...+a_1 z + a_0
с заданными (n-1) критическими значениями c_1,...,c_{n-1} ?

---
Вопросы сформулированы — и давайте сначала немного посчитаем, какими будут ответы при небольших n. Проще всего это сделать для второго вопроса.

Для n=2 единственное дерево на двух вершинах это отрезок, так что ответ 1.
Для n=3 это два последовательных отрезка — но важно, какая из трёх вершин в центре, поэтому мы получаем 3 варианта (можно сказать, что полный граф на трёх вершинах это треугольник, а мы выкидываем одну из его сторон).
Для n=4 деревьев без пометок два, это три последовательных отрезка и "лапа" из трёх отрезков с общей вершиной. В первом случае пометки можно расставить 12 способами (потому что 24/2 — подписываем всеми возможными способами, а потом вспоминаем, что дерево можно перевернуть), во втором 4 (единственное, что важно, это значение в центральной вершине; ну или 24/6, потому что отрезки из центра переставляются 3!=6 способами).
Итого 12+4=16 вариантов.

Сколько существует деревьев с n вершинами? (Фрагмент — из «Задач от 5 до 15» Арнольда.)

Наконец, для n=5 есть три разных дерева без пометок:
* четыре отрезка в линию — вершины можно подписать 60=120/2 способами;
* лапа-трилистник, у которой один из выходящих отрезков продолжается ещё одним; тут вершины можно подписать тоже 60=120/2 способами;
* одна точка, из которой выходят все четыре ребра; тут есть всего 5=120/24 способов подписать вершины (единственное, что имеет значение, это номер центральной вершины).
Итого 60+60+5=125.

125 это 5^3, и это ответ при n=5. Если после этого посмотреть на 16 как на ответ при n=4, то немедленно хочется записать 16=4^2.

После чего последовательность ответов записывается как
2^0, 3^1, 4^2, 5^3,
и становится ясно, что ответом должно быть n^{n-2}.

Этот ответ носит название формулы Кэли — и давайте я опять процитирую коллег: