パズルの国のアリス

園遊会でのゲーム(解答)

坂井 公(筑波大学) 題字・イラスト:斉藤重之

 どちらのゲームも,かなり古くから知られているものだ。似て非なるゲームだが,関連がありそうな戦略を持つので一緒に紹介してみた。

 まず,最初の女王たちのゲームであるが,これは,別名ワイトホフ(W. A. Whythoff,オランダの数学者)のゲームと呼ばれているもので,組み合わせゲーム理論を扱った多くの書物に記載がある。最初にお詫び申し上げるが,女王たちによる説明とその後の数学的な説明とでは,ルールにわずかに食い違いがあった。女王たちの説明では目標の座標から遠ざかる動きができないだけだから,たとえば(0,4)→(1,3)とか(0,4)→(−1,3)とかいう動きは可能と考えられる。ユークリッド距離では4=√16→√13で確かに減少しているからだ。一方,その後の数学的な説明では,両座標値はどちらも,増加することや負の値をとることが許されないのでこのような動きは禁じられる。やや混乱を招く記述だったが,以下ではルールとして数学的説明のほうを採用させていただこう。ワイトホフのもともとのルール設定でもこの後者の説明が正しい。

 さて戦略だが,実は,先月号の解答とも深く関わっている。先月号の解答で一松信先生からのお便りとご著書について触れたが,その著書とは『石とりゲームの数理』(森北出版,POD版が出ている)のことだ。その中で一松先生は「チャヌシッツィ」という名でワイトホフゲームの変形の1つを扱っておられ,その戦略と先月号解答中の「レイリーの定理」(著書の中での呼び名はヴィノグラドフの定理)との関係についても述べておられる。他にも,佐藤文弘氏の『石取りゲームの数学』(数学書房)など,このゲームに触れた書物はあるので,詳しいことを知りたければ参考にされるとよい。

 すぐにわかるように,女王たちがいる座標が(0,n),(n,0),(nn)(n>0)の場合,先手は1手で(0,0)に行って勝つことができる。ということは,座標(1,2)と(2,1)は,そこから先手勝ちの座標にしか行けないので後手勝ちだ。以下,グラフ用紙を使って,各座標を順次つぎのように「後手勝ち」と「先手勝ち」に分類していくことができる。まず,座標(0,0)のマス目に○をつけ,そこに1手で行ける全マス目に×をつける(下図左)。次にまだ○×をつけていない一番左下のマス目に○をつけ,そこに1手で行けるマス目に×をつける(下図右)。

201511-a-img01 201511-a-img02

 こうして,まだ印のない一番左下のマス目に○をつけ,そこに1手で行けるマス目に×をつけるということを繰り返すと,下図が得られるが,この図で○のマス目が後手勝ちで,×が先手勝ちであることは,言うまでもあるまい。

201511-a-img03

 従って,現在×(先手勝ち)のマス目にいるなら,そこから1手で行ける○(後手勝ち)のマス目が存在するから,そこに進めばよい。たとえば(4,6)からなら左下の(3,5)へ進めばよい。また(4,8)ならば1つ下の(4,7)へ,(5,9)なら(5,3)まで下へ一気に6マス進めばよい。以後の動きも簡単だ。○のマスから1手で進めるのは×のマスばかりだから,さらにそこから,また○へ進むようにしていれば,自然に勝利に導かれる。

 従って上のような○×表を前もって作っておけば,必勝戦略を持つ側は,さほど苦労せずに勝つことができるが,盤面がもっと広くて,たとえば座標(1000,2000)からはどう動けばよいかというと,表を作るのもかなり煩雑な作業となる。だが,なんとなく見て取れるように表の中の○の配置は,大体だが,原点を通る2本の直線上に分布している。これは偶然ではない。当然だが,表の作り方から縦横や右上がり斜め(傾き1)の直線上に2つの○が来ることはない。その条件を守りながら,左下から順に○を詰めていくとなんとなく直線的になりそうだとは想像できよう。

 この○が配置される後手勝ちの座標(xy)がどうなっているか,数学的な解答を与えよう。これが第2問への答えになる。いささか天下り的ではあるが,iを正の整数とし,ϕを黄金比(√5+1)/2≃1.61803として,pi=⌊iϕ⌋と定義する(⌊x⌋は,xの小数点以下の切捨て,すなわちxを超えない最大の整数を表す)。少し計算してみると,p1=1,p2=3,p3=4である。またqi=⌊iϕ2⌋と定義する。たとえばq1=2,q2=5,q3=7である。実はpiがわかればqiは簡単に計算できる。なぜなら

qi=⌊iϕ2⌋=⌊i(ϕ+1)⌋=⌊iϕ⌋+ipii

だからである。ここで整数の集合PQP={p1p2p3,…},Q={q1q2q3,…}と定義すると,PQ=∅,PQ={1,2,3,…}となる。すなわち,すべての正の整数がPQの一方にのみ属する。これがなぜかという点で,先月号の解答にあるレイリーの定理が関わってくる。簡単な計算でわかるように1/ϕ+1=1/ϕ2=1であり,ϕϕ2も無理数だからだ。よって,先月号で述べたように,tを正の整数とするとtt+1の間にはiϕ型かiϕ2型の数値xが唯一つだけ存在し,t=⌊x⌋となる。

 さて,上の表を見てもらえばわかることだが○のついている座標は,ある正整数iについて,(piqi)か(qipi)の形をしている。その事実を厳密に証明するのは,かなりの紙面を要しそうなので,ここではその事情を説明するポイントだけに触れて,あとは自分で考えていただくのがよいだろう。一松先生や佐藤氏の本には丁寧な説明があるので,それを参照していただいてもよい。

 先のように表を○×で埋めていって(pq)に○がつけば,(qp)にも○がつくことは操作の対称性から明らかだ。証明は基本的には数学的帰納法で進む。今,順次○×表を埋めて行って

(0,0),(p1q1),(q1p1),…,(pnqn),(qnpn)

に○がついていると仮定し,次に○がつくのはどこかを考えてみよう。その座標を(pq)と(qp)とすると(pqと仮定する),○が2つ縦横に並ぶことはないからpは0,p1q1,…,pnqnのいずれとも異なることがわかる。そのような正の整数で最小のものがpの候補になる。すべての正の整数が集合PまたはQの一方のみに属することより,それはpn+1だとわかる。では,次にqはどうだろうか? ○が斜め方向(傾き1の直線上)に2つ並ぶこともないから,qpは0−0=0,q1p1=1,…,qnpnnのいずれとも異なることがわかる。よってqpn+1すなわちqqn+1が予想され,実際,(pn+1qn+1)と(qn+1pn+1)とがまだ○×のついていない一番左下のマス目であることを示すのはやさしい。

 こうして,後手勝ちのマス目は,(0,0)を含めて非負整数iにより(piqi)または(qipi)の形の座標を持つことがわかった。では,このゲームで先手勝ちのマス目(mn)にいた場合,次の1手はどうすればよいだろうか。これは基本的には簡単な問題だ。そこから行けるマス目で座標(piqi)または(qipi)を持つものを探し,そこに移動すればよい。具体的に述べよう。mnなら一気に(0,0)へ進めばよい。mnなら対称性によりmnと仮定してよい。inmとする。pimなら斜めにmpiマス進めば(piqi)に到達する。pimなら,そこは後手勝ちのマス目なので,適当に進み相手のミスを期待するしかない。mpiなら,mPmQか調べる。mPならmpjなるj(ji)が存在するので,縦にnqjマス進めば(mqj)=(pjqj)へ到達できる。mQならmqjなるjが存在するので,縦にnpjマス進んで(mpj)=(qjpj)へ到達できる。この「mPmQか」という判定は,いささか難しく思えるかもしれないが,表を持っていてもよいし,次のような計算でもできる。マス目(1000,2000)にいる場合を例としよう。i=2000−1000=1000だから,p1000=⌊1000ϕ⌋=1618で,m=1000<1618だから1000∈Pか1000∈Qかを判定する必要がある。1000/ϕ≃618.03かつ1001/ϕ≃618.65だから,618ϕ<1000かつ1001<619ϕにより,1000=pjなるjは存在しない。逆に1000/ϕ2≃381.97かつ1001/ϕ2≃382.35だから,1000<382ϕ2<1001により1000=q382である。よって(q382p382)=(1000,618)へ進むことで先手は勝てる。

 mPmQかについては別の判定法もあるので,触れておこう。それはフィボナッチ数を利用するものだ。F1=1,F2=2,Fn+2Fn+1Fnで定義される数Fnをフィボナッチ数と呼び,黄金比ϕと密接な関係があることを読者はご存知であろう。一例を挙げるとFn√5=ϕn+1+(−1)nϕn−1である。実際に少し計算してみると,F3=3,F4=5,F5=8,F6=13,F7=21,F8=34,…などとなる。任意に与えられた正の整数をフィボナッチ数の和に分解することを考える。30を例にとる。まず,30を超えない最大のフィボナッチ数を求めるとF7=21である。そこで30=F7+9と分解する。次に,残った9を超えない最大のフィボナッチ数F5=8をとり30=F7F5+1とする。さらに残った1はそれ自身フィボナッチ数F1だから30=F7F5F1となり分解完了だ。他の例をいくつか挙げると,5=F4,10=F5F2,40=F8F4F1,1000=F15F6=987+13などがある。これをフィボナッチ分解と呼ぶことにする。ある数のフィボナッチ分解には,FnFn−1というような連続する2つのフィボナッチ数が出てこないという特徴がある。なぜなら,分解にFnFn−1というような部分が現れるなら,(Fn+1FnFn−1だから)分解の定義によりその部分はFn+1という形になっていなければならないからだ。

 このフィボナッチ分解とmPmQかの判定とに妙な関係があるのだ。mをフィボナッチ分解してmFpFq+…+Ftとなったとする。気づきにくいが,この最後の項Ftの添え字tが偶数であることがmQであるための必要十分条件である。そのことを短く厳密に証明するのは困難に思えるので,ここでは読者にとって多少ヒントになるようなことを述べるにとどめよう。tが偶数の場合,mqjQと対になるpjのフィボナッチ分解は,各添え字を1つずつ下げて,Fp−1Fq−1+…+Ft−1で与えられる。当然,最後の項Ft−1の添え字t−1は奇数となり,pjQであることとつじつまが合う。また,jはさらに1つ添え字を下げてjFp−2Fq−2+…+Ft−2となる(ここでt=2の場合,最後の項がF0となることを気にされる読者がおられるだろうが,フィボナッチ数の定義を延長してF2F1F0すなわちF0=1と考えればよい)。上の例で確認すると,m=30=F7F5F1の場合,F1の添え字1が奇数だから30∈Pで,実際30=p19であり,q19F8F6F2=34+13+2=49かつ19=F6F4F0=13+5+1である。また,m=1000=F15F6の場合,6が偶数だから1000∈Qで,実際1000=q382だ。さらにp382F14F5=610+8=618,382=F13F4=377+5である。m=5,10,40の場合も同様なので,確認されたい。

 従ってmをフィボナッチ分解することでmPmQかは判定できる。これがm/ϕのような計算をするより簡単かどうかはわからないが,たとえば座標(F2i−1F2i)は後手勝ちのマス目だというような知見がただちに得られる。また,フィボナッチ分解は,iからpi=⌊iϕ⌋やqi=⌊iϕ2⌋を計算するのにも利用できる。i−1のフィボナッチ分解をFpFq+…+Ftとすると,piFp+1Fq+1+…+Ft+1+1,qipiiFp+2Fq+2+…+Ft+2+2となるからだ。

 双子のゲームについてはなるべく簡単に済まそう。まず,このゲームについてもルールを誤解させたかもしれないことをお詫びしたい。まっすぐにゴールへ向かうということを筆者は意図していたのだが,ジョウロを持って斜めに動いても,ゴールに近づくことはありうる。おそらく,そういう動きが可能だと誤解した人はおられないと思うが,そう誤解してかえって面白い結果に辿り着いた読者がおられれば連絡をいただけると幸いだ。

 さて,双子のゲームでは,まっすぐにゴール(座標0)に向かうしかないとしよう。従って座標は1次元で考えればよく,女王たちのゲームのように2次元ではないので,その分は簡単になる。逆に,今度は前の1手で進んだマス数が次の手を決める因子として入り込むので,その分は複雑化している。まず,一気にゴールまで行ければ別だが,そうでない場合,ゴールまでの残りマス数の1/3以上を進むと,次に相手にゴールまでいきなり進まれて負けになることに気がつく。ということは,そういう手しかない初期位置の座標1,2,3は後手勝ちのマスだ。4は,そこから3に進むことで勝てるので先手勝ちだ。このように順次考えていくと,5は後手勝ち,6と7は先手勝ち,8は後手勝ち,9と10は先手勝ちである。もうパターンが見えてきただろう。そう,フィボナッチ数の座標を持つマス目が先手勝ちのようだ。

 ここで双子のゲームでの最初の問題を考えよう。6からは1マス進んで後手勝ちのマス5に行けばよい。10からは2マス進んで8に行けばよい。12からも4マス進んで8に行けばよい……と考えたところで,ふと立ち止まる。確かに8は後手勝ちのマス目だが,そこから一足飛びにゴールへは行けないことが条件だった。ところが,最初に4マス進むと,次は8マス進んでゴールに着くことが可能になってしまう。かといってもっと近い後手勝ちのマス目はない。では12が先手勝ちと予想したのは間違いだろうか? そこで,少し冷静になって考え直してみると,12からは11へ進む手を思いつく。相手がそこからは進めるのは高々2マスだから,その後に8へ進めばよい。結局,マス目12は先手勝ちだ。

 さて,そろそろ後手勝ちの場合の特徴づけと先手勝ちの場合の戦略を,先のフィボナッチ分解を援用してズバリ述べてしまおう。現在の座標値をmとし,そのフィボナッチ分解をFpFq+…+FsFtとしよう。このときFtマス進んでm′=FpFq+…+Fsに行くことができれば先手勝ち,そうでなければ後手勝ちである。先手勝ちの場合の次の1手はもちろんFtマス進むことだ。従って,初期位置がFt(すなわちフィボナッチ数)の場合,(Ftマス進むことは禁じられているから)後手勝ちであり,それ以外の初期位置は先手勝ちということになる。上の後手勝ちの局面の特徴づけの証明の詳細は省略するが,ポイントは,フィボナッチ分解では連続する2つのフィボナッチ数が出てこないこと,stより2以上大きいとFs>2FtだからFtマス進んだあとにFsマス進むという動きができないことだ。あとは自分で考えて,納得していただけるだろう。

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004),
Mathematical Mind-Benders(2007) P. Winkler。
邦訳は『とっておきの数学パズル』(2011年),『続・とっておきの数学パズル』(2012年),ピーター・ウィンクラー著,坂井公・ 岩沢宏和・小副川健訳,日本評論社。

問題はこちらです