The Ordered Zeckendorf Game

以下は、Ivan Bortnovskyi らによる論文「THE ORDERED ZECKENDORF GAME（順序付きゼッケンドルフ・ゲーム）」の技術的な要約です。

1. 問題の背景と定義

背景

ゼッケンドルフの定理（Zeckendorf's Theorem）は、すべての正の整数が、連続しないフィボナッチ数の和として一意に表現できることを保証するものです。これまでに「ゼッケンドルフ・ゲーム」という組み合わせゲームが研究されており、プレイヤーはフィボナッチ数の多重集合に対して「結合（Merge）」や「分割（Split）」の操作を行い、最終的にゼッケンドルフ分解に至るまで交互に手番を行います。しかし、従来のゲームでは要素の順序は関係なく（非順序集合）、Player 2 が $n > 2$ のすべての場合において支配的な勝利戦略を持つことが知られており、戦略的な深さに欠けるという課題がありました。

提案されたゲーム：順序付きゼッケンドルフ・ゲーム

本研究では、この制限を克服し、より豊かな戦略的構造を持つ新しい変種「順序付きゼッケンドルフ・ゲーム（Ordered Zeckendorf Game）」を提案・分析しました。

• 初期状態: $n$ 個の $F_1$（1）からなる順序付きリスト $(F_1, F_1, \dots, F_1)$。
• ルール: プレイヤーは隣接する要素に対してのみ以下の 5 種類の合法な手を打つことができます。
  1. 結合 (Merging): 隣接する $(F_i, F_{i+1})$ を $F_{i+2}$ に置き換える。
  2. 1 の結合 (Merging Ones): $(F_1, F_1)$ を $F_2$ に置き換える。
  3. 分割 (Splitting): $i > 2$ のとき、$(F_i, F_i)$ を $(F_{i-2}, F_{i+1})$ に置き換える。
  4. 2 の分割 (Splitting Twos): $(F_2, F_2)$ を $(F_1, F_3)$ に置き換える。
  5. 入れ替え (Switching): 隣接する要素 $(F_i, F_j)$ が $i > j$ の場合（順序が逆転している場合）、それらを $(F_j, F_i)$ に交換する。
• 終了条件: リストが厳密に昇順であり、かつ結合・分割の操作が不可能になった状態（すなわち、$n$ のゼッケンドルフ分解）に達したとき。

2. 手法と理論的アプローチ

本研究は、理論的な証明と計算機シミュレーションの両面からアプローチしています。

理論的証明

• 単調変数（Monovariant）の構成: ゲームの終結と最終状態の一意性を証明するために、状態 $S = (F_{i_1}, \dots, F_{i_k})$ に対して関数 $f(S) = \sum_{j=1}^k (k + 1 - j)F_{i_j}$ を定義しました。この関数は、結合、分割、入れ替えのすべての合法な手番において厳密に減少することが示され、ゲームが無限に続くことがない（必ず終了する）こと、および最終状態が一意なゼッケンドルフ分解であることを証明しました。
• 状態遷移グラフ: ゲームの長さを最大化する戦略（Long Game Strategy: LGS）を分析するために、高インデックス項（$F_3$ 以上）における重複パターンの状態遷移グラフを構築し、その構造を数学的に解析しました。

計算機シミュレーション

• 小規模な $n$ に対する完全探索（Exhaustive Search）を行い、勝敗パターンの分析を行いました。
• 大規模な $n$ に対するランダムプレイのシミュレーションを行い、ゲーム長の分布特性を調査しました。

3. 主要な貢献と結果

3.1 ゲームの終結と最終状態

• 定理 1.3: 順序付きゼッケンドルフ・ゲームは有限の手番で必ず終了し、最終状態は $n$ のゼッケンドルフ分解（厳密に昇順のフィボナッチ数列）となります。

3.2 ゲーム長の境界値

• 最短ゲーム長: 最小手番数は $n - Z(n)$ です（$Z(n)$ は $n$ のゼッケンドルフ分解における項数）。これは貪欲法で隣接する項を可能な限り早く結合することで達成されます。
• 最長ゲーム長の上限: 最長ゲーム長 $M(n)$ は、$M(n) \le \frac{n(n-1)}{2}$ で抑えられます。
• 最長ゲーム長の下限と漸近挙動: 「Long Game Strategy (LGS)」という優先順位ベースの戦略（入れ替え→1 の結合→分割→結合の順序で実行）を用いることで、$M(n)$ の下限を導出しました。
  • 下限：$M(n) \ge \frac{n^2}{2} - n \log_\phi(n) + o(n \log_\phi(n))$
  • 上限（改良版）：$M(n) \le \frac{n^2}{2} - \frac{1}{32}n \log_\phi(n) + o(n \log_\phi(n))$
  • 結論: 最長ゲーム長は $M(n) = \frac{n^2}{2} - \Theta(n \log_\phi(n))$ として漸近的に振る舞います。

3.3 勝敗戦略とゲームのバランス

• Player 1 の優位性: 従来の非順序ゲームでは Player 2 が支配的でしたが、順序制約と「入れ替え」操作の導入により戦略的バランスが変化しました。
• シミュレーション結果: $n \le 25$ の範囲での完全探索により、$n=18$ を除くすべての $n$ で Player 1 が勝利する戦略を持っていることが確認されました。$n=18$ のみが Player 2 の勝利となります。これは順序制約がゲームの複雑さを高め、Player 1 に有利な構造を生み出していることを示唆しています。

3.4 ランダムプレイの分布

• 全ての合法な手を等確率で選択するランダムプレイにおいて、ゲーム長（手番数）の分布は $n \to \infty$ で**対数正規分布（Log-normal distribution）**に収束する可能性がシミュレーションデータから示唆されました（予想 3.2）。

4. 意義と今後の展望

学術的意義

• 数論的ゲームの拡張: ゼッケンドルフ分解に基づくゲームに「順序」と「入れ替え」という新しい制約を導入することで、単なる数値分解のゲームから、位置関係と局所的な操作が戦略に深く関わる高度な組み合わせゲームへと進化させました。
• 戦略的複雑性の回復: 従来のゲームが持っていた「Player 2 の支配」という単純化された構造を打破し、より予測困難でバランスの取れた戦略的景観を創出しました。
• 漸近解析の進展: ゲーム長の最大値が $n^2/2$ のオーダーで増大し、その補正項に $\log_\phi(n)$ が現れるという精密な漸近挙動を明らかにしました。

今後の課題

• 最適戦略の一般化: $n > 25$ における勝敗の一般則や、Player 1 の優位性が普遍的かどうかの証明。
• 最長ゲーム戦略の証明: LGS が実際に最長手番を実現することを厳密に証明すること。
• 一般化: $k$-bonacci 数列や非定数漸化式など、他の漸化式に基づくゲームへの拡張。
• 確率論的解析: ランダムプレイにおける対数正規分布の収束の厳密な証明と、エルゴード理論的な性質の解明。

本論文は、数論的ゲームの分野に新たなアルゴリズム的課題と理論的枠組みを提供し、組み合わせゲーム理論と整数表現の交差点における研究のフロンティアを切り開くものです。