Additive Subtraction Games

Each language version is independently generated for its own context, not a direct translation.

1. ゲームのルール：お菓子の取り合い

まず、このゲームのルールをイメージしてください。

プレイヤー: 2 人。
道具: お菓子の山（カウンター）が 1 つあります。
行動: 自分の番になったら、山から**「決まった数」**のお菓子を取り除きます。
制限: 取り除ける数は、あらかじめ決められたセット $S = \{a, b, a+b\}$ $S = {a, b, a + b}$ の中から選ぶ必要があります。
- 例： $a=3, b=5$ なら、3 個、5 個、または 8 個（$3+5$）取れます。
負け条件: お菓子が取れなくなったら（残りが 0 個、または取り除ける数が残りの量より多い場合）その人の負けです。

このゲームには**「必勝法」**があります。

P ポジション（必敗点）: 今自分がここにいると、相手が上手にプレイすれば負ける場所。
N ポジション（必胜点）: 今自分がここにいると、上手にプレイすれば勝てる場所。

この論文の目的は、「どんなお菓子の数（位置）でも、それが P ポジションか N ポジションか、そしてその『強さ（ニム値）』がいくつなのか」を、複雑な計算なしに瞬時に見分ける公式を見つけることでした。

2. 発見された「魔法の公式」

これまで、このゲームの必勝法は「パターンを見つけるまでひたすら計算する」しかなかったのですが、著者たちはある**「魔法の公式」**が正解であることを証明しました。

この公式は、**「床関数（小数点以下を切り捨てる機能）」**を使った、少し変わった式です。
$w_n = n + a \times \lfloor \frac{n}{a} \rfloor + b \times \lfloor \frac{n}{\delta} \rfloor$
（ $\lfloor \dots \rfloor$ は小数点以下を切り捨てる意味です）

この式で計算された数字 $w_n$ が、**「負ける場所（P ポジション）」**のリストになります。
つまり、「お菓子が $w_n$ 個残っているときは、絶対に負ける（相手が上手なら）」と、この式を見れば一発でわかるのです。

3. なぜこれがすごいのか？「階段の隙間」の謎

この研究の面白いところは、この公式が**「4 つの異なるグループ」**に世界を分けると言っている点です。

お菓子の数が 0, 1, 2, 3... と増えていくとき、その「強さ（ニム値）」は 0, 1, 2, 3 の 4 つのパターンで繰り返されます。

0 (P ポジション): 負ける場所。
1: 1 回動けば P ポジションにできる場所。
2: 2 回動けば P ポジションにできる場所。
3: 3 回動けば P ポジションにできる場所。

著者たちは、この 4 つのグループが**「完全に重なり合わずに、すべての数字をカバーしている」ことを証明しました。
まるで、「4 色のペンキで、地面の数字をすべて塗り分け、どこにも隙間も重なりもないようにした」**ような状態です。

4. 難しかった部分：「衝突」の計算

ここが最も数学的に難しい部分ですが、**「お菓子の山」**というイメージで説明します。

公式で計算した「負ける場所（P ポジション）」のリストを並べると、その間隔（ギャップ）は一定ではありません。

1 個の隙間
5 個の隙間
12 個の隙間
など、4 種類の「間隔」が規則的に現れます。

ここで問題が発生します。
「負ける場所」のリストを、ある数だけずらしたとき（例えば、 $b$ 個ずらす）、元のリストと**「どこかで重なる（衝突する）」**のでしょうか？
もし重なってしまうと、「ここは P ポジションなのに、ずらしたらまた P ポジション？」となって矛盾が起きます。

著者たちは、この**「衝突」が起きる場所と回数を、数学的に正確に数え上げました**。
それは、**「階段の段差」**のようなイメージです。

階段の段差（間隔）が一定の規則で並んでいる。
その階段を少しずらして重ねると、どの段がどの段とぶつかるか。
そのぶつかり具合を、**「左側の制限」「右側の制限」**という 3 つのゾーンに分けて計算し、合計がちょうど良い数字になることを示しました。

この計算が完璧に合致したことで、「4 つのグループに分ける」という主張が、単なる推測ではなく**「絶対的な事実」**であることが証明されたのです。

5. まとめ：何ができたのか？

この論文は、**「足し算と引き算のゲーム」**という、1982 年の名著『Winning Ways』で提起されて以来、完全な証明がなかった難問を解決しました。

発見: 必勝法（P ポジション）は、ある「床関数を使った公式」で正確に書ける。
証明: その公式が、ゲームのすべての状態を 4 つのグループ（0, 1, 2, 3）に完璧に分割することを示した。
手法: 数字の「間隔」の規則性と、それをずらした時の「衝突」を、数論（数字の性質）を使って精密に計算した。

一言で言うと：
「このゲームの勝敗は、複雑な計算ではなく、『床関数』というシンプルなルールで決まっていることがわかった。しかも、そのルールがすべての数字をきれいに 4 色に塗り分けていることを、数学的に証明した！」

これは、一見ランダムに見えるゲームの奥に、**「美しい数学的な秩序」**が隠れていることを示した、非常にエレガントな研究です。

Each language version is independently generated for its own context, not a direct translation.

この論文「ADDITIVE SUBTRACTION GAMES（加法的引き算ゲーム）」は、都市ラッソン（Urban Larsson）と真鍋光（Hikaru Manabe）によって執筆されたもので、組合せゲーム理論における「加法的引き算ゲーム」のニム値（nim-value）構造、特に「原始的二次レギーム（primitive quadratic regime）」における完全な解を導出するものです。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳細な技術的サマリーを記述します。

1. 問題設定

加法的引き算ゲーム: 2 人のプレイヤーが、正の整数の集合 $S$ に含まれる数 $s$ を、現在の山（heap）から取り除くゲームです。取り残された数が負にならない限り移動が可能で、移動できなくなったプレイヤーが敗北します。
対象とするゲーム: $S = \{a, b, a+b\}$ であり、ここで $b = a + \delta$ とします。
原始的二次レギーム: パラメータは $a < \delta < 2a$ かつ $\gcd(a, \delta) = 1$ を満たす範囲に限定されます。この範囲は、 $a$ と $\delta$ の 2 つのスケールが非自明に相互作用し、問題の二次的な複雑さの源泉となる領域です。
既存の研究: 1982 年の『Winning Ways』において、P-ポジション（先手必敗の位置）の閉じた公式が提案されましたが、その完全な証明は文献に存在しませんでした。Miklós と Post (2024) は結果の周期性を証明しましたが、その閉じた公式への言及はありませんでした。

2. 主要な結果と定理

論文の核心は、以下の**定理 1（主要定理）**の証明にあります。

定理 1: $a < \delta < 2a$ かつ $\gcd(a, \delta) = 1$ 、 $b = a + \delta$ とする。このとき、自然数集合 $\mathbb{N}_0$ は、以下の 4 つの互いに素な集合 $W_0, W_1, W_2, W_3$ に分割され、それぞれがニム値 $0, 1, 2, 3$ に対応する。

P-ポジション（ニム値 0）:
$W_0 = \{ w_n : n \ge 0 \}$
ここで、 $w_n$ は以下の「括弧式（bracket expression）」で定義される。
$w_n = n + a \left\lfloor \frac{n}{a} \right\rfloor + b \left\lfloor \frac{n}{\delta} \right\rfloor$
（注：これは 3 項の括弧式であり、 $n$ は $1 \cdot \lfloor n/1 \rfloor$ とみなされる。）
ニム値 1 の位置:
$W_1 = W_0 + a = \{ w_n + a : n \ge 0 \}$
（Ferguson のペアリング原理により導かれる。）
ニム値 2 の位置:
$W_2 = W_0 - b = \{ w_n - b : n \ge 0 \}$
ニム値 3 の位置:
$W_3 = (W_0 - \delta) \setminus W_0$
（ $W_0$ を $\delta$ だけシフトした集合から、 $W_0$ 自体を除いた集合。）

これらの集合の和は自然数全体を覆い、ゲームのすべての位置のニム値を完全に分類します。

3. 手法と証明の概要

証明は、位置のサイズに関する強い帰納法（strong induction）に基づいており、以下のステップで構成されています。

A. 反衝突（Anti-collision）の証明

Lemma 3: 任意の異なる $n, m$ に対して、 $w_n - w_m \in \{a, b, a+b\}$ とならないことを示します。
これにより、 $W_0$ 内の任意の 2 点間には移動が存在せず、 $W_0$ が P-ポジションの候補として妥当であることが確認されます。同様の論理が $W_1, W_2, W_3$ にも適用されます。

B. 到達性（Reachability）の検証

ニム値 1: $W_1$ の各要素は $W_0$ へ移動可能（ $-a$ ）であり、 $W_0$ が P-ポジションであれば、Ferguson の原理によりニム値 1 となります。
ニム値 2: $W_2$ の要素 $v_n = w_n - b$ について、 $v_n - b$ が $W_0$ または $W_1$ に属することを数論的に示し、ニム値 0 または 1 への移動が存在することを証明します。
ニム値 3: $W_3$ の要素は、 $W_0$ への移動（ニム値 0）と $W_2$ への移動（ニム値 2）が可能であることを示し、ニム値 3 であることを導きます。

C. 数論的構造と衝突の解析（セクション 4）

最も技術的に高度な部分は、 $W_3$ のサイズを決定する「 $\delta$ -衝突（ $\delta$ -collisions）」の解析です。

衝突の定義: $W_0$ とその $\delta$ シフト $W_0 - \delta$ の共通部分 $C = (W_0 - \delta) \cap W_0$ を調べます。これは $w_n - w_m = \delta$ となるペア $(m, n)$ の数に対応します。
ギャップの規則性: $w_n$ の差分（ギャップ） $g_n = w_{n+1} - w_n$ は、 $n+1$ が $a$ または $\delta$ の倍数かどうかによって決まり、4 種類の値 $\{1, a+1, b+1, b+a+1\}$ のみを取ります。
衝突ウィンドウ: $\delta$ の長さを満たす連続したギャップの和として衝突を定義し、 $(a+1)$ のギャップを挟む左右の「1」のギャップの数（ $L, R$ ）に基づいて、各 $(a+1)$ -ギャップがいくつの衝突ウィンドウに寄与するかを計算します。
剰余類による分類: 剰余 $r \equiv qa \pmod \delta$ に応じて、衝突数 $c(r)$ が「左制限領域」「無制限領域」「右制限領域」の 3 つの領域で異なる挙動を示すことを明らかにし、その総和が $ad$ となることを証明しました（定理 7）。
結果: この解析により、 $W_3$ の周期内のサイズが $a^2$ であることが示され、4 つの集合が自然数を完全に分割することが確認されました。

4. 主要な貢献

未解決問題の解決: 『Winning Ways』で提示された P-ポジションの閉じた公式（括弧式）に対する完全な証明を初めて提供しました。
完全なニム値構造の解明: 単に P-ポジションだけでなく、ニム値 1, 2, 3 に対応する位置の集合をすべて明示的な式（ $W_0$ のアフィン変換や差集合）として記述し、それらが自然数を分割することを証明しました。
数論的メカニズムの解明: 括弧式（Beatty 型の床関数の線形結合）のシフトによる衝突構造を、剰余類と「衝突ウィンドウ」の概念を用いて詳細に解析しました。これは、従来の Beatty 列の分割問題（Fraenkel の予想など）とは異なる、新しい数論的アプローチです。
周期性の明確化: インデックス周期が $a\delta$ 、ヒープ周期（実際のゲーム位置の周期）が $(3\delta + a)a$ であることを示しました。

5. 意義と今後の展望

理論的意義: この研究は、二次的な複雑さを持つ引き算ゲームの核心を捉えており、より一般的な加法的引き算ゲームや、双対設定（sink subtraction）における複雑性の理解の基盤となります。
応用可能性: 得られた「括弧式」の構造は、より高次の多項式レギームや、異なるニム値のシードを持つゲームへの拡張（質問 17, 18）への道を開きます。
数論的貢献: 固定項数の括弧式におけるシフト衝突集合 $C(k)$ の構造を研究する新たな分野（質問 19）を提起しており、これは従来の Beatty 列の理論を超えた新しい数論的課題です。

総じて、この論文は組合せゲーム理論と数論の交差点において、特定のクラスの問題に対して完全な解決を与え、その背後にある精巧な数論的構造を明らかにした重要な業績です。