Давайте посмотрим на один пример применения этой науки.
Есть такая стандартная кружковская задача:
Решение:при 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 Математические этюды