Игра Гранди — стратегическая математическая игра для двух игроков. Сначала существует одна куча предметов. Два игрока по очереди разделяют любую из куч на две кучи разных размеров. Игра заканчивается, когда остаются только кучи из двух или одного предметов, т.к. ни одна не может быть разделена на кучи разных размеров. Выигрывает игрок, который сделал последний ход.
Пример
Игра, которая начинается с одной кучки из 8 предметов, выигрышна для первого игрока, если он разделит исходную кучу на две из 7 и 1 предметов:
игрок 1: 8 → 7+1
Игрок 2 сейчас может сделать один из трех ходов: разбить 7 на 6 + 1, 5 + 2 или 4 + 3. В каждом из этих случаев игрок 1 может обеспечить возврат противнику куч из 4 предметов и кучи размером 2 и меньше:
игрок 2: 7+1 → 6+1+1 игрок 2: 7+1 → 5+2+1 игрок 2: 7+1 → 4+3+1
игрок 1: 6+1+1 → 4+2+1+1 игрок 1: 5+2+1 → 4+1+2+1 игрок 1: 4+3+1 → 4+2+1+1
Сейчас игрок 2 должен разделить кучу из четырех предметов на 3 + 1, игрок 1, в дальнейшем, разделит 3 на 2 + 1:
игрок 2: 4+2+1+1 → 3+1+2+1+1
игрок 1: 3+1+2+1+1 → 2+1+1+2+1+1
игрок 2 не может сделать ход и проигрывает.
Математическая теория
Игра может быть проанализирована с помощью теории Шпрага-Гранди. Для этого нужно размерам куч в игре Гранди поставить в соответствие эквивалентные размеры куч в игре Ним. Это соответствие описывается последовательностью:
Размеры куч : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
Эквивалентные размеры Ним куч : 0 0 0 1 0 2 1 0 2 1 0 2 1 3 2 1 3 2 4 3 0 ... (Шаблон:OEIS)
Используя это соответствие, стратегия для игры Ним может быть также использована и для игры Гранди. Вопрос, становится ли последовательность Ним-значений для игры Гранди периодичной, это нерешенная проблема. Элвин Берлекэмп, Джон Хортон Конвей и Ричард Гай предположили[1], что она периодична, несмотря на то, что первые 235 значений, найденные Achim Flammenkamp, этого не подтверждают.
См. также
Литература
Шаблон:Примечания
Ссылки
| Партнерские ресурсы |
|---|
| Криптовалюты |
|
|---|
| Магазины |
|
|---|
| Хостинг |
|
|---|
| Разное |
- Викиум - Онлайн-тренажер для мозга
- Like Центр - Центр поддержки и развития предпринимательства.
- Gamersbay - лучший магазин по бустингу для World of Warcraft.
- Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память.
- Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России.
- Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме.
- Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео.
- Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет
- SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона.
- «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется.
- StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.
- Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено.
- StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.
|
|---|
- ↑ E. Berlekamp, J. H. Conway, R. Guy. Winning Ways for your Mathematical Plays. Academic Press, 1982.
