77

数理解析研究所講究録第2003巻 2016年 77-81

P 飽和 Welter ゲーム
千葉大学大学院理学研究科

入江佑樹

Yuki Irie
Graduate School of Science,Chiba University
p 飽和 Welter ゲームの Sprague‐Grundy 関数 \mathrm{s}\mathrm{g} は,対称群の通常既約表現の次数と深く関係している.このゲームの局面は分割 $\lambda$ で表せる. $\rho$^{ $\lambda$} を $\lambda$ に対応する \mathrm{S}\mathrm{y}\mathrm{m}(| $\lambda$|)の既約表現としよう.このとき,全ての素数 p に対して次の二つを示した: (1) $\rho$^{ $\lambda$} の次数が pと素である必要十分条件は \mathrm{s}\mathrm{g}( $\lambda$)=| $\lambda$| である;(2) $\rho$^{ $\lambda$} の \mathrm{S}\mathrm{y}\mathrm{m}(\mathrm{s}\mathrm{g}( $\lambda$) への制限は次数が p と素な既約成分を持つ.さらに,全ての2以上の整数 p に対して \mathrm{s}\mathrm{g}( $\lambda$) の明示
公式を与えた.

1

Welter ゲーム
Welter ゲームは,有限枚のコインを使った二人対戦ゲームである.各コインは,左から0 1, 2,,\cdotsと番号をつけたマス目上に置かれている.ただし,一つのマス目に置くことができるコインは高々 1枚である.二人のプレイヤーは交互に1枚のコインを空いている
小さい数字のマス目 (左側のマス目) に移動する.交互に移動していき,先に動かせなくなった方が負けである.さて,コインが x^{1}, x^{2},..

.

x^{m} のマス目にある局面 X を考えよう.Welter [14] はXのSprague‐Grundy 数(次節で定義する) の公式を与えている:\mathrm{s}\mathrm{g} ( \mathrm{X} )=x^{1}\displaystyle \oplus_{2}\cdots\oplus_{2}x^{m}\oplus_{2}(\bigoplus_{i<j}2N_{2}(x^{i}-x^{j})

.

(1.1)

ただし \oplus_{2} は2進展開して繰り上がりのない足し算を表し N2 (x)=x\oplus_{2}(x-1) である.局面 X は m 点集合 \{x^{1}, . . , x^{m}\}\subset \mathbb{N} と (x1, . . , x^{m})\in 1\mathrm{N}^{m} のどちらでも表せることに注意しておく.ただし \mathbb{N} は非負整数全体である.
Welter ゲームは,ヤング図形を使ったゲームと思うこともできる[10]. 分割 $\lambda$(X)78(x^{ $\sigma$(1)}-m+1,x^{ $\sigma$(2)}-m+2, \ldots,x^{ $\sigma$(m)}) で定義する.ただしを$\sigma$はx^{ $\sigma$(1)}>x^{ $\sigma$(2)}>>x^{ $\sigma$(m)} となる置換である.分割 $\lambda$(X) と対応するヤング図形 \{(i,j)\in \mathbb{Z}^{2}|1\leq i\leq

1\leq j\leq x^{ $\sigma$(i)}-m+i\} を同一視する.このとき,コインを動かすことは,フックを抜m,くことに対応する.佐藤 [11, 12] は(1.1) に加えて,別の形の公式を得ている

さらに,この別の形がフック長公式に似ていることから,Welter ゲームは対称群の表現と関係があることを予想している.川中 [7] は \mathrm{s}\mathrm{g}(\mathrm{X}) を $\lambda$(X) の2‐core towerを使って表してい*1

る.

本稿の目的は p 飽和という概念を導入し, p 飽和 Welter ゲームの Sprague‐Grundy関数と対称群の通常既約表現の次数の関係を与えることである.なお,本稿の詳細は投稿準備中である [5].

p 飽和 Welter ゲーム

2

本稿では (不偏)(G)

ゲームとは次を満たす有向グラフを表す :各頂点 Xについて X を始点とするパスの長さの最大 \mathrm{l}\mathrm{g}(X) が有限である.

ゲームの頂点を局面と呼ぶ.二つの局面 X と Y に対して, X から \mathrm{Y} への辺 (X, Y) があるとき \mathrm{Y} を X の子と呼ぶ.このとき条件 (G) より \mathrm{l}\mathrm{g}(\mathrm{Y})<\mathrm{l}\mathrm{g}(\mathrm{X}) に注意しよう.

ゲームはSprague‐Grundy 数で解析できる.局面 X のSprague‐Grundy 数 \mathrm{s}\mathrm{g}(\mathrm{X})とは,次を満たす非負整数 n の中で最小のものである :\bullet \mathrm{X} の子 \mathrm{Y} に対して sg(Y) \neq n.

ゲーム $\Gamma$ の局面全体から IN への写像 \mathrm{X}\mapsto \mathrm{s}\mathrm{g}(X) を $\Gamma$ のSprague‐Grundy 関数と呼ぶ.条件 (G) よりゲームには子を持たない局面 X がある.定義から X のSprague‐

Grundy 数は 0 と定まり,ここから \mathrm{l}\mathrm{g} が小さい順に Sprague‐Grundy 数は定まっていく.定義から sg(X) \leq \mathrm{l}\mathrm{g}(X) である.例えばWelter ゲームの局面 X の場合は\mathrm{s}\mathrm{g}(X)\leq \mathrm{l}\mathrm{g}(X)=| $\lambda$(X)| である.さてSprague‐Grundy の定理 [4, 13] から任意のゲー
ムの局面 X は,1枚のコインを使った Welter ゲームの局面 {sg(X)} と本質的に同じと思える.特に X が後手必勝形であることとsg(X) =0 は同値である.そのため Sg(X) を求めることがゲームの解析では重要である.Welter ゲームや Nim については,全ての*1

さらに,Welter ゲームを一般化し,良手判定アルゴリズムを含む様々な結果を得ている [7].

79

局面に対して Sprague‐Grundy 数の明示公式が知られている. 2しかし,これらの他に*はそのような例は殆ど見つかっていない.なお,ゲーム理論については [1, 2] が詳しい.
以下 p を2以上の整数とする. m 枚のコインを使った Welter ゲームを \mathcal{W}^{m} で表す.
p 飽和を定義するために,まず p 指数 k の \mathcal{W}^{m} を定義しよう.このゲームは,Mooreの \mathrm{N}\mathrm{i}\mathrm{m}_{k} (指数 k のNim) [9]を満たす (dl,..とFlanigan の \mathrm{R}\mathrm{i}\mathrm{m}_{k} が元になっている.

./d^{m} ) \in \mathbb{N}^{m} 全体としよう:*3集合\mathcal{D}_{p,k}^{m} を次1. 0 でない成分があり,その個数は高々 k-1 個,2. ord(\displaystyle \sum_{i=1}^{m}d^{i})=\min\{\mathrm{o}\mathrm{r}\mathrm{d}(d^{i}):1\leq i\leq m\},ただし \mathrm{o}\mathrm{r}\mathrm{d}(d) は d の p ‐adic order を表す.すなわち d を割り切る p 幕の内の最大幕指数である (\mathrm{o}\mathrm{r}\mathrm{d}(0)=\infty)
このとき.

\mathcal{W}_{\mathrm{P},k}^{m} を頂点集合 \mathcal{V} が\{(x^{1}, \ldots,x^{m})\in N^{m}:x^{i}\neq x^{i}(1\leq i<j\leq m)\}であり,辺集合が \{(\mathrm{X}, \mathrm{Y})\in \mathcal{V}^{2}:\mathrm{X}-\mathrm{Y}\in \mathcal{D}_{p,k}^{m}\} であるゲームと定義する.このゲームを

p 指数 k の \mathcal{W}^{m}と呼ぶ.すなわち,通常の Welter ゲームでは1枚のコインしか動かせなかったが, p 指数 k のWelter ゲームでは高々 k-1 枚のコインを動かすことができる.
例えば \mathcal{W}_{2,3}^{2} において,局面 (4, 3) から局面 ( 1, 0) には移動できないが,局面 (0,1) には移動できる.集合で書くと,局面 {3, 4} から局面 \{0 1 \} に移動できる.
,ゲーム\mathcal{W}_{p,k}^{m} が \mathcal{W}mの p 飽和とは持つことと定義する. 4さらに*\mathcal{W}_{p,k}^{m} と \mathcal{W}_{p_{m+1}}^{m} が同じ Sprague‐Grundy 関数を\mathcal{W}_{p,k}^{m} が \mathcal{W}^{m} の p 飽和となるような最小の k を \mathcal{W}^{m} のp 飽和指数と呼んで,記号 \mathrm{s}\mathrm{a}\mathrm{t}_{\mathrm{P} (\mathcal{W}^{m}) で表す.整数 h が \mathrm{s}\mathrm{a}\mathrm{t}_{\mathrm{p} (\mathcal{W}^{m}) 以上のとき \mathcal{W}_{p}^{m_{h} も\mathcal{W}_{p,m+1}^{m} と同じ Sprague‐Grundy 関数を持つことに注意しておく.
公式 (1.1) より \mathrm{s}\mathrm{a}\mathrm{t}_{2}(\mathcal{W}^{m})=2 がわかる.一般に \displaystyle \mathrm{s}\mathrm{a}\mathrm{t}_{p}(\mathcal{W}^{m})\geq\min(p, m+1) を示せる.しかし, 3\leq p\leq m の場合について \mathrm{s}\mathrm{a}\mathrm{t}_{\mathrm{p} ( \mathcal{W} 吟の正確な値はわかっていない.
*2\mathrm{N}\mathrm{i}\mathrm{m} はWelter ゲームから条件 「 1 マスに置くことができるコインは高々 1枚」を外したゲームである.

*3\mathrm{N}\mathrm{i}\mathrm{m}_{k} と \mathrm{R}\mathrm{j}\mathrm{m}_{k} では,プレイヤーは高々 k-1 枚のコインを動かすことができる. \mathrm{R}\mathrm{i}\mathrm{m}_{k} は未発表論文[3] で導入されている.

*4_{p} 飽和の定義は Nim の誘導部分グラフとなっているゲームに一般化できる.特に Nim の p 飽和は\mathrm{R}\mathrm{j}\mathrm{m}_{p} と同じSprague‐Grundy 関数を持ち, m 枚のコインを使ったNim の p 飽和指数は \displaystyle \min(p,m+1)である.さらに反転 Nim というゲームについて,2飽和した Sprague‐Grundy 関数と2飽和指数がわかっている [6].

80

3主結果
主結果を述べるため,言葉の復習と記号の導入をしよう.X をWelter ゲームの局面,L を非負整数とする.各 (i,j)\in $\lambda$(X) に対してフツク{ (i',j')\in $\lambda$(X):(i'\geq i かつ j^{-}=j)

H_{i,j} とは集合または(i'=i かつ j^{-}\geq j) }のことである.フックは大きさが p^{L} の倍数であるとき p^{L} フック と呼ぶ.

$\lambda$(X) のP^{L} フックの個数を P で割った余りとする.〒(X) を次で定義する〒( X )\overline{ $\tau$}_{L}(\mathrm{X}) を:=\displaystyle\sum_{L\in]\mathrm{N}\overline{$\tau$}_{L}(X)p^{\mathrm{L}(3.1)\oplus p と \ominus p をそれぞれ p 進展開して繰り上がりのない足し算と引き算とする.たとえば5\oplus_{3}10=(2+3)\oplus_{3}(1+9)=3+9 である.整数 x に対して N_{\mathrm{P}}(x)=x\ominus_{p}(x-1) とする.

定理3.1. X を p 飽和 Welter ゲームの局面 \{x^{1}, . . ., x^{m} \} とする.このとき局面 \mathrm{Y} で| $\lambda$(\mathrm{Y})|= 〒(Y)=(ヤング図形として)(X) と$\lambda$(\mathrm{Y})\subseteq $\lambda$(X) を満たすものがある.さ

らに

sg(X)

=

〒(X)

=x_{1}\displaystyle\oplus_{p}\cdots\oplus_{p^{X_{m}\ominus}p (\bigoplus_{i<j}N_{p}(x_{i}-x_{i})= \oplus N_{p}(|H_{i,j}|).

(i,j)\in $\lambda$(X)P を素数としよう. X を p ‐飽和 Welter ゲームの局面として $\rho$^{\mathrm{X} を $\lambda$(\mathrm{X}) に対応する\mathrm{S}\mathrm{y}\mathrm{m}(| $\lambda$|) の既約表現とする.このとき,Macdonald の結果 [8] を使うと,表現 $\rho$^{X} の次数が p と素であることと| $\lambda$(\mathrm{X})|= 〒(X) が同値であることがわかる.よって,定理3.1より次を得る.
系3.2. Xを p 飽和 Welter ゲームの局面とする. p が素数ならば,次が成立する :$\rho$^{\mathrm{X} の次数が p と素であることと \mathrm{s}\mathrm{g}(\mathrm{X})=| $\lambda$(X)| であることは同値である.
2. $\rho$^{\mathrm{X} のSym(sg(X)) への制限は次数が p と素な既約成分を持つ.
1.

ただし \mathrm{S}\mathrm{y}\mathrm{m}(0)=\mathrm{S}\mathrm{y}\mathrm{m}(1) とする.

81

参考文献
[1] E. R. Berlekamp, J. H. Conway, and R. K. Guy. Winning Ways for Your Mathe‐matical Plays. A.K. Peters, Natick, Mass., 2nd edition, 2001.

[2] J. H. Conway. On numbers and games. A.K. Peters, Natick, Mass., 2nd edition,
2001.

[3] J. Flanigan. Nim, Trim and Rim. Working Paper, Mathematics Department,

University of California, Los Angeles, 1980.
[4] P. M. Grundy Mathematics and games. Eureka, 2:6−8, 1939.
[5] Y. Irie. \mathrm{p} ‐Saturations of Welters Game and the Irreducible Representations ofSymmetric Groups. in preparation.
[6] 入江佑樹.反転ニムゲーム.第32回代数的組合せ論シンポジウム報告集,pp. 14‐17,
June 22‐24, 2015.

[7] 川中宣明.フック構造をもつゲームとアルゴリズム.数学, 63(4):421-441 2011.
,[8]I. G. Macdonald. On the Degrees of the Irreducible Representations of Sym‐

metric Groups. Bulletin of the London Mathematical Society, 3(2):189-192 , Jan.
1971.

[9] E. H. Moore. A Generalization of the Game Called Nim. Annals ofMathematics,

11(3):93-94 1910.
,[10] 佐藤幹夫 (上野健爾記). あるゲームについて.第12回代数分科会シンポジューム

報告集,pp. 123‐136, 1968.
[11] 佐藤幹夫 (榎本彦衛記). Maya game について.数学のあゆみ, 15(1):73-84 1970.
,[12] 佐藤幹夫 (榎本彦衛記). マヤ

ゲームの数学的理論.数理解析研究所講究録,第98巻,pp. 105‐135, 1970.
[13] R. Sprague. Über mathematische Kampfspiele.

Tohoku Mathematical Journal,

First Series, 41:438−444, 1935.

[14] C. P. Welter. The Theory of a Class of Games on a Sequence of Squares, in Termsof the Advancing Operation in a Special Group.

(Proceedings), 57: 194‐200, 1954.

Indagationes Mathematicae