パズルの国のアリス

アリスとグリフォン,マジックに挑戦!(解答)

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

 

解答例グリフォンがアリスに情報を伝える手段は,行進の順序しかない。4人の順列は4!=24通りしかなく,アリスから見れば4人以外の48人の誰もがリーダーの可能性があるから,何かのズルをして別に1ビットの情報を渡さない限り,このマジックは不可能に見える。カギは,5人から誰をリーダーにするかをグリフォンが決めていい点にある。

このマジックをやる上で一番簡単な方法を紹介しよう。観客が選ぶトランプは5人だから,そのうち2人は必ず同じスート(マーク)になる。その2人のランク(番号)をxとyとする。ランクは,A→2→……と続き,Kの次はAにつながって循環していると考えると,xとyはどちらかの方向に最大でも6隔たっているだけだ。

xがその隔たりで見て“上”とすると,グリフォンはxをリーダーに選び出し,行進の先頭をyにする。さらに残りの3人の並び順を利用して,アリスにyからxへの隔たりを伝えるのだ。3人の並び順は6通りあるから,それぞれに1~6を対応させておけばよい。

例えばトランプの大小順を,♣A<♣2<…<♣K<♢A<…<♢K<♡A<…<♡K<♠A<…<♠Kと決めたとする。そして,3人の並び順が「小中大」 ならば隔たり1を表し,「小大中」は2,「中小大」は3,「中大小」は4,「大小中」は5,「大中小」は6を表すとアリスとグリフォンで申し合わせておく。これで,グリフォンは選び出したリーダーの情報をアリスに完全に伝えることができる。

イラストのように残りの3人が♡6,♠3,♢9と並ぶのは「中大小」の順に相当する。これは,隔たりが4であることを示しているから,先頭が♣2ならば,リーダーは♣6とわかる。

 

 

このマジックの仕組みには,情報量的に多少ゆとりがある。実際,もし最初に選ばれた5人に4種類全部のスートが含まれていなかったら,リーダーの選び方には少なくとも2通りの選択肢がある。例えば,最初に選ばれた5人が♣2,♣K,♢8,♢K,♡Aだとしたら,グリフォンは,リーダーを♣2と決め, ♣K,♢8,♡A,♢Kの順(小大中だから隔たりは2,Kより2上の♣)に行進させても,リーダーを♢Kにして, ♢8, ♡A, ♣2, ♣K(大小中だから隔たりは5。8より5上の♢)の順に行進させてもよい。

 

何人まで可能か

5人からリーダーを1人選ぶ場合,最大何人の組まで扱えるのだろう。実は,この問題の52人よりずっと多く,最大では124人の組まで扱える。それより多いとうまくいかないことは,次のように考えると納得できる。

観客が選んだ5人のうち,4人の行進を見て,残りの1人がわかるということは,結局5人全部がわかるということだ。n人の組から5人を選ぶ選び方は,nC5=n!/〔5!(n-5)!〕通りある。一方,グリフォンがアリスに渡せる情報は,4枚のカードの順番によるものだけだとすると,その可能性は n(n-1)(n-2)(n-3)しかない。ゆえにマジックを確実に行うには

n(n-1)(n-2)(n-3)≧nC5

すなわちn≦124である必要がある。もっと一般化すると,観客がk人を指名する場合に,同じようなマジックを確実に行うには,母数nはk!+k-1以下であることが必要だ。

もちろん,これは「必要だ」というだけで,実際にアリスとグリフォンの間の通信の仕組みを作らないと十分とはいえない。今,n人の集合Cを使ってこのマジックをやるとしよう。

これを成功させるには,Cから選んだk-1人の順列(u1, …,uk-1) に対して,別の人f(u1,…,uk-1)∈Cを割り当てる写像fで,グリフォンの立場からすると,次のような性質を持つものを見つけなければならない。

k人からなるCのどの部分集合Sに対しても,順列(u1,…,uk-1)を見つけてS={u1,…,uk-1,f(u1,…,uk-1)}となるようにできる。

このような写像は実際に設計できるから,124人の人を使ってこのマジックをやることもできるが,一般的な解は後回しにして,k=3の場合を特に考えてもらおうというのが,8人のポーンでの問題だ。3!+3-1=8だから,これはぎりぎりで,観客が指名するのが3人の場合,ポーンがこれより も多いとマジックは成立しなくなる。

さて8人の場合は,例えば,次のような仕掛けなら,比較的簡単で覚えやすいだろう。ポーンに番号を振り,8番の次は1番へ循環すると考える。行進するのは2人だから,アリスは,前のポーンから後ろのポーンまで番号が上方向にいくつ隔たっているか数える。

・隔たりが3以下なら後ろのポーンの次の次の番号を答える。
・隔たりが4以上なら前のポーンの次の番号を答える。例えば,前が7で後ろが4なら,上方向への隔たりは5となり,アリスは8と答える。リーダーを選ぶグリフォンの戦略は例えば次のようになる。
・指名された3人の中に番号が連続するペアA→Bがいて,3人目Cがペアの上の番号Bから上へ3以上隔たっていれば,グリフォンはBをリーダーと決めA→Cの順に行進させる。
・そうでなければ,番号の隔たりが2のペアA→Bで,3人目Cがペアの上の番号Bから上に3以上隔たっているものを探し,Bをリーダーと決めC→Aの順に行進させる。

先の例では,選ばれた3人は「4,7,8」だが,7→ 8 は連続し,8→ 4 は隔たり4(3以上)だから,A,B,Cは順に,7,8,4となる。

観客が選んだ3人が「3,5,7」の場合を考えよう。連続する番号のペアはない。3→5 は隔たり2だが5→7も隔たり2(2以下)だ。一方7→3は隔たりが4 (3以上)だから,A,B,Cを5,7,3とすれば第2の場合に当てはまる。そこでグリフォンは7をリーダーと決め,3→5と行進させる。

アリスは3→5の隔たりが2(3以下)だから5の次の次の7を答える。

選ばれたのが「1,7,8」の場合,7→8は連続しているが8→1の隔たりも1(2以下)だから,A,B,Cを7,8,1としても,最初の場合には当てはまらない。しかし1→7の隔たりは6(3以上)だから,A,B,Cを8,1,7とすれば,最初の場合に当てはまる。そこでグリフォンは1をリーダーと決 め8→7と行進させる。アリスは8→7の隔たりが7(4以上)だから8の次の1を答える。

アリスの関数が上述のf(u1,u2)の性質を持つことの確認は読者への宿題にしておこう。

 

一般式で挑戦!

上のように覚えやすい仕掛けではないが,一般のn=k!+k-1の場合でもマジックは可能だ。例えば,次のような方法があり,十分な計算練習を積んでおけば実行できるだろう。

先と同様にn人全員に番号を振っておく。グリフォンは,観客が指名したk人の番号を合計し,kで割った余りを求める。それがjであれば,小さいほうから j+1番目の番号の人をリーダーにする(すなわちj=0なら番号が最小の人,j=k-1なら最大の人がリーダーとなる)。

残りのk-1人を番号順に並べたときc1,c2,…,ck-1になったとする。またその合計をsとする。リーダーの番号xがc1より小さいなら,その決め方よりx+sをkで割った時の余りは0となる。これをx+s ≡0(mod k)と書く。また,ck-1 < x だとしたらx+s≡k-1(mod k)であり,ci<x<ci+1だとしたらx+s≡i(mod k)だ。

アリスから見て,リーダー候補は行進しているc1,c2,…,ck-1の人以外の全員となるが,この人たちに小さい順に1から番号を振り直すとしよう。振り直したリーダーの番号をyとすると,y+s ≡0(mod k)が満たされる。そのような番号yを持つ人は全部でk!/k=(k-1)!人いる。そこでこの(k-1)!人のうち誰が(何番目が)リーダーであるかを グリフォンはc1,c2,…,ck-1の行進順で示せばいい。

k=5,n=124のときに,単純な辞書式順序を使った場合を例として挙げよう。例えば観客が6,17,40,99,110を選んだとする。6+17+ 40+99+110=272で,5で割ると余りは2だから,グリフォンは3番目に小さい40をリーダーに決める。そして6,17,99,110を除いた人 に番号を振り直すと40の番号は38となる。行進する4人の番号の和は232なので,y+s=y+232≡0(mod 5)となる番号yを考えればよい。これが成り立つ番号は小さい順に3,8,13,…,113,118があるが,38はこのうちの8番目になる。

行進する4人を番号の小さい順に①②③④とすると,その並べ方の順列は24通り。辞書式に並べると8番目が②①④③になることを利用して,この順番,す なわち17,6,110,99の順に行進させることで「リーダーは8番目」であることをアリスに伝える。アリスは,この計算を逆にたどって,振り直した番 号が38番の人,すなわち(6番と17番が行進した人の中にいるので)もともとは40番がリーダーであると見抜くことができる。

n<k!+k-1の場合でも,上の仕掛けは,変更なしでそのまま使える。

 

参考にした本:Peter Winkler のMathematical Puzzles: A Connoisseur’s Collection (2004)とMathematical M ind-Benders (2007)。ともに出版元はA K Peters, Ltd.ルイス・キャロルによる『不思議の国のアリス』『鏡の国のアリス』

 

 

問題に戻る

問題はこちらです