Forwarded from Математические этюды
Процесс колебаний маятника Чеботаева или, как часто его называют — волнового маятника, завораживает https://etudes.ru/models/Chebotaev-wave-pendulum/ .
В какой-то момент наблюдатель видит синусоиду, через некоторое время переплетающиеся синусоиды, в некоторые моменты шары разделяются на группы, находящиеся в красивых правильных положениях… Достигается это правильным подбором длин маятников.
В какой-то момент наблюдатель видит синусоиду, через некоторое время переплетающиеся синусоиды, в некоторые моменты шары разделяются на группы, находящиеся в красивых правильных положениях… Достигается это правильным подбором длин маятников.
Forwarded from Непрерывное математическое образование
https://zadachi.mccme.ru/2012/pics.html
сегодня вместо картинок по выходным — вот такая страница с разными геометрическими рисунками (на скриншоте несколько примеров) —
в честь 15 000 задач в ИПС «Задачи по геометрии»
и напомним отзывы коллег к предыдущему юбилею — https://old.mccme.ru/head/news/zadachi10000.htm
сегодня вместо картинок по выходным — вот такая страница с разными геометрическими рисунками (на скриншоте несколько примеров) —
в честь 15 000 задач в ИПС «Задачи по геометрии»
и напомним отзывы коллег к предыдущему юбилею — https://old.mccme.ru/head/news/zadachi10000.htm
Forwarded from Непрерывное математическое образование
Сергей Петрович Новиков (20.03.1938–06.06.2024)
Завершая (ну, почти) тему выборов из списков с условиями, давайте я вернусь к задаче о Кощее, Иване-дураке и волшебной дудочке — и вообще к последовательностям с запретами.
Эту часть мне рассказал Алексей Куликов — спасибо ему за ссылки и комментарии!
Помните, я когда-то упоминал последовательность Морса-Туэ, явно предъявляемую последовательность 0 и 1, в которой нет тройных повторов (и даже подслов вида aXaXa). Её можно построить бесконечным применением к начальному слову w_1=0 бесконечной череды замен
0->01, 1->10,
а ещё она получается, если каждый индекс n записать в двоичной системе, а потом сложить «цифры» по модулю 2. Получается слово
w=0110100110010110…
Если цифр есть хотя бы три — то есть слова, в которых никакое подслово не повторяется подряд даже дважды (нет никаких подслов вида XX). И такие слова тоже впервые построил Аксель Туэ — вот тут можно посмотреть переводы его работ, и на с. 11 есть утверждение:
Theorem 2.1 (Satz 3). There exist arbitrarily long square-free words over three letters.
Итак, если рассматривать слова из k символов 1,2,…,k и запрет на повтор подслов — то уже при k=3 такое бесконечное слово есть. Вы ведь уже догадались, что будет дальше?
Вопрос. Пусть для каждого n задан список A_n из хотя бы k символов. Обязательно ли существует бесконечное слово w=(w_n), такое, что:
- каждый символ w_n выбирается из соответствующего списка A_n, и
- w не содержит квадратов, т. е. подслов вида XX?
Конечно, очень хочется сказать, что когда символы различные, не иметь повторений проще… Только вот мы уже знаем, что для «списочной» задачи четырёх красок не просто из этого не получается сделать строгое рассуждение, а даже ответ другой, нужно 5 красок в списке!
Для k=4 ответ на вопрос выше положительный — и совсем недавний! Его сначала получили в статье A new approach to nonrepetitive sequences Jarosław Grytczuk, Jakub Kozik, Piotr Micek (препринт 2011 года, статья).
Они использовали такое рассуждение: будем каждый раз дописывать случайную букву (из списка для текущего номера), а потом, если вдруг на конце появился повтор XX, второе повторённое X сотрём. Оказывается, тогда рано или поздно мы напишем сколь угодно длинное слово без повторов.
Потому что — давайте сделаем большое число M шагов такого процесса и будем, как шахматисты, вести протокол, записывая в него:
* на каждом шаге — то, как меняется текущая длина слова (она может возрасти на 1 или уменьшиться на длину вычеркнутого слова |X|).
* и в конце — «финальную позицию», какое слово в итоге получилось.
Несложно понять, что по такому протоколу можно восстановить обратным ходом и всю «партию»: если нам удавалось добавить букву, то от текущего слова нужно последнюю стереть, а если нет, то мы знаем, слово X какой длины было вычеркнуто, так что мы сначала повторяем последние |X| букв, возвращая вычеркнутое X на место, а потом стираем последнюю (дописанную на этом шаге) букву.
Так вот — оказывается, что если строящееся слово не может оказаться длиннее n символов, то при достаточно большом числе шагов M нам не хватит протоколов. Потому что всех партий 4^M, финальных позиций вообще ограниченное количество, а количество путей, по которым изменяется длина слова, можно оценить через ~числа Каталана как o(4^M). Точнее — давайте записывать изменение длины как последовательность из M символов « +1 » (когда пытаемся дописать букву) и почти M символов « -1 » (в количестве |X| там, где вычёркивается слово X). Эта последовательность длины не больше 2M, и все её частичные суммы остаются между 0 и n, так что легко поверить, что такие последовательности составляют (на самом деле, даже экспоненциально) малую долю от всех
2^{2M+1} -1 = 2*4^M -1
последовательностей из +1 и -1 длины не больше 2M.
Вот и получается, что игр всего 4^M, а протоколов o(4^M). При том, что по протоколу ход игры однозначно восстанавливается. Противоречие.
Эту часть мне рассказал Алексей Куликов — спасибо ему за ссылки и комментарии!
Помните, я когда-то упоминал последовательность Морса-Туэ, явно предъявляемую последовательность 0 и 1, в которой нет тройных повторов (и даже подслов вида aXaXa). Её можно построить бесконечным применением к начальному слову w_1=0 бесконечной череды замен
0->01, 1->10,
а ещё она получается, если каждый индекс n записать в двоичной системе, а потом сложить «цифры» по модулю 2. Получается слово
w=0110100110010110…
Если цифр есть хотя бы три — то есть слова, в которых никакое подслово не повторяется подряд даже дважды (нет никаких подслов вида XX). И такие слова тоже впервые построил Аксель Туэ — вот тут можно посмотреть переводы его работ, и на с. 11 есть утверждение:
Theorem 2.1 (Satz 3). There exist arbitrarily long square-free words over three letters.
Итак, если рассматривать слова из k символов 1,2,…,k и запрет на повтор подслов — то уже при k=3 такое бесконечное слово есть. Вы ведь уже догадались, что будет дальше?
Вопрос. Пусть для каждого n задан список A_n из хотя бы k символов. Обязательно ли существует бесконечное слово w=(w_n), такое, что:
- каждый символ w_n выбирается из соответствующего списка A_n, и
- w не содержит квадратов, т. е. подслов вида XX?
Конечно, очень хочется сказать, что когда символы различные, не иметь повторений проще… Только вот мы уже знаем, что для «списочной» задачи четырёх красок не просто из этого не получается сделать строгое рассуждение, а даже ответ другой, нужно 5 красок в списке!
Для k=4 ответ на вопрос выше положительный — и совсем недавний! Его сначала получили в статье A new approach to nonrepetitive sequences Jarosław Grytczuk, Jakub Kozik, Piotr Micek (препринт 2011 года, статья).
Они использовали такое рассуждение: будем каждый раз дописывать случайную букву (из списка для текущего номера), а потом, если вдруг на конце появился повтор XX, второе повторённое X сотрём. Оказывается, тогда рано или поздно мы напишем сколь угодно длинное слово без повторов.
Потому что — давайте сделаем большое число M шагов такого процесса и будем, как шахматисты, вести протокол, записывая в него:
* на каждом шаге — то, как меняется текущая длина слова (она может возрасти на 1 или уменьшиться на длину вычеркнутого слова |X|).
* и в конце — «финальную позицию», какое слово в итоге получилось.
Несложно понять, что по такому протоколу можно восстановить обратным ходом и всю «партию»: если нам удавалось добавить букву, то от текущего слова нужно последнюю стереть, а если нет, то мы знаем, слово X какой длины было вычеркнуто, так что мы сначала повторяем последние |X| букв, возвращая вычеркнутое X на место, а потом стираем последнюю (дописанную на этом шаге) букву.
Так вот — оказывается, что если строящееся слово не может оказаться длиннее n символов, то при достаточно большом числе шагов M нам не хватит протоколов. Потому что всех партий 4^M, финальных позиций вообще ограниченное количество, а количество путей, по которым изменяется длина слова, можно оценить через ~числа Каталана как o(4^M). Точнее — давайте записывать изменение длины как последовательность из M символов « +1 » (когда пытаемся дописать букву) и почти M символов « -1 » (в количестве |X| там, где вычёркивается слово X). Эта последовательность длины не больше 2M, и все её частичные суммы остаются между 0 и n, так что легко поверить, что такие последовательности составляют (на самом деле, даже экспоненциально) малую долю от всех
2^{2M+1} -1 = 2*4^M -1
последовательностей из +1 и -1 длины не больше 2M.
Вот и получается, что игр всего 4^M, а протоколов o(4^M). При том, что по протоколу ход игры однозначно восстанавливается. Противоречие.
А потом кто-то придумал, что можно пройти рассуждением, аналогичным тому, что мы уже видели: доказать по индукции, что число разрешённых слов L_n растёт по крайней мере как L_{n+1}>=2 L_n.
Потому что — опять же, из разрешённых слов длины n можно получить 4*L_n слов, дописывая все возможные последние буквы. После этого — если на конце появился повтор XX, то есть w=RXX, то ему можно сопоставить слово w’=RX, и по w’ исходное w восстанавливается: мы видим, сколько букв вычеркнуто, и повторяем хвост такой длины. Так что
L_{n+1} >= 4*L_n - L_n - L_{n-1} - L_{n-2} - …,
и индукция по n завершает рассуждение (буквально так же, как мы уже видели) : вычтя 2L_n из обеих частей, получаем
L_{n+1}-2L_n >= L_n - L_{n-1} - L_{n-2} - …
>= L_{n-1} - L_{n-2} - L{n-3} - …
>= L_{n-2} - L_{n-3} - L{n-4} - …
>= 0.
А вопрос про k=3 — всё ещё открыт!
Потому что — опять же, из разрешённых слов длины n можно получить 4*L_n слов, дописывая все возможные последние буквы. После этого — если на конце появился повтор XX, то есть w=RXX, то ему можно сопоставить слово w’=RX, и по w’ исходное w восстанавливается: мы видим, сколько букв вычеркнуто, и повторяем хвост такой длины. Так что
L_{n+1} >= 4*L_n - L_n - L_{n-1} - L_{n-2} - …,
и индукция по n завершает рассуждение (буквально так же, как мы уже видели) : вычтя 2L_n из обеих частей, получаем
L_{n+1}-2L_n >= L_n - L_{n-1} - L_{n-2} - …
>= L_{n-1} - L_{n-2} - L{n-3} - …
>= L_{n-2} - L_{n-3} - L{n-4} - …
>= 0.
А вопрос про k=3 — всё ещё открыт!
Forwarded from Непрерывное математическое образование
novikov-interview-2001.pdf
357.1 KB
такое интервью С.П.Новикова пусть здесь еще будет
О, «Математические этюды» выложили подборку про огибающую:
общее описание со ссылками, статьи в «Квантике» (классные!), и картинки ко всему этому (красивые!).
общее описание со ссылками, статьи в «Квантике» (классные!), и картинки ко всему этому (красивые!).
Математические байки
Photo
Вдогонку к огибающим — я очень люблю сюжет про окружности, соприкасающиеся кривой в разных её точках (который когда-то узнал от Этьена Жиса). В отличие от касательных, которые, если их провести в близких точках кривой, будут пересекаться — соприкасающиеся окружности оказываются вложенными друг в друга! (Пока мы не пройдём через вершину кривой — локальный минимум или максимум кривизны.)
А кривая (опять же, вне вершин) лежит от каждой соприкасающейся окружности по разные стороны до и после прохода через точку касания, так что она всех их «касаясь, пересекает».
Вот эта картинка из их статьи E. Ghys, S. Tabachnikov, V. Timorin, Osculating curves: around the Tait-Kneser theorem, Math. Intelligencer 35 (2013), http://perso.ens-lyon.fr/ghys/articles/osculatingcurves.pdf , на которой нарисованы соприкасающиеся окружности к спирали. Только сама спираль не нарисована — мы её просто видим, как их область сгущения!
А кривая (опять же, вне вершин) лежит от каждой соприкасающейся окружности по разные стороны до и после прохода через точку касания, так что она всех их «касаясь, пересекает».
Вот эта картинка из их статьи E. Ghys, S. Tabachnikov, V. Timorin, Osculating curves: around the Tait-Kneser theorem, Math. Intelligencer 35 (2013), http://perso.ens-lyon.fr/ghys/articles/osculatingcurves.pdf , на которой нарисованы соприкасающиеся окружности к спирали. Только сама спираль не нарисована — мы её просто видим, как их область сгущения!
Forwarded from Непрерывное математическое образование
http://www.mathnet.ru/present135
к д.р. В.И.Арнольда — вот, например, видеозаписи его рассказов про квадратичные иррациональности и цепные дроби
к д.р. В.И.Арнольда — вот, например, видеозаписи его рассказов про квадратичные иррациональности и цепные дроби
Forwarded from Непрерывное математическое образование
Математические байки
http://www.mathnet.ru/present135 к д.р. В.И.Арнольда — вот, например, видеозаписи его рассказов про квадратичные иррациональности и цепные дроби
https://mccme.ru/free-books/mmmf-lectures/book.14-full.pdf
напомним также замечательную брошюру В.И.Арнольда про цепные дроби
напомним также замечательную брошюру В.И.Арнольда про цепные дроби
Forwarded from Математура: книги МЦНМО
427_m-viarnold-80.pdf
118.3 KB
В честь дня рождения В.И.Арнольда (1937-2010) публикуем воспоминания А.М.Вершика из сборника "В.И.Арнольд. К восьмидесятилетию"
Forwarded from Непрерывное математическое образование
https://zykin.mccme.ru/
в понедельник (17.06) в МИАН будет VIII конференция памяти Алексея Зыкина (13.06.1984–22.04.2017)
11:00 Денис Лысков. Обобщение операд на основе графов и производящие функции
12:20 Олег Демченко. Формальные группы над p-адическими кольцами целых
14:30 Константин Шрамов. Бирациональная геометрия поверхностей дель Пеццо
15:50 Сергей Горчинский. О работах Алексея Зыкина
в понедельник (17.06) в МИАН будет VIII конференция памяти Алексея Зыкина (13.06.1984–22.04.2017)
11:00 Денис Лысков. Обобщение операд на основе графов и производящие функции
12:20 Олег Демченко. Формальные группы над p-адическими кольцами целых
14:30 Константин Шрамов. Бирациональная геометрия поверхностей дель Пеццо
15:50 Сергей Горчинский. О работах Алексея Зыкина