Математические байки
Давайте теперь вернёмся к модифицированной задаче четырёх красок. Что будет, если каждая страна сообщает свой набор из k красок — иными словами, что можно сказать про choice number для всевозможных плоских графов? Эрдёш, Рубин и Тэйлор всё в той же работе…
Да, рассуждение Томассена — то, что плоские графы являются 5-выбираемыми — удивительно короткое.
Давайте предположим, что на плоскости нарисован граф, причём все его внутренние грани — треугольники (ясно, что от того, что мы проведём дополнительные рёбра, появятся только дополнительные условия).
Пусть его внешний цикл — v_1 v_2 … v_p ; более того, пусть:
- вершинам v_1 и v_2 предписаны конкретные несовпадающие цвета (пусть это 1 и 2 соответственно);
- всем остальным вершинам внешнего цикла — списки из (хотя бы) трёх цветов;
- ну и вершинам внутри — списки из 5 цветов.
Оказывается, у такого графа всегда существует правильная предписанная раскраска!
(Утверждение более сильное, чем нам нужно — но зато его проще доказывать по индукции.)
Набросок доказательства — мы будем доказывать по индукции по количеству вершин в графе. Если во внешнем цикле есть хотя бы одна «диагональ» — т. е. ребро v_a v_b, соединяющее внутри области две его вершины — то можно по нему разбить граф на две части. Сначала раскрасить ту, на границе которой есть ребро v_1 v_2. Получить раскраску для вершин v_a и v_b, и раскрасить вторую часть.
Если же такой диагонали нет (что, собственно, есть основной случай), то давайте возьмём вершину v_p — соседнюю с v_1 с другой стороны. Для неё формально есть 3 разрешённых цвета — так что хотя бы два из них отличны от цвета 1, который сопоставили вершине v_1. Выберем два таких цвета, x и y.
Теперь — выкинем вершину v_p. Какие-то из внутренних вершин графа тогда станут граничными — пусть это u_1,…,u_r. Из разрешённых им цветов (их было 5) выкинем оба x и y — у каждой из них останется хотя бы 3 цвета; так что можно применить предположение индукции и правильно раскрасить получившийся граф. Остаётся дораскрасить выкинутую вершину v_p — а единственный возможный конфликт, который остался, это ребро v_{p-1} v_p. Ну так раскрасим v_p в тот из цветов x и y, в который не окрашена вершина v_{p-1}. Ура!
Как пишет Томассен,
«The proof is probably the simplest proof of the 5-color theorem for planar graphs.»
Давайте предположим, что на плоскости нарисован граф, причём все его внутренние грани — треугольники (ясно, что от того, что мы проведём дополнительные рёбра, появятся только дополнительные условия).
Пусть его внешний цикл — v_1 v_2 … v_p ; более того, пусть:
- вершинам v_1 и v_2 предписаны конкретные несовпадающие цвета (пусть это 1 и 2 соответственно);
- всем остальным вершинам внешнего цикла — списки из (хотя бы) трёх цветов;
- ну и вершинам внутри — списки из 5 цветов.
Оказывается, у такого графа всегда существует правильная предписанная раскраска!
(Утверждение более сильное, чем нам нужно — но зато его проще доказывать по индукции.)
Набросок доказательства — мы будем доказывать по индукции по количеству вершин в графе. Если во внешнем цикле есть хотя бы одна «диагональ» — т. е. ребро v_a v_b, соединяющее внутри области две его вершины — то можно по нему разбить граф на две части. Сначала раскрасить ту, на границе которой есть ребро v_1 v_2. Получить раскраску для вершин v_a и v_b, и раскрасить вторую часть.
Если же такой диагонали нет (что, собственно, есть основной случай), то давайте возьмём вершину v_p — соседнюю с v_1 с другой стороны. Для неё формально есть 3 разрешённых цвета — так что хотя бы два из них отличны от цвета 1, который сопоставили вершине v_1. Выберем два таких цвета, x и y.
Теперь — выкинем вершину v_p. Какие-то из внутренних вершин графа тогда станут граничными — пусть это u_1,…,u_r. Из разрешённых им цветов (их было 5) выкинем оба x и y — у каждой из них останется хотя бы 3 цвета; так что можно применить предположение индукции и правильно раскрасить получившийся граф. Остаётся дораскрасить выкинутую вершину v_p — а единственный возможный конфликт, который остался, это ребро v_{p-1} v_p. Ну так раскрасим v_p в тот из цветов x и y, в который не окрашена вершина v_{p-1}. Ура!
Как пишет Томассен,
«The proof is probably the simplest proof of the 5-color theorem for planar graphs.»
Forwarded from Непрерывное математическое образование
задача Ф.Петрова с ВсОШ-2007: доказать, что цикл длины 100 является списочно раскрашиваемым в 2 цвета — или, другими словами,
если каждой вершине 100-угольника написано по два различных числа, то можно так вычеркнуть по одному числу в каждой вершине, чтобы оставшиеся числа в каждых двух соседних вершинах были различными
доказать это можно так
рассмотрим многочлен
P:=(x1-x2)(x2-x3)(x3-x4)…(x100-x1)
мы хотим доказать, что если для каждой переменной есть два разрешенных варианта, то для какого-то из выборов P в соответствующей точке не равен нулю
а это следует из того, что коэффициент при мономе x1 x2 … x100 ненулевой
(
действительно, пусть для переменной x1 разрешены значения a и b — тогда перейдем от многочлена P(x1,…) к многочлену P(b,…)-P(a,…); потом сделаем то же по следующей переменной и т.д.
если для каждого из выборов значение P нулевое, то мы в итоге получим 0
с другой стороны, эта операция аддитивная, на мономе x1 x2 … x100 она ненулевая, а на всех остальных мономах из P нулевая — так как все они имеют нулевую степень хотя бы по одной переменной
противоречие
)
доказанное в скобках утверждение — частный случай “комбинаторной теоремы о нулях” и
если каждой вершине 100-угольника написано по два различных числа, то можно так вычеркнуть по одному числу в каждой вершине, чтобы оставшиеся числа в каждых двух соседних вершинах были различными
доказать это можно так
рассмотрим многочлен
P:=(x1-x2)(x2-x3)(x3-x4)…(x100-x1)
мы хотим доказать, что если для каждой переменной есть два разрешенных варианта, то для какого-то из выборов P в соответствующей точке не равен нулю
а это следует из того, что коэффициент при мономе x1 x2 … x100 ненулевой
(
действительно, пусть для переменной x1 разрешены значения a и b — тогда перейдем от многочлена P(x1,…) к многочлену P(b,…)-P(a,…); потом сделаем то же по следующей переменной и т.д.
если для каждого из выборов значение P нулевое, то мы в итоге получим 0
с другой стороны, эта операция аддитивная, на мономе x1 x2 … x100 она ненулевая, а на всех остальных мономах из P нулевая — так как все они имеют нулевую степень хотя бы по одной переменной
противоречие
)
доказанное в скобках утверждение — частный случай “комбинаторной теоремы о нулях” и
Telegram
Непрерывное математическое образование
Пусть карту — или посто граф — можно раскрасить в N цветов (так, что соседние вершины имеют разные цвета).
А если для каждой вершины зафиксирован свой набор из N разрешенных цветов, получится ли выбрать из них правильную раскраску? На первый взгляд может…
А если для каждой вершины зафиксирован свой набор из N разрешенных цветов, получится ли выбрать из них правильную раскраску? На первый взгляд может…
Forwarded from Непрерывное математическое образование
на странице https://www.mathnet.ru/present12021 и далее по ссылкам
можно послушать рассказы Ф.Петрова на ЛШСМ-2015 про полиномиальный метод
в т.ч. с применениями и к упоминавшимся чуть выше списочным раскраскам, и к аддитивной комбинаторике, и к тождествам с q-биноимальным коэффициентам…
можно послушать рассказы Ф.Петрова на ЛШСМ-2015 про полиномиальный метод
в т.ч. с применениями и к упоминавшимся чуть выше списочным раскраскам, и к аддитивной комбинаторике, и к тождествам с q-биноимальным коэффициентам…
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
напомним также замечательную брошюру В.И.Арнольда про цепные дроби
напомним также замечательную брошюру В.И.Арнольда про цепные дроби