Welter のゲーム（Welter's game、佐藤幹夫の「マヤゲーム」と同じもの）をブラウザに実装した。0, 1, 2, … と番号のついた細長い盤に硬貨が並び、1 マスに 1 枚まで。手番では硬貨を 1 枚、それより番号の小さい空いたマスへ動かす（他の硬貨を飛び越えてよい）。動かせなくなった人の負け。硬貨 1 枚なら Nim の山そのものなので、全体は「山が同じ大きさになってはいけない Nim」になる。この 1 つの制約で Nim の和（XOR）は使えなくなり、Welter（1954）が別の式を見つけた。佐藤はこの盤を Young 図形として読み直し、硬貨を a から b へ動かすことは長さ a − b のフックを取り除くことだと気づいた。局面の Grundy 数は、全フック長 h について 2^(ord₂ h + 1) − 1 を XOR したもの。対称群の既約表現の次元を出すフック長公式と同じ数を使う。デモは局面を硬貨と Young 図形の両方で描き、Grundy 数を 3 通りの式で計算し、合法手ごとに勝ち手 ✓／負け手 ✗ を出す。式を信じずに、(1) 26 マスに収まる全 67,108,864 局面を素朴な mex で解き、3 つの式とすべて一致、(2)「値 = マス数 |λ|」になる満ちた局面の数が、表現の次元が奇数になる分割の数、OEIS A059867 と n ≤ 72 の全項で一致（Irie が 2025 年 10 月に OEIS に書き足したコメントの検算）、(3) Irie（2018）が「分かっていない」とした p-飽和指数（複数枚を同時に動かしてよいゲームで、何枚まで動かせば値が p 進のフック数え上げになるか）を有限の窓で正確に計算し、p = 3, 4, 5 の調べた範囲すべてで論文の下界 min(p, m + 1) ちょうどだった。テスト 13 件。ソルバー内蔵パズル第 102 弾。
デモ: https://sen.ltd/portfolio/welters-game/
リポジトリ: https://github.com/sen-ltd/welters-game
ルール
- 盤は 0, 1, 2, … と番号のついたマスの列。硬貨が何枚か置いてあり、1 マスに 1 枚まで。
- 手番では硬貨を 1 枚選び、それより小さい番号の空いたマスへ動かす。途中の硬貨は飛び越えてよい。
- 動かせなくなった人の負け（正規形）。硬貨が全部 0, 1, 2, … と下に詰まると終わり。
デモには 3 つのモードがある。自分が先手、コンピュータが先手、両方を自分で指す study。硬貨をクリックすると動かせるマスが光り、ヒントを出していれば勝ち手 ✓ と負け手 ✗ が付く。コンピュータは勝ち手があれば必ず指し、なければ 1 マスだけ動かして粘る。
Nim の和が崩れる
硬貨が 1 枚だけなら、マス a の硬貨は大きさ a の Nim の山と同じだ。好きなだけ減らせる。硬貨が複数あれば Nim の山が複数あるのと同じで、ただし同じ大きさの山を 2 つ作ってはいけない。
この制約だけで XOR の公式は崩れる。{1, 2}（マス 1 と 2 に硬貨）の XOR は 3 だが、実際の Grundy 数は 2 だ。2 → 1 は 1 が埋まっているので指せず、指せる手は 2 → 0（{0, 1}、終局で 0）と 1 → 0（{0, 2}、値 1）の 2 つしかない。mex{0, 1} = 2。
Welter（1954）の答えは次の式。
sg(x¹, …, xᵐ) = x¹ ⊕ … ⊕ xᵐ ⊕ ⨁_{i<j} N(xⁱ − xʲ), N(d) = d ⊕ (d − 1)
N(d) = d ⊕ (d − 1) は「d の 2 進で一番下の 1 から下を全部 1 にした数」、つまり 2^(ord₂ d + 1) − 1 だ。{1, 2} なら 1 ⊕ 2 ⊕ N(1) = 3 ⊕ 1 = 2 になる。
スクリーンショットの局面 {1, 4, 5, 9, 11} では、硬貨の XOR が 2、10 組の差の N の XOR が 12 で、値は 2 ⊕ 12 = 14。勝ち手は 9 → 3 の 1 つだけ。デモの右側に、この計算の途中経過を出している。
盤を Young 図形として読む（佐藤のマヤゲーム）
佐藤幹夫は 1968〜70 年にこのゲームを独立に解き、盤を Young 図形に読み替えた。硬貨を上から x¹ > x² > … > xᵐ と並べ、
λᵢ = xⁱ − (m − i)
を行の長さにする。言い換えると、行は硬貨、列は空きマスで、「硬貨 a と、それより下の空きマス e」の組 1 つが 1 マスになる。そのマスのフック長は a − e だ。{1, 4, 5, 9, 11} なら λ = (7, 6, 3, 3, 1)、20 マスで、11 の硬貨の行には 11, 9, 8, 5, 4, 3, 1 が並ぶ（空きマス 0, 2, 3, 6, 7, 8, 10 との差）。
この読み方では、硬貨を a から空きマス b へ動かすと、長さ a − b のフックが 1 本取り除かれる。デモで硬貨を選んで行き先にマウスを載せると、取り除かれるフックが緑の枠で光る。スクリーンショットは 9 → 3 で、長さ 6 のフックを取る手だ。
そして佐藤の式は、フック長だけで値を書く。
sg(λ) = ⨁_{フック長 h} (2^(ord₂ h + 1) − 1)
硬貨 1 枚（λ = (a)、フック長 a, a − 1, …, 1）なら、h ⊕ (h − 1) の XOR は望遠鏡のように消えて a になり、Nim の山に戻る。
Irie（2018）はこれをもう一段ほどいた。2 進の第 L 桁は、長さが 2^L で割り切れるフックの本数の偶奇になる。{1, 4, 5, 9, 11} の 20 本のフックでは、
| 2^L | 割り切れるフック | 桁 |
|---|---|---|
| 1 | 20 | 0 |
| 2 | 7 | 1 |
| 4 | 3 | 1 |
| 8 | 1 | 1 |
で 1110₂ = 14。デモはこの表もそのまま出している。
3 つの式を総当たりで確かめる
式を信じないで、窓 [0, n) に収まるすべての硬貨の置き方を素朴な mex で解く。置き方はビットマスク（ビット a が立つ ⇔ マス a に硬貨）で持つ。硬貨を a から b < a へ動かすとマスクは必ず小さくなるので、マスクの昇順に 1 回なめれば評価順として正しい。
for (let mask = 1; mask < 1 << n; mask++) {
stamp++;
for (let a = 1; a < n; a++) {
if (!(mask & (1 << a))) continue;
const without = mask ^ (1 << a);
for (let b = 0; b < a; b++) if (!(mask & (1 << b))) seen[g[without | (1 << b)]] = stamp;
}
let v = 0;
while (seen[v] === stamp) v++;
g[mask] = v;
}
n = 26 で 67,108,864 局面、DP が 94.6 秒、Welter の式と（盤から直接数えた）フックの式との照合を含めて 212.7 秒（Node 26、1 スレッド）。食い違いは 0。分割に直して計算する版（hookFormula、btower）は 18 マスの 262,144 局面で照合して 0。
副産物として、硬貨の枚数ごとの P 局面（値 0）の数が出る。
0:1 1:1 2:13 3:90 4:518 5:2,098 6:7,318 7:20,690 8:49,195 9:98,095 10:166,631 11:241,876 12:302,660 13:325,948 14:302,660 …
c 枚と 26 − c 枚で数がぴったり対称になる。理由は図形の側にある。盤を左右反転して硬貨と空きを入れ替えると、Young 図形は転置（共役分割）になる。フック長の多重集合は転置で変わらないので、値も変わらない。テストにはこの対称性も入れた。
満ちた局面と、奇数次元の表現
フック長は表現論の数でもある。n 個のマスを持つ Young 図形 λ は対称群 Sₙ の既約表現 χ^λ に対応し、その次元はフック長公式
dim χ^λ = n! / ∏ h
で出る。{1, 4, 5, 9, 11} なら 20! / ∏h = 94,057,600。
Irie（2018）は Macdonald（1971）の結果を使って、
値 = |λ|（マスの数）⇔ dim χ^λ が奇数
を示した。値が |λ| に達する局面を満ちた局面（full position）と呼ぶ。2 進で n = Σ 2^{e_i} のとき、奇数次元の既約表現の数は 2^{Σ e_i}（Macdonald）。これが OEIS A059867 で、2025 年 10 月に Irie 自身が「Welter のゲームで値 n の満ちた局面の数でもある」とコメントを足している。
これを 3 方向から数えた。
- ゲームそのもの：上の総当たり表から、マス 0 に硬貨のない置き方（分割 1 つにつき 1 つ）を数える。値は mex で出したもので、式は使っていない。n < 26 の 25 項。
- フックの式：n ≤ 72 の分割を全部（計 40,143,941 個）列挙し、値 = n のものを数える。
- 次元の偶奇：同じ分割について ord₂(n!) = Σ ord₂(h) かどうか（Legendre の公式）。
3 つとも OEIS の b-file と 72 項すべて一致、分割ごとの判定の食い違いも 0 だった。数字の並びは面白い。n = 31 では 6,842 個中 1,024 個が満ちているのに、n = 32 では 8,349 個中 32 個しかない。2 進で 1 桁の 32 は Σ e_i = 5 で、2^5 = 32。
Irie の定理 1 はさらに、どの局面にも、値と同じマス数の満ちた部分図形 μ ⊆ λ があると言う（|μ| = sg(μ) = sg(λ)）。部分図形を角のマスを 1 つずつ削る DP で持ち上げ、p = 2, 3 は n ≤ 40 の 215,308 分割、p = 5 は n ≤ 30 の 28,629 分割で調べ、反例は 0。論文の例 msg({3, 7}) = 8、msg({3, 4, 5}) = 6（p = 3）もそのままテストに入れた。
未知の数を測る：p-飽和指数
ここからが論文の未解決部分だ。Irie は 2 を一般の p に置き換えるため、ゲームを少し緩めた。
- 一度に k − 1 枚までの硬貨を同時に下げてよい（各硬貨は名前つきで、追い越してもよい）。
- ただし、動いた距離 dᵢ について ord_p(Σ dᵢ) = min ord_p(dᵢ) のときだけ合法。
これを W^m_{p,k}（硬貨 m 枚）と書く。p = 2, k = 2 は元の Welter のゲーム。論文の例では、W_{2,3} で {3, 4} から {0, 1} へは行ける（4 → 0 と 3 → 1、距離 4 と 2、和 6 の ord₂ は 1 で最小値 1 と一致）。
Irie の主定理は、k を十分大きくすると（k = m + 1、つまり全部動かしてよければ必ず）、値がp 進のフック数え上げ、
b_p(λ) の p 進第 L 桁 = （長さが p^L で割り切れるフックの本数）mod p
になる、というもの。そうなる最小の k が p-飽和指数 sat_p(W^m) で、論文は sat_p(W^m) ≥ min(p, m + 1) を示したうえで、3 ≤ p ≤ m では正確な値が分からないと書いている。下界の証拠は具体的な局面だ。k = min(p, m + 1) として {p, p + 1, …, p + k − 2} の硬貨を m − k + 1 マス上にずらし、空いた下の m − k + 1 マスを硬貨で埋めた局面は、b_p = p(k − 1) なのに、k − 1 枚までしか動かせないと値 0 の局面に行けない。
これは有限の窓で正確に計算できる。窓 [0, n) の局面から行ける局面はまた窓の中なので、窓の中の値は無限の盤での値と同じだ。やることは、
- m 枚の置き方を硬貨の和の順に並べる（どの手も和を減らすので、和の順が評価順になる）。
- 置き方を colex 順位 Σ C(xᵢ, i + 1) で番号づけし、Int32 の表で値を引く。
- 手は硬貨を 1 枚ずつ「動かさない／0 … x − 1 のどこかへ」と再帰で決め、最終位置のビットマスクで衝突を切る。動いた枚数が k − 1 に達したら残りは動かさない。葉で ord_p の条件を見る。
速い表と、定義そのままの遅い手生成（satOptions）で mex を取り直した値とが一致することを、テストで確かめている。
結果（「differ」は b_p と値が食い違った局面の数）：
| p | m | k | 窓 | 局面 | differ | 最初の食い違い |
|---|---|---|---|---|---|---|
| 3 | 3 | 2 | [0, 20) | 1,140 | 1,060 | {0, 2, 4}：値 1、b₃ = 3 |
| 3 | 3 | 3 | [0, 31) | 4,495 | 0 | — |
| 3 | 4 | 3 | [0, 31) | 31,465 | 0 | — |
| 3 | 5 | 3 | [0, 28) | 98,280 | 0 | — |
| 3 | 6 | 3 | [0, 25) | 177,100 | 0 | — |
| 3 | 7 | 3 | [0, 23) | 245,157 | 0 | — |
| 3 | 8 | 3 | [0, 22) | 319,770 | 0 | — |
| 4 | 3 | 3 | [0, 24) | 2,024 | 132 | {4, 5, 6}：値 0、b₄ = 12 |
| 4 | 4 | 4 | [0, 22) | 7,315 | 0 | — |
| 4 | 5 | 4 | [0, 21) | 20,349 | 0 | — |
| 5 | 4 | 4 | [0, 24) | 10,626 | 159 | {5, 6, 7, 8}：値 0、b₅ = 20 |
| 5 | 5 | 4 | [0, 22) | 26,334 | 735 | {0, 6, 7, 8, 9}：値 0、b₅ = 20 |
| 5 | 5 | 5 | [0, 22) | 26,334 | 0 | — |
| 5 | 6 | 5 | [0, 19) | 27,132 | 0 | — |
読み方：
- 太字の k はすべて下界 min(p, m + 1) そのもの。p = 3 なら、硬貨が 8 枚あっても「同時に 2 枚まで」動かせれば値が 3 進のフック数え上げに一致した。窓の中に反例は 1 つもない。
- 下界より 1 少ない k では食い違いが出て、和が最小の食い違いは論文の証拠局面そのものだった。p = 4, m = 3 の {4, 5, 6} は λ = (4, 4, 4)、p = 5, m = 4 の {5, 6, 7, 8} は λ = (5, 5, 5, 5)。どちらも b_p = p(k − 1) で、値は 0。
- p = 4 は素数でないが、論文の定理は p > 1 の整数で成り立つので含めた。結果は素数と同じ形だった。
注意しておくと、窓が有限なので「sat_p(W^m) = min(p, m + 1)」の証明ではない。食い違いの側（下界）は具体的な局面なので証明になるが、一致の側は「この範囲に反例がない」という証拠にとどまる。ただ、p = 3 で m = 8 まで、窓 22〜31 で反例がないのは、予想を立てるには十分な量だと思う。
実装メモ
-
src/welter.ts：Welter の式、分割 λ(X)、フック長、佐藤の式、Irie の b_p（btower）と p 進 Welter 式、合法手・勝ち手、BigInt での次元、総当たり表（bruteForceTable）。 -
src/saturation.ts：W^m_{p,k} の値の表（saturationTable）、定義どおりの手生成（satOptions）、部分図形の列挙と Irie の msg。 -
tools/compute.mts：brute <n>、full <nmax>、msg <p> <nmax>、sat <p> <m> <k> <n>。結果はruns/*.json、tools/report.mtsが README の表とデモ下部の文章（src/findings.json）を作る。表の数字は手で書き写していない。 - デモは依存ゼロの TypeScript + Vite。
まとめ
- Welter のゲームは「山が同じ大きさになってはいけない Nim」で、XOR の代わりに Welter の式、あるいは佐藤のフック長の式で値が出る。硬貨の移動はフックの除去になる。
- 26 マスの全 67,108,864 局面で、3 つの式は素朴な mex と完全に一致した。硬貨と空きの入れ替え（転置）で値が変わらないことも数で見える。
- 値がマス数に届く「満ちた局面」は、対称群の奇数次元の表現と同じ数だけある。n ≤ 72 で OEIS A059867 と全項一致した。
- 論文で未知の p-飽和指数は、調べた範囲（p = 3 は m ≤ 8、p = 4 は m ≤ 5、p = 5 は m = 5, 6）ですべて下界 min(p, m + 1) ちょうどで、1 少ないと論文の証拠局面で崩れた。