パズルの国のアリス

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

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

 着席順に何らかの戦略があると,客はその順に従って席に着くので,そのときどちらのナプキンを取るかだけを考えればよいが,この問題は,客の着席順という要因が加わることで複雑さが増している。

 まず,3人の場合を考えてみよう。最初の着席者が左右どちらのナプキンを取るかは,まったくでたらめなので,右を取ったと仮定しても一般性を失わない。次の客がその右隣に案内されれば(確率1/2),右のナプキンしか残っていないのでそれを取るしかない。3人目も同様なので,この場合は全員がナプキンにありつく。では2人目が最初の客の左隣に案内されると(確率1/2)どうだろうか?

 その客も右のナプキンを取れば(確率1/2),3人目もそうせざるをえず,誰もナプキンを失わない。だが,左のナプキンを取れば(確率1/2),3人目は自分の両側のナプキンを奪われて犠牲者となる。結局,ナプキンを失う可能性があるのは3人目だけで,その確率は1/2×1/2=1/4だから,平均では1/4人の犠牲者が出る。

 次に4人の場合だが,最初の客が右のナプキンを取ったと仮定してもよいのは同様である。2人目がその右隣に座った場合(確率1/3),その客には右のナプキンしか残されていない。この後の状況は,3人の場合に最初の客が座った後とよく似ており,確率1/4で4人目がナプキンを失う。では,2人目が最初の客の左隣に座った場合(確率1/3)はどうだろう? その客も右のナプキンを取れば(確率1/2),同様に確率1/4で4人目がナプキンを失う。また,その客が左のナプキンを取れば(確率1/2),確率1で4人目がナプキンを失う。最後に2人目が最初の客の向かい側(麻雀用語でいう対面)に座った場合(確率1/3)はどうだろう? その客が右のナプキンを取れば(確率1/2)誰もナプキンを失わず,左のナプキンを取れば(確率1/2)その左隣の客がナプキンを失う。結局,ナプキンを失う可能性があるのは1人だけで,その確率は

201506-a-img01

となるから,平均で11/24人が犠牲になる。

 5人以上の場合にもこの調子で分析していくのは,場合分けが多岐にわたり,すでに非現実的だろう。そこで期待値を求める場合の常套手段,すなわち,期待値の加法性に訴えることにしよう。具体的には,特定の客1人に着目し,その客がナプキンを失う確率を計算してみることにする。

 その客を0とし,その右に向かって1,2,…,左に向かって−1,−2,…と客に番号を振る。また,各客は着席したときに両側のナプキンが残っている場合にでたらめにどちらかを取ることになっているが,そういう場合にどちらを取るか,各客に癖があるとしても問題は変わらない。右を取る癖のある客を右利き,左を取る癖のある客を左利きと呼ぼう。客0の右側にいる最初の左利きの客をiとする。すなわち,客1,2,…,i−1は右利きで,客iが左利きとする。同様に客0の左側にいる最初の右利きの客を−jとする。各客が右利きか左利きかの可能性は半々だから,客0の周囲の配置が実際にそうなる確率は1/2ijだ。

 この場合に客0がナプキンを失うのはどういうときだろうか? 少し考えればわかるが,それは客iと客−jの癖の影響が伝わってきた場合だけであり,(客0自身を含めて)−j+1からi−1までの客の誰かが着席したとき,両側にナプキンが残っていて自分の癖を発揮すれば,その影響はブロックされ,客0のところまでは来ない。すなわち,客kの着席時刻をtk)とすると,

t(−j)<t(−j+1)<…<t(−1)<t(0)>t(1)>…>t(i−1)>t(i)

が成り立つ場合にのみ,客0はナプキンを失う。t(−j)からti)までの時刻を並べたとき,どういう順になるかについては(ij+1)!通りの可能性があるが,上のような順になるためには,最後の時刻t(0)の右側に来るi個の時刻を選べるにすぎないから,ijCiしかない。従って,実際に着席時刻が上のようになっている確率はijCi /(ij+1)!であり,ijについて総和を取ると,結局,客数が全部でn人の会食では,客0がナプキンを失う確率は

201506-a-img03

となる。さらにkijとおいて,整理すると

201506-a-img04

となる(最後の等号は2項定理から得られる)。この確率Pn)はどの客についても同じだから,全体では平均でnPn)人がナプキンを失うことになる。

 各客がナプキンを失う確率Pn)はnについて単調増加であるが,式からわかるようにnの増加とともに急速に収束する。その極限値は(2−√e2≃0.1234であるが,近似値でよいならPn)の式にn=10くらいを代入することで簡単に求まる。帽子屋にいじわるされた場合の値,約1/6≃0.1667に比べて,たいしてよくなっていないのを見ると,帽子屋を締め出すよりやはり全員にマナー教育をするほうが賢明なようだ。

 さて,上の極限値を元の式から直接求めるには,いささか面倒な計算と知識が必要なようだが,はじめからnが無限大に近づいた場合の極限値だけを求めるのなら,微積分を用いた次のような巧妙な計算方法がある。微積分計算に拒否反応のない読者のために簡単に紹介しよう。全客をある単位時間内に席に案内するのならば,各客の着席時刻は単位区間[0,1]内の独立で一様な乱数とみてよい。今,ある客の着席時刻をtとすると,そのとき自分の右のナプキンがすでになくなっている確率は,tの関数であり,それをpt)としよう。そういうことが起こるのは,その右隣の客の着席時刻をsとすると,tsであり,かつその右隣の客が座ったときに両側のナプキンが残っていた(確率1−ps))のに左を選んだ場合(確率1/2)か,その時点ですでに右側のナプキンはなかった(確率ps))ので 仕方なく左のナプキンを取った場合である。従って

201506-a-img05

が成り立つ。この方程式は比較的簡単に解け,pt)=et/2−1が得られる(この種の方程式を解くのがあまり得意でない人でも,これを上の式に代入して,正しく解になっていることは簡単に確かめられよう)。客が時刻tに着席したときに,左のナプキンがすでになくなっている確率も同じだから,結局,ナプキンにあぶれる確率はpt2である。最後に,各客が到着する時刻は区間[0,1]で一様な乱数だから,平均すれば

201506-a-img06

が,各客がナプキンを失う確率である。この積分によるアプローチはなかなか優れていて,たとえば,全部でn人の場合,一番最後に着席する客がナプキンを失う確率はPn)に似た式

201506-a-img07

で与えられることが,先と同様の論法で示されるが,この値は当然p(1)2=(√e−1)2≃0.4208に収束することなどもわかる。

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

問題はこちらです