パズルの国のアリス

給仕長・帽子屋のたくらみ(解答)

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

 

解答例最初の帽子屋の戦略では犠牲者は8~9人。3日目に厨房に下がってからも,席に1~52の番号を付け,「最初に4の倍数番,次に奇数番,最後に奇数の2倍番」の順で席を埋めていくと,7人以上の犠牲者が期待できる。

最初の帽子屋の戦略で,ある人Aが着席したときに,そこから最初の人の席まで右に空席がまだnあったとする。Aが右のナプキンを取った場合にそれらの空席に座る人で犠牲者になる人数の期待値をR(n),左のナプキンを取った場合の犠牲者の人数の期待値をL(n)とする。Aが右のナプキンを取った場合,次のBは1つ空けて席に着くのでBの右にはn-2の空席が残る。Bが左のナプキンを取ればAB間に座る人はナプキンがないが,Bがどちらのナプキンを取る か,その確率は半々だ。したがって,この状況を漸化式で書くと

R(n)=1/2×R(n-2)+1/2×(L(n-2)+1)

となる。Aが左のナプキンを取った場合,Bはすぐ隣の席に着くのでBの右にはn-1の空席が残る。今度は犠牲者は出ないが、Bが左右どちらのナプキンを取るかはやはり半々なのでL(n)=1/2×R(n-1)+1/2×L(n-1)が成り立つ。R(1)=L(1)=0,R(2)=1/2から初めて少し計算してみると

n 1 2 3 4 5 6
R(n) 0 1/2 1/2 3/4 7/8 17/16
L(n) 0 0 1/4 3/8 9/16 23/32

が得られる。トランプたち総勢52人の場合,最初の人が着席した状況で空席が51残っているから,R(51)まで計算すればよいが,だいたいの人数でよければ漸化式を利用してもっと簡単に計算できる。

まず,R(n)とL(n)の漸化式を見比べれば,L(n)=R(n+1)-1/2であることがすぐにわかる。これを代入してLを消去すると

R(n)=1/2×R(n-2)+1/2×R(n-1)+1/4

が得られる。R(n)がnにほぼ比例して増えることは,戦略の性質や漸化式から明らかなので,やや乱暴だが,R(n)をαnとおいて解いてみると,α=1/6が得られる。したがって,R(51)はだいたい51/6=8.5くらいと予測されるので,2晩目にナプキンを奪われた犠牲者は8~9人と考えられ る。厳密に漸化式を解くと

R(n)=n/6+(1+8/(-2)n)/18

が得られるが,この式を導くのは得意な人にお任せしよう。

厨房からヤマネに指示をするだけになると,あまりよい方法がないように思える。まず先に偶数番目の席を埋め,その後,奇数番席を埋めるくらいしか思いつかないかもしれない。その場合,左隣の人が右のナプキンを,右隣の人が左のナプキンを取ったときだけ,奇数番席の人はナプキンのない犠牲者となる。その可能性は1/4で,奇数番席は半分だから全体では1/8くらいの人が犠牲者となる。総勢52人ならば平均6.5人だ。

しかし,もう少し考えると帽子屋のベスト戦略は,冒頭に挙げたように,最初に4の倍数番,次に奇数番,最後に奇数の2倍番という順で席が埋まるように座らせることだとわかる。この戦略では平均で9/64が犠牲者となる。52人ならば7人以上が期待できる。

席に案内されたときに両隣がどちらも空席だった客を「孤立客」と呼ぶことにしよう(この後で隣に誰かが座っても,孤立客と呼ぶ)。孤立客は左右どちらのナプキンでも選べる。孤立客以外が席に着くときには,左右どちらかの席は埋まっており,ナプキンを自由に選べないことがある。しかし,ナプキンにあぶれることがあるのは両側がすでに埋まっている場合だけで,これを「危険客」と呼ぼう。孤立客の隣に後から誰かが座ったとしても,ある孤立客と次の孤立客の間には,いつも必ずちょうど1人だけ危険客が座ることになる。

孤立客と次の孤立客の距離がd,すなわち間にd-1の席があるとする。その間の危険客と左右の孤立客との距離をa,bとする(a+b=d)。この危険客は犠牲者となる可能性があるが,左の孤立客からすぐ左隣の客まで誰もが左のナプキンを使えば犠牲者にはならない。その確率は1/2aとなる。右も同様なので,この危険客が実際にナプキンにあぶれる確率は

(1-1/2a) (1-1/2b)=1-1/2a-1/2b+1/2d

である。

孤立客どうしがd離れているとき,d人ごとに1人の危険客がいる。こうして,総人数nがdの倍数であれば,犠牲者数の期待値は

(n/d) (1-1/2a) (1-1/2b)

であることがわかる。これが最大になるのは,d=4,a=b=2のときであるのは簡単に確認できる。実際,d=2,a=b=1の時はこの値はn/8だが,d=4,a=b=2のときは9n/64だ。

 

参考にした本:Peter Winklerによる次の2冊(ともに出版元はA K Peters, Ltd.)Mathematical Puzzles: A Connoisseur’s Collection(2004)Mathematical Mind-Benders(2007)ルイス・キャロルによる2冊(さまざまな翻訳本や注釈本が出ている)『不思議の国のアリス』『鏡の国のアリス』

 

 

問題に戻る

 

 

 

問題はこちらです