パズルの国のアリス

ハートの女王による継子立て(解答)

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

 この問題は継子立てという名で知られ,ヨーロッパではヨゼフス問題とも呼ばれる。最初の問題は,40個の印を丸く描き,誰が輪から外れていくか実際に調べることで簡単に答えが得られる。毎回,図を描くのが厄介であれば,次のような工夫をするともっとよいかもしれない。

 スペードのエースに番号0を振り,以降1,2,…と順次番号を振っていくと最後のダイヤの10は番号39になって,1周する。一般にn人の輪があり,1からkまでの数を何度も唱えて,k番を唱えた人を外していくとき,最後に残る人の番号をJkn)とするなら,nまたはkについての漸化式が求まれば,計算が機械的になる。というわけで,Jkn−1)の値からJkn)を求めることを考えてみよう。実はn人の輪というのはn+1人から始めて最初の1人が外された状態と考えることができる。違うのはそのとき振られている番号だけだ。n人のとき0番の人は,n+1人で始めたときはk番だったはずであり,同様にj番の人は,jk番だったことになる。全体が輪になっているので,より正確には,n+1で割った余りをとる必要があるから,実はJkn+1)=(Jkn)+kmodn+1)という漸化式が成立する(ここで,y mod xyxで割った余りを表す)。1人しかいない場合,もちろん番号は0だから,初期値Jk(1)を0としてJkn)の表を作ると下のようになる。

201401-a-img04

 表の7列40行目を見ると23だから,最初の問題の答えJ7(40)=23が得られ,この番号を持つ兵士はクラブの4とわかる。また,J7(41)=30だから,もう1人増えたときは番号30の位置が当たりになるので,2番目の問題では,アリスはクラブの10とダイヤのエースの間に入るのがよいとわかる。

 さて,上の漸化式を使う方法は,結局,地道にやるとn回くらいの計算が必要となる。そこで,まずk=2の場合に,もっと効率よくJ2n)を求める方法を考えよう。そのために1,2,1,2,…と番号を唱えていき,ちょうど1周したときの状況を考えてみる。最初の人数が偶数のときと奇数のときとで,やや状況が異なる。偶数の2n人の場合,奇数番号の人は輪から外れ,輪に残っているのは,0,2,4,…,2n−2番のn人となり,ちょうどn人の輪で始める場合と同じになる。ここで番号を振り直すと,2n人のときの番号は,明らかに振りなおした後の番号の2倍になる。したがってJ2(2n)=2J2n)という式が成立する。奇数の2n−1人の場合も,同様に奇数番号の人は輪から外れるが,最後の番号が2nなので次に外れるのは0番になる。よってその状況まで進めるとやはりn人が残るが,その番号は2,4,6,…,2nとなる。ここで番号を振り直すと,古い番号は新しい番号の2倍より2多くなる。よってJ2(2n+1)=2J2n)+2という式が成立する。これにJ2(1)=0という初期条件を加えることで,先のよりはかなり高速にJ2n)を計算する漸化式が得られる。実際,40人の場合でやってみると

 J2(1)=0,
 J2(2)=2×0=0,
 J2(5)=2×0+2=2,
 J2(10)=2×2=4,
 J2(20)=2×4=8,
 J2(40)=2×4=16

となり,J2(1),J2(2),J2(3),…と順次計算するより,格段に効率がよい。もっとも,漸化式J2n+1)=(J2n)+2)modn+1)による計算の場合でも,J2n)の値は通常は2ずつ増加していき,それがn+1に達したときに,modn+1)の効果が現れ0に戻ることに気づけば,効率的に計算することが可能だ。実際,少し考えればnが2のべき2mの形のときにJ2n)=0になることがわかるだろう。すると一般のnの場合,n以下の最大の2のべき2mをとり,n=2mr(0≦r<2m)とおけばJ2n)=2rとなることが,先の漸化式から容易に証明できる。

 では,k=3やk=4の場合にも,同様の速い計算法があるだろうか。k=2の場合にならって計算して,あえて式を一気に書き下せば,

 201401-a-img01

となる。201401_lcelx201401_rcelxの小数点以下の切り捨て,すなわち,xを超えない最大の整数を表し,またann mod 3=0,1,2に応じて0,3,3/2である。確かにこの漸化式では,J3(n)の値を計算するのに,nを元の2/3くらいの値に下げているので,逐次的にやるよりだいぶ速そうだが,こういう複雑な式はあまり歓迎されまい。

 そこでほんの少しだけ考え方を変えてみよう。1,2,3,1,2,3,…と繰り返し唱える代わりに,0,1,2,3,4,…と順に唱えていって,n mod 3=2すなわちn=3m−1の形の数を唱えた者を輪から外しても結果は同じである。例えばスペードのエースから8までが輪になって,これを行うと下の表のようになる。

 201401-a-img02

 表で−となっているのは,3m−1を唱えて輪から外されたことを示している。表は誰が外れたかが最後までわかるように22まで書いてあるが,実はゲーム自体は20を唱えたときが終わりで,次の21を唱えるべき兵士,すなわちスペードの7が勝者である。

 一般にn人ゲームでは3(n−1)を唱えることになった者が勝者になる。さて,いまp番を唱えた者がいるとして,pnならば,その人が番号を唱えたのが初めてであるはずはない。では,前に唱えた番号は何番だろうか。それをqとし,q=3mii=0,1)とおく(i=2だと輪から外されてしまうので,次に番号を唱える機会は来ない)。このときまでに,m人が輪から外れたはずであり,残っているのはnm人である。

 すると次にその人の唱える番号はqnmだから,これがpと等しい。よって3miqpnmであるが,これをmについて解くと,i=0,1よりm201401_lcelpn)/2201401_rcelとなる。従ってqpn201401_lcelpn)/2201401_rcelとなり,番号pを唱えた人が前に唱えた番号qを計算できる。勝者が3(n−1)を唱えることになるのは間違いないので,そこからその前の番号を順次計算していくことができる。例えばn=8の場合なら,3×(8−1)=21から始めて,19,16,12,6と計算していける。6<8だから,その前に番号を唱えたはずはなく,勝者の最初の番号が6だったことがわかる。

 同じ論法により,アリスの選んだ数がkならば,p0kn−1)から始めて,漸化式

 201401-a-img03

により,p1p2,…を順次計算していき,psnが達成されたところでJkn)=psが求まる〔k=2,n=2mr(0≦r<2m)の場合,この方法は実質的には0≦2n−2snなる2n−2sとしてJ2n)=2rを求める方法となっている〕。しかし,これはknに比べ小さい数でないと,あまり効率のよい方法とはいえないかもしれない。もっとよい漸化式,あるいはこの漸化式を速く計算する方法をご存知の読者は,おられるだろうか。

 最後の問題は,自分の最初の位置がjだったとして,Jk(40)=jとなるようにkが選べるかという問題である。答えはイエスなのだが,これを証明したり,そのようなkを実際に見つけるとなると相当の難問だろう。

 まず,比較的簡単なj=0の場合を片付けることにしよう。最初の人数をnとして,Lを1からnまでの整数の最小公倍数とする。n=40なら

  L=5342931457063200

である。巨大な数だが,kLとすれば,Jkn)=0である。なぜならkLn以下のすべての正の整数で割り切れるので,kを唱えるのはいつでも最後の番号の人となるからだ。つまり,n−1,n−2,…番の順に輪から外れていき,最後に残るのは0番になる。

 では,j≠0の場合はどうすればよいか。そのために,まずn以下の最大の素数をpとしよう。n=40の場合p=37であるが,ベルトランの仮説というのがあり,pn/2であることは証明されている。また,Lの定義からML/pは整数であり,Mpは互いに素であることがわかる。

 jpの場合を先にすまそう。その場合,kMの倍数でkjmod p)であるように選べば,Jkn)=jとなる。なぜなら,kp+1からnまでのすべての整数で割り切れるので,人数がp人になるまでは最後の番号の人が輪から外される。p人のとき外れる人は,kの決め方よりj−1番となる。ここで番号を付け替えると新しく0番になるのはj番の人であり,kは1からp−1のすべての整数で割り切れるから,前と同じ理屈で最後に残るのは新しい番号で0番,すなわち元はj番の人である。

 最後にjpの場合だが,j’n−1−jとすれば,j’pとなるので,上のやり方でJkn)=j’となるk’を計算できる。そこでkL+1−k’とすれば,kを使ったときは,k’のときとは対称的に人が外れていくので,最後に残るのはj番となる。例えばjn−1の場合,k=1とすれば,0番から順に外れていき,最後に残るのは当然n−1番になる。

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

問題はこちらです