Вариант игры Вайтхоффа, определённый последовательностью Хофстадтера G

Основная информация

• ID статьи: 2510.11767
• Название: A Variant of Wythoff's Game Defined by Hofstadter's G-Sequence
• Авторы: Kahori Komaki, Ryohei Miyadera, Aoi Murakami
• Классификация: math.CO (комбинаторика)
• Дата публикации: 13 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.11767

Аннотация

В данной работе исследуется вариант классической игры Вайтхоффа. Классическая игра Вайтхоффа включает две кучи камней, два игрока по очереди удаляют камни из одной или обеих куч, при одновременном удалении из обеих куч необходимо удалять одинаковое количество. Игрок, удаливший последний камень или последние несколько камней, побеждает. Эквивалентно, это можно рассматривать как перемещение шахматной королевы на большой доске, где каждый игрок может перемещать королеву на любое количество клеток вертикально, горизонтально или диагонально в направлении левого верхнего угла (0,0).

В варианте, предложенном в данной работе, множество терминальных позиций расширено до {(0,0), (1,0), (0,1), (1,1), (2,0), (0,2)}. P-позиции этого варианта описываются через P-позиции игры Вайтхоффа и последовательность Хофстадтера G. Вариант обладает двумя значительными свойствами: для позиций (x,y) с x≥8 или y≥8 число Гранди позиции (x,y) в этом варианте равно 1 тогда и только тогда, когда (x,y) является P-позицией игры Вайтхоффа; для позиций (x,y) с x≥8 или y≥8 позиция (x,y) является P-позицией в версии misère этого варианта тогда и только тогда, когда (x,y) является P-позицией игры Вайтхоффа.

Научный контекст и мотивация

Определение проблемы

Данное исследование направлено на анализ и решение нового варианта классической игры Вайтхоффа, в котором условие терминации расширено с единственной позиции (0,0) на множество, содержащее 6 позиций. Это расширение, хотя и кажется простым, существенно изменяет сложность и стратегическую структуру игры.

Значимость

1. Теоретическое значение: Игра Вайтхоффа является классической задачей комбинаторной теории игр, её P-позиции тесно связаны с золотым сечением φ=(1+√5)/2. Исследование её вариантов способствует глубокому пониманию структурных свойств комбинаторных игр.
2. Математические связи: Данное исследование устанавливает новые связи между последовательностью Хофстадтера G и теорией комбинаторных игр, что редко рассматривалось в предыдущих работах.
3. Методологические инновации: Введение функции g(n) и последовательности Хофстадтера G предоставляет новые математические инструменты для анализа комбинаторных игр со сложными условиями терминации.

Ограничения существующих методов

P-позиции классической игры Вайтхоффа имеют явное замкнутое выражение, но когда условие терминации становится множеством нескольких позиций, традиционные методы анализа трудно применяются непосредственно. Существующая теория комбинаторных игр не содержит систематического подхода к обработке таких расширенных условий терминации.

Основные вклады

1. Определение нового варианта игры: Расширение терминальных позиций игры Вайтхоффа с единственной точки (0,0) на множество {(x,y): x+y≤2}
2. Полная характеризация P-позиций: Введение функции g(n) и последовательности Хофстадтера G позволило получить точные формулы для P-позиций этого варианта
3. Открытие двух важных свойств:
   • Для позиций с x≥8 или y≥8 число Гранди варианта равно 1 тогда и только тогда, когда позиция является P-позицией исходной игры Вайтхоффа
   • Для позиций с x≥8 или y≥8 позиция является P-позицией версии misère тогда и только тогда, когда она является P-позицией исходной игры Вайтхоффа
4. Установление связи с последовательностью Хофстадтера G: Доказано, что функция g(n) может быть определена рекурсивно через последовательность Хофстадтера G

Подробное описание методов

Определение задачи

Входные данные: Позиция игры (x,y), где x,y∈ℤ≥0 Выходные данные: Определение, является ли позиция P-позицией (позиция победы предыдущего игрока) или N-позицией (позиция победы следующего игрока) Ограничения: Правила перемещения совпадают с классической игрой Вайтхоффа, но терминальное множество равно {(x,y): x+y≤2}

Основная математическая структура

1. Определение функции g(n)

g(0) = 1, g(1) = 0
g(n) = {
  1 - g(m)  если ⌊nφ⌋ = ⌊m(φ+1)⌋ + 1 для некоторого m∈ℤ≥0
  1         в остальных случаях
}

2. Характеризация множества P-позиций

P₁ = P₁,₁ ∪ P₁,₂ ∪ {(0,0)}, где:

• P₁,₁ = {(⌊nφ⌋ + g(n) - 1, ⌊n(φ+1)⌋ + g(n)) : n ∈ ℤ≥0}
• P₁,₂ = {(⌊n(φ+1)⌋ + g(n), ⌊nφ⌋ + g(n) - 1) : n ∈ ℤ≥0}

3. Связь с последовательностью Хофстадтера G

Для n≥2:

g(n) = {
  1 - g(h(n-1))  если h(n-2) < h(n-1)
  1              в остальных случаях
}

где h — последовательность Хофстадтера G: h(0)=0, h(n)=n-h(h(n-1))

Технические инновации

1. Техника разложения последовательности: Путём разложения натуральных чисел на нижнюю последовательность Вайтхоффа A₁={⌊nφ⌋} и верхнюю последовательность Вайтхоффа A₂={⌊n(φ+1)⌋} установлена систематическая аналитическая структура.
2. Проектирование рекурсивной функции: Конструкция функции g(n) искусно захватывает влияние расширения терминального множества на распределение P-позиций.
3. Анализ чисел Гранди: Посредством вычисления чисел Гранди установлены глубокие связи между этим вариантом и исходной игрой.

Экспериментальная установка

Методы теоретической верификации

В работе используется чистый теоретический метод доказательства, включающий следующие этапы:

1. Доказательство полноты: Доказательство того, что из любой не-P-позиции можно перейти в P-позицию
2. Доказательство согласованности: Доказательство того, что из P-позиции невозможно перейти в другую P-позицию
3. Вычислительная верификация: Полный перебор для случаев малого масштаба

Конкретный диапазон верификации

• Полный перебор всех случаев для координат позиций x,y≤7
• Для случаев x≥8 или y≥8 установлена эквивалентность с исходной игрой Вайтхоффа посредством теоретического доказательства

Результаты экспериментов

Основные теоретические результаты

Теорема 1: Полная характеризация P-позиций

Множество P₁ является множеством P-позиций для этого варианта игры, что доказано через Лемму 8 и Лемму 12:

• Лемма 8: Из позиции в P₁ невозможно перейти в другую позицию в P₁
• Лемма 12: Из любой позиции, не входящей в P₁, можно перейти в некоторую позицию в P₁

Теорема 2: Связь с исходной игрой Вайтхоффа

Для позиций (x,y) с x≥8 или y≥8:

• G₂(x,y,1)=0 в этом варианте тогда и только тогда, когда G₀(x,y)=0 в исходной игре
• Это устанавливает эквивалентность двух игр на "больших" позициях

Теорема 3: Свойства версии Misère

P-позиции версии misère (игрок, входящий в терминальное множество, проигрывает) совпадают с P-позициями суммы исходной игры и одиночной кучи камней.

Результаты верификации малого масштаба

Посредством полного перебора определены следующие множества P-позиций малого масштаба:

• Множество A: {(0,0,1), (0,1,1), (0,2,1), (1,0,1), (1,1,1), (2,0,1), (3,6,1), (6,3,1), (4,8,1), (8,4,1)}
• Множество B: {(0,3,1), (1,2,1), (2,1,1), (3,0,1), (4,4,1), (5,7,1), (7,5,1)}
• Множество C: {(0,0), (1,2), (2,1), (3,5), (5,3), (4,7), (7,4)}

Ключевые находки

1. Граничные эффекты: В диапазоне x,y≤7 распределение P-позиций существенно отличается от исходной игры Вайтхоффа
2. Асимптотическое поведение: При достаточно больших координатах поведение этого варианта сходится к исходной игре Вайтхоффа
3. Свойства последовательности: Паттерн значений функции g(n) тесно связан со свойствами роста последовательности Хофстадтера G

Связанные работы

Теория игры Вайтхоффа

Классическая игра Вайтхоффа была предложена В.А. Вайтхоффом в 1907 году, связь её P-позиций с золотым сечением является классическим результатом комбинаторной математики. Соответствующие исследования включают:

• Теорему Рэлея: установление свойств разбиения нижней и верхней последовательностей Вайтхоффа
• Исследования различных вариантов игры Вайтхоффа

Теория последовательностей Хофстадтера

Хофстадтер в работе «Gödel, Escher, Bach» определил несколько рекурсивных последовательностей, среди которых последовательность G обладает особыми теоретико-числовыми свойствами:

• Исследования рекурсивных функций Гаулта и Клинта (1988)
• Анализ сингулярных рекурсивных отношений Гранвилля и Рассона (1988)

Комбинаторная теория игр

Данная работа относится к области справедливой комбинаторной теории игр:

• Теорема Спрага-Гранди и её применения
• Методы определения P-позиций и N-позиций
• Теоретическая структура игр misère

Заключение и обсуждение

Основные выводы

1. Полное решение: Получена полная характеризация P-позиций варианта игры Вайтхоффа с расширенным терминальным множеством
2. Глубокие связи: Выявлены существенные связи между этим вариантом и последовательностью Хофстадтера G
3. Асимптотическая эквивалентность: Доказана эквивалентность этого варианта и исходной игры при больших координатах

Ограничения

1. Сложность: Определение функции g(n) относительно сложно и не столь элегантно, как замкнутое решение исходной игры Вайтхоффа
2. Вычислительная эффективность: Определение P-позиций требует вычисления последовательности Хофстадтера, что может вызвать проблемы с вычислительной сложностью
3. Обобщаемость: Остаётся неясным, может ли метод быть обобщён на другие терминальные множества

Направления будущих исследований

1. Более общие терминальные множества: Исследование вариантов игры Вайтхоффа с произвольными терминальными множествами
2. Оптимизация алгоритмов: Разработка более эффективных алгоритмов определения P-позиций
3. Другие рекурсивные последовательности: Исследование применения других известных рекурсивных последовательностей в комбинаторных играх

Глубокая оценка

Преимущества

1. Теоретическая глубина: Установлены новые связи между теорией комбинаторных игр и теорией рекурсивных последовательностей, что имеет важное теоретическое значение
2. Методологические инновации: Конструкция функции g(n) искусна и посредством рекурсивного определения захватывает сложную структуру игры
3. Полнота доказательств: Предоставлены полные математические доказательства, включая детальное обоснование многочисленных технических лемм
4. Глубокие результаты: Обнаруженное свойство асимптотической эквивалентности предоставляет новую перспективу для понимания сложных комбинаторных игр

Недостатки

1. Сложность изложения: Определение функции g(n) относительно абстрактно, что может затруднить интуитивное понимание результатов
2. Ограниченная практическая применимость: Хотя теоретически полно, практическая ценность в реальных приложениях остаётся неясной
3. Трудность обобщения: Специфичность метода может ограничить его применение к другим задачам

Влияние

1. Академическая ценность: Открывает новые направления в пересечении комбинаторной теории игр и теории рекурсивных последовательностей
2. Методологический вклад: Предоставляет новые инструменты для анализа комбинаторных игр со сложными условиями терминации
3. Теоретическая полнота: Обогащает теоретическую систему вариантов игры Вайтхоффа

Применимые сценарии

1. Теоретические исследования: Подходит для теоретических исследований в комбинаторной математике и теории игр
2. Разработка алгоритмов: Предоставляет теоретическую основу для проектирования алгоритмов оптимальной стратегии для соответствующих игр
3. Применение в обучении: Может служить отличным примером демонстрации связей между рекурсивными последовательностями и комбинаторными задачами

Библиография

1. M.H. Albert, R.J. Nowakowski, and D. Wolfe: Lessons In Play, A K Peters/CRC Press, 2007
2. D. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Penguin Books, 1980
3. W.A. Wythoff: A modification of the game of Nim, Nieuw Arch. Wiskd, 7 (1907), 199-202
4. V. Granville and J.-P. Rasson, A strange recursive relation, J. Number Theory 30 (1988), 238–241

Данная статья вносит важный теоретический вклад в область комбинаторной теории игр, предоставляя полную математическую структуру для анализа варианта игры Вайтхоффа с расширенным терминальным множеством посредством искусного применения последовательности Хофстадтера G. Хотя в аспекте практической применимости существуют определённые ограничения, теоретическая глубина и методологическая инновационность делают эту работу значительным результатом исследований в данной области.