Математические байки
Следствие/упражнение. Пусть A=B, т.е. есть такая игра D, что A+D=0 и B+D=0. Тогда для любой игры D’, такой, что A+D’=0, выполнено B+D’=0. Решение 1. Достаточно рассмотреть сумму A+B+D+D’ и по-разному сгруппировать слагаемые. Решение 2. Применить теорему…
Итак, мы увидели, что ним с несколькими кучками камней эквивалентен ниму с одной кучкой из правильно выбранного количества (XOR-а) камней. А случайно ли, что у нас так получилось? Оказывается, нет — существование такой эквивалентности это общее утверждение.
Теорема Шпрага-Гранди. Для любой равноправной игры существует эквивалентная ей игра в ним с одной кучкой (правильно выбранного начального количества) камней.
Замечание. Если это количество камней нулевое — то в игре выигрывает второй игрок, если нет — то начинающий.
Но прежде, чем доказывать эту теорему — давайте посмотрим с этой точки зрения на нахождение проигрышных позиций в ниме с тремя кучками камней. В каждом столбце есть проигрышная позиция — и то, на каком она уровне, как раз и указывает нам, сколько камней нужно взять в третьей кучке, чтобы она равнялась сумме игр-первой и второй кучек (потому что тогда всё в целом даёт нулевую игру, a.k.a. проигрышную позицию).
Теорема Шпрага-Гранди. Для любой равноправной игры существует эквивалентная ей игра в ним с одной кучкой (правильно выбранного начального количества) камней.
Замечание. Если это количество камней нулевое — то в игре выигрывает второй игрок, если нет — то начинающий.
Но прежде, чем доказывать эту теорему — давайте посмотрим с этой точки зрения на нахождение проигрышных позиций в ниме с тремя кучками камней. В каждом столбце есть проигрышная позиция — и то, на каком она уровне, как раз и указывает нам, сколько камней нужно взять в третьей кучке, чтобы она равнялась сумме игр-первой и второй кучек (потому что тогда всё в целом даёт нулевую игру, a.k.a. проигрышную позицию).
А как эта проигрышная позиция находится? В столбце будут выигрышные позиции, приходящие из проигрышных клеток в столбцах ниже (в смысле плоскости — если хотите, севернее) или левее (западнее). И первая из клеток, которая таким образом « выбита » не будет, и будет проигрышной.
Если заполнять таблицу «какой игре *n равняется сумма *k+*m» (как мы уже знаем, на самом деле это таблица значений XOR двоичных записей), то правило выше превращается в правило наименьшего исключенного:
в клетке (k,m) стоит первое из неотрицательных целых чисел, которое не появляется ни в одной из клеток (k’,m’), которые из неё можно получить за один ход.
Если заполнять таблицу «какой игре *n равняется сумма *k+*m» (как мы уже знаем, на самом деле это таблица значений XOR двоичных записей), то правило выше превращается в правило наименьшего исключенного:
в клетке (k,m) стоит первое из неотрицательных целых чисел, которое не появляется ни в одной из клеток (k’,m’), которые из неё можно получить за один ход.
Так вот — на самом деле, то, что мы тут исследовали ним на двух кучках, совершенно неважно! То же самое правило наименьшего исключенного (mex-rule) строит соответствующее *n (ним на одной кучке из n камней) и для любой равноправной игры. А именно: пусть у нас есть какая-то равноправная игра, будем сопоставлять ей ним-игру *n по индукции. Если уже построены сопоставления для всего, что можно из данной позиции получить за один ход, и это *n_1,…,*n_m, то самой позиции сопоставляем *n, где n — наименьшее неотрицательное целое число, не встречающееся среди n_1,…,n_m.
Доказательство теоремы Шпрага-Гранди. Построить-то соответствующие ним-игры мы построили, но остаётся проверить, что построенная игра действительно равна исходной — то есть что их сумма нулевая. А для этого в их сумме мы предъявим выигрышную стратегию для второго игрока.
Пусть из исходной позиции A нашей игры можно пойти в A_1,…,A_m — которым соответствуют ним-игры *n_1,…,*n_m, и мы уже знаем, что
A_j + *n_j =0.
Мы взяли n = mex(n_1,…,n_m), и рассматриваем сумму A+*n. Докажем, что в ней выигрывает второй игрок.
Действительно, что может сделать первый игрок? Он может сделать ход со стороны A, переведя её в одну из A_j с n_j<n. Тогда мы отвечаем, оставляя *n_j из n камней в *n — и тем самым отдаём противнику позицию A_j + *n_j, проигрышную по предположению.
Он может сделать ход со стороны ним-кучки, перейдя от *n к какому-то *n’. Но раз n было наименьшим исключённым из n_1,…,n_m, значит, найдётся j такое, что n’=n_j. И тут уже мы отвечаем, переходя из A в A_j и опять приводя игру в проигрышную позицию A_j + *n_j.
Наконец, первый игрок мог сделать ход со стороны A, переведя её в одну из A_j, но с n_j>n. Тогда мы ответим ходом из A_j. А именно — n<n_j, поэтому найдётся позиция A_j’, куда мы из A_j можем пойти, которой сопоставлена *n (потому что n_j — наименьшее исключённое). Вот туда мы и пойдём — приведя игру к
A_j’+*n=0.
На самом деле, разбора вариантов n_j<n и n_j>n можно было и не делать, ограничившись замечанием, что *A_j + *n = *n_j + *n; в игре в правой части очевидно выигрывает начинающий (т.е. мы — ход сейчас наш), а у нас есть теорема, что замена игры на равную не изменяет победителя. Но так у нас есть не только теорема, но и явная конструкция стратегии.
Доказательство теоремы Шпрага-Гранди. Построить-то соответствующие ним-игры мы построили, но остаётся проверить, что построенная игра действительно равна исходной — то есть что их сумма нулевая. А для этого в их сумме мы предъявим выигрышную стратегию для второго игрока.
Пусть из исходной позиции A нашей игры можно пойти в A_1,…,A_m — которым соответствуют ним-игры *n_1,…,*n_m, и мы уже знаем, что
A_j + *n_j =0.
Мы взяли n = mex(n_1,…,n_m), и рассматриваем сумму A+*n. Докажем, что в ней выигрывает второй игрок.
Действительно, что может сделать первый игрок? Он может сделать ход со стороны A, переведя её в одну из A_j с n_j<n. Тогда мы отвечаем, оставляя *n_j из n камней в *n — и тем самым отдаём противнику позицию A_j + *n_j, проигрышную по предположению.
Он может сделать ход со стороны ним-кучки, перейдя от *n к какому-то *n’. Но раз n было наименьшим исключённым из n_1,…,n_m, значит, найдётся j такое, что n’=n_j. И тут уже мы отвечаем, переходя из A в A_j и опять приводя игру в проигрышную позицию A_j + *n_j.
Наконец, первый игрок мог сделать ход со стороны A, переведя её в одну из A_j, но с n_j>n. Тогда мы ответим ходом из A_j. А именно — n<n_j, поэтому найдётся позиция A_j’, куда мы из A_j можем пойти, которой сопоставлена *n (потому что n_j — наименьшее исключённое). Вот туда мы и пойдём — приведя игру к
A_j’+*n=0.
На самом деле, разбора вариантов n_j<n и n_j>n можно было и не делать, ограничившись замечанием, что *A_j + *n = *n_j + *n; в игре в правой части очевидно выигрывает начинающий (т.е. мы — ход сейчас наш), а у нас есть теорема, что замена игры на равную не изменяет победителя. Но так у нас есть не только теорема, но и явная конструкция стратегии.
Давайте посмотрим на один пример применения этой науки.
Есть такая стандартная кружковская задача:
Решение:при n>2 выигрывает второй игрок. После первого хода первого игрока второй отрывает лепестки строго напротив — разбивая окружность лепестков на два одинаковых участка, и остаётся применить симметричную стратегию.
Это, конечно, решает исходную задачу. Но представим себе, что нам досталась позиция после нескольких ходов. Например, пусть нам достался набор лепестков, образующий отрезки длиной 4, 5, 9 и 20. Кто выигрывает при правильной игре? А если (допустим, ромашка была очень большая) нам достались отрезки длиной 12, 70 и 180?
Попытка исследовать эти игры «от начальной позиции», исследуя дерево вариантов сверху, приводит к не очень подъёмному перебору. (Навскидку, первый вариант вручную и без оптимизации уже неподъёмный, но ещё должен перебираться на компьютере; а второй даже и компьютер не потянет.)
А вот применение конструкции из теоремы Шпрага-Гранди позволяет справиться даже и вручную! А именно — мы хотим для любого n узнать, какому числу камней a_n соответствует игра для одного отрезка из n последовательных лепестков. За один ход мы можем получить из него два отрезка длин s и t, где либо s+t=n-1, либо s+t=n-2.
(Если отрываем лепестки с края, то кто-нибудь из s и t будет нулём.)
Двум отрезкам соответствует сумма игр, и ним-сумма (a.k.a. XOR) соответствующих количеств камней. Соответственно, получаем рекуррентное соотношение
a_n = mex ( XOR(a_s,a_t) | s+t = n-1 или s+t = n-2 ).
Во-первых, при необходимости его и до 180 можно дотащить «вручную». Да, априори это могло бы быть оочень занудно, но это явно посильная задача даже без компьютера.
Во-вторых: давайте посчитаем первые несколько членов последовательности.
n=0 -> пустая игра, ходов нет,
a_0=0.
n=1 -> единственный ход приводит к 0, значит,
a_1=1.
n=2 -> можно получить либо пустую позицию, либо один лепесток, значит,
a_2=mex(0,1) = 2.
n=3 -> можно получить конфигурации (1), (2), (1,1), которым соответствуют ним-значения 1, 2 и 0 соответственно. Значит,
a_3=mex(0,1,2)=3.
n=4 -> можно получить конфигурации (2), (1,1), (3), (1,2), которым соответствуют ним-значения 2, 0, 3 и 3 соответственно. Значит,
a_4= mex(0,2,3)=1.
n=5 -> можно получить конфигурации (3), (2,1), (4), (1,3), (2,2) которым соответствуют ним-значения 3, 3, 1, 2 и 0 соответственно. Значит,
a_5= mex(0,1,2,3)=4.
После чего можно ввести начало найденной последовательности — 0,1,2,3,1,4 — в OEIS, онлайн-энциклопедию целочисленных последовательностей (коллеги цитировали текст к 50-летию энциклопедии — начинавшейся ещё не как онлайн!).
И первой ссылкой этот поиск выдаст последовательность A002186 — после чего, посмотрев на то, что такое упоминаемая там game of Kayles, становится понятно, что это буквально то, что нам нужно. И кстати — начиная с n=71 последовательность становится периодичной с периодом 12.
(For the record: подумав, что я хочу привести тут пример с игрой с ромашкой, я ещё не знал названия Kayles — выше описан буквально тот путь, которым я прошёл.)
Если возвращаться именно к нашим позициям из примеров выше — наборам (4,5,9,20) и (12,70,180) — то первому из них соответствует ним-сумма 1, 4, 4 и 1, и выигрывает второй игрок. А второму — ним-сумма 4, 4 и 6, так что выигрывает первый. Один из выигрышных ходов — превратить третий отрезок в 180 лепестков с ним-значением 6 во что-то с нулевым ним-значением, вырвав два лепестка посередине: мы получим позицию (12,70,89,89) с нулевым суммарным ним-значением.
Есть такая стандартная кружковская задача:
Есть ромашка с n лепестками, и двое по очереди отрывают либо один лепесток, либо два соседних. Кто не может сделать ход — проиграл. Кто выигрывает при правильной игре?
Решение:
Это, конечно, решает исходную задачу. Но представим себе, что нам досталась позиция после нескольких ходов. Например, пусть нам достался набор лепестков, образующий отрезки длиной 4, 5, 9 и 20. Кто выигрывает при правильной игре? А если (допустим, ромашка была очень большая) нам достались отрезки длиной 12, 70 и 180?
Попытка исследовать эти игры «от начальной позиции», исследуя дерево вариантов сверху, приводит к не очень подъёмному перебору. (Навскидку, первый вариант вручную и без оптимизации уже неподъёмный, но ещё должен перебираться на компьютере; а второй даже и компьютер не потянет.)
А вот применение конструкции из теоремы Шпрага-Гранди позволяет справиться даже и вручную! А именно — мы хотим для любого n узнать, какому числу камней a_n соответствует игра для одного отрезка из n последовательных лепестков. За один ход мы можем получить из него два отрезка длин s и t, где либо s+t=n-1, либо s+t=n-2.
(Если отрываем лепестки с края, то кто-нибудь из s и t будет нулём.)
Двум отрезкам соответствует сумма игр, и ним-сумма (a.k.a. XOR) соответствующих количеств камней. Соответственно, получаем рекуррентное соотношение
a_n = mex ( XOR(a_s,a_t) | s+t = n-1 или s+t = n-2 ).
Во-первых, при необходимости его и до 180 можно дотащить «вручную». Да, априори это могло бы быть оочень занудно, но это явно посильная задача даже без компьютера.
Во-вторых: давайте посчитаем первые несколько членов последовательности.
n=0 -> пустая игра, ходов нет,
a_0=0.
n=1 -> единственный ход приводит к 0, значит,
a_1=1.
n=2 -> можно получить либо пустую позицию, либо один лепесток, значит,
a_2=mex(0,1) = 2.
n=3 -> можно получить конфигурации (1), (2), (1,1), которым соответствуют ним-значения 1, 2 и 0 соответственно. Значит,
a_3=mex(0,1,2)=3.
n=4 -> можно получить конфигурации (2), (1,1), (3), (1,2), которым соответствуют ним-значения 2, 0, 3 и 3 соответственно. Значит,
a_4= mex(0,2,3)=1.
n=5 -> можно получить конфигурации (3), (2,1), (4), (1,3), (2,2) которым соответствуют ним-значения 3, 3, 1, 2 и 0 соответственно. Значит,
a_5= mex(0,1,2,3)=4.
После чего можно ввести начало найденной последовательности — 0,1,2,3,1,4 — в OEIS, онлайн-энциклопедию целочисленных последовательностей (коллеги цитировали текст к 50-летию энциклопедии — начинавшейся ещё не как онлайн!).
И первой ссылкой этот поиск выдаст последовательность A002186 — после чего, посмотрев на то, что такое упоминаемая там game of Kayles, становится понятно, что это буквально то, что нам нужно. И кстати — начиная с n=71 последовательность становится периодичной с периодом 12.
(For the record: подумав, что я хочу привести тут пример с игрой с ромашкой, я ещё не знал названия Kayles — выше описан буквально тот путь, которым я прошёл.)
Если возвращаться именно к нашим позициям из примеров выше — наборам (4,5,9,20) и (12,70,180) — то первому из них соответствует ним-сумма 1, 4, 4 и 1, и выигрывает второй игрок. А второму — ним-сумма 4, 4 и 6, так что выигрывает первый. Один из выигрышных ходов — превратить третий отрезок в 180 лепестков с ним-значением 6 во что-то с нулевым ним-значением, вырвав два лепестка посередине: мы получим позицию (12,70,89,89) с нулевым суммарным ним-значением.
Telegram
Непрерывное математическое образование
https://arxiv.org/abs/2301.03149
"A Handbook of Integer Sequences" Fifty Years Later (N. J. A. Sloane)
Until 1973 there was no database of integer sequences. Someone coming across the sequence 1, 2, 4, 9, 21, 51, 127,... would have had no way of discovering…
"A Handbook of Integer Sequences" Fifty Years Later (N. J. A. Sloane)
Until 1973 there was no database of integer sequences. Someone coming across the sequence 1, 2, 4, 9, 21, 51, 127,... would have had no way of discovering…
Математические байки
Спасибо коллегам, приславшим два других решения: И.П.: «Привет. Насчёт фазы луны -- я когда прочитал вопрос даже не понял что может быть другой ответ чем этот: В еврейском календаре Новый Год (Рош ха Шана) начинается в с новой луны. Симхат Тора - 23й день…
Когда бывают самые сильные приливы и отливы?
Final Results
29%
В полнолуние самые сильные, в новолуние самые слабые
23%
В полнолуние самые слабые, в новолуние самые сильные
41%
В полнолуние и в новолуние самые сильные, в первую и в третью четверть самые слабые
6%
В полнолуние и в новолуние самые слабые, в первую и в третью четверть самые сильные
Forwarded from Непрерывное математическое образование
https://mccme.ru/free-books/
Дед Мороз напоминает про страницу, на которой бесплатно доступны файлы множества книг (в основном издательства МЦНМО)
брошюры библиотеки «Математическое просвещение» и Летней школы «Современная математика», доклады семинара «Глобус» и материалы выездного семинара учителей, книги Арнольда и Гельфанда, Прасолова и Шеня и многое другое.
новогодние каникулы — как раз хорошая возможность спокойно почитать
Дед Мороз напоминает про страницу, на которой бесплатно доступны файлы множества книг (в основном издательства МЦНМО)
брошюры библиотеки «Математическое просвещение» и Летней школы «Современная математика», доклады семинара «Глобус» и материалы выездного семинара учителей, книги Арнольда и Гельфанда, Прасолова и Шеня и многое другое.
новогодние каникулы — как раз хорошая возможность спокойно почитать
Нерегулярная рубрика «рабочие картинки» (они красивые, хочется поделиться): часть поверхности Маркова
x^2+y^2+z^2-xyz = D
и некоторые слоения на ней.
x^2+y^2+z^2-xyz = D
и некоторые слоения на ней.
Женя Кац напомнила про видео — мыльные пузыри в сильный мороз можно заморозить(!). Я вот вживую такого никогда не видел…
YouTube
Морозные узоры на мыльных пузырях. Зимние эксперименты
Ирина @irina_magic.lab вдохновила нас на проведение серии экспериментов с мыльными пузырями. При морозе в минус 10-15 на плёнке мыльного пузыря очень быстро появляются морозные узоры!
Делаем самодельный раствор из Fairy, глицерина и дистиллированной воды.…
Делаем самодельный раствор из Fairy, глицерина и дистиллированной воды.…
Forwarded from Непрерывное математическое образование
https://mccme.ru/nir/seminar/
в четверг (11.01) продолжится семинар учителей математики:
А.Д.Блинков будет рассказывать про книжку «Площади без формул», которая скоро выйдет в серии «Школьные математические кружки»
как обычно: 19:00, столовая МЦНМО, приглашаются все желающие
в четверг (11.01) продолжится семинар учителей математики:
А.Д.Блинков будет рассказывать про книжку «Площади без формул», которая скоро выйдет в серии «Школьные математические кружки»
как обычно: 19:00, столовая МЦНМО, приглашаются все желающие
Forwarded from tropical saint petersburg
St. Petersburg mathematicians and their discoveries
Книжка про математиков Петербурга и их открытия — завершена.
Теперь напечатаем малым тиражом и разошлём авторам и всем причастным.
Кому интересно иметь её в бумажном виде — печатайте сами себе в каком-нибудь самиздате (вроде есть сайты, куда можно pdf загрузить, и потом в мягком переплёте получить по почте).
Книжка про математиков Петербурга и их открытия — завершена.
Теперь напечатаем малым тиражом и разошлём авторам и всем причастным.
Кому интересно иметь её в бумажном виде — печатайте сами себе в каком-нибудь самиздате (вроде есть сайты, куда можно pdf загрузить, и потом в мягком переплёте получить по почте).
Три дня назад на небе можно было увидеть аккуратную половинку Луны (почти точно в фазе первой четверти) — и очень яркую «звёздочку» рядом. Первое, что приходит в голову при виде чего-то столь яркого, это Венера и Юпитер. (Вообще, Марс иногда бывает очень ярким, но не так часто; есть ещё Сириус, но давайте мы его временно заметём под ковёр).
Так вот: допустим, мы ограничили выбор Венерой и Юпитером. Интересно, что написанного выше достаточно, чтобы один из этих вариантов исключить! Как думаете, какой?
(image credit: NASA, вырезано из What’s Up video)
Так вот: допустим, мы ограничили выбор Венерой и Юпитером. Интересно, что написанного выше достаточно, чтобы один из этих вариантов исключить! Как думаете, какой?
(image credit: NASA, вырезано из What’s Up video)
Какой именно вариант можно искючить?
Final Results
71%
Можно исключить Венеру, рядом с Луной был Юпитер.
29%
Можно исключить Юпитер, рядом с Луной была Венера.
Математические байки
Какой именно вариант можно искючить?
Ответ:
Луна в первой четверти означает, что направление на неё почти под прямым углом к направлению на Солнце. А Венера — внутренняя планета, так что на 90 градусов выйти не может.
Если говорить более аккуратно, то радиус орбиты у неё — чуть больше 0.7 радиуса орбиты Земли (точнее, большая полуось 0.723 а.е., но я наизусть только 0.7 помню — одну цифру помнить проще 🙂 ; ну и на уровне прикидки в уме эллиптичностью пренебрегаем, всё-таки там эксцентриситеты порядка процента)
Значит, Венера не может быть от Солнца на угловом расстоянии, большем, чем (примерно) arcsin 0.7.
Ну а sqrt{2}/2=0.707..., так что этот угол это с отличной точностью 45 градусов.
Итак, максимальный угол между направлениями на Венеру и Солнце это чуть больше, чем 45 градусов (на самом деле 47, но это я уже потом посмотрел — а тут прикидывал на ходу, и кажется, неплохо получилось).
Итого:
*) угол Солнце-Земля-Луна в этот момент примерно равен 90 градусам (потому что от Луны освещена половина),
*) угол Солнце-Земля-Венера никогда не больше 47 градусов.
Значит, в момент наблюдения угол Венера-Земля-Луна был не меньше 43 градусов. А не единицы градусов, которые « рядом » на небе! Так что Венеру исключаем.
Луна в первой четверти означает, что направление на неё почти под прямым углом к направлению на Солнце. А Венера — внутренняя планета, так что на 90 градусов выйти не может.
Если говорить более аккуратно, то радиус орбиты у неё — чуть больше 0.7 радиуса орбиты Земли (точнее, большая полуось 0.723 а.е., но я наизусть только 0.7 помню — одну цифру помнить проще 🙂 ; ну и на уровне прикидки в уме эллиптичностью пренебрегаем, всё-таки там эксцентриситеты порядка процента)
Значит, Венера не может быть от Солнца на угловом расстоянии, большем, чем (примерно) arcsin 0.7.
Ну а sqrt{2}/2=0.707..., так что этот угол это с отличной точностью 45 градусов.
Итак, максимальный угол между направлениями на Венеру и Солнце это чуть больше, чем 45 градусов (на самом деле 47, но это я уже потом посмотрел — а тут прикидывал на ходу, и кажется, неплохо получилось).
Итого:
*) угол Солнце-Земля-Луна в этот момент примерно равен 90 градусам (потому что от Луны освещена половина),
*) угол Солнце-Земля-Венера никогда не больше 47 градусов.
Значит, в момент наблюдения угол Венера-Земля-Луна был не меньше 43 градусов. А не единицы градусов, которые « рядом » на небе! Так что Венеру исключаем.
Forwarded from Математические этюды