パズルの国のアリス

ハートの女王とマハラジャの勝負(解答)

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

 表記の都合上,コイン投げで表が出る場合をH,裏が出る場合をTと表し(それぞれ英語のheadとtailの頭文字),HとTの列でコイン投げ結果の経緯を表すことにしよう。たとえば,HHTは,最初2回表が出て,3回目で裏が出た場合だ。

 ウォーミングアップ問題は,高校数学での順列・組み合わせ・確率の簡単な復習だから,多くの説明は要るまい。1回のコイン投げでHとTのどちらになるかは,どちらも1/2であり,各コイン投げは独立だから,長さ20のある特定のHT列が出る確率はどれも1/220だ。一方,収支が0になったということは,その列に含まれているHとTの数が10個ずつだということだ。そのような列は明らかに全部で20C10=20!/(10!×10!)通りある。したがって,求める確率は

である。

 次の問題は,通常の高校数学の範囲で解こうとすると少し難しいが,組み合わせ論ではお馴染みの数を使って答えられるので,ご存知の読者も多かろう。ベルギーの数学者の名前を冠したカタラン数Catn)というものだ。この数の定義の仕方はいろいろと考えられるが,一番,計算しやすい形で与えるならば

となる。さて,「20回目に収支が0になったが,途中は常にハートの女王の赤字だった」ということはHT列で考えると,その列を途中で左右に切り分けたとき,左の列は常にTのほうが多く,右の列はHのほうが多いということだが,そのような列の総数はCat(9)で与えられる。したがって,問題の条件付き確率は

だ。20回目で初めて赤字が解消されるようなHT列の総数が,どうしてCat(9)=18C9/10になるのかという点は後回しにして,この数が組み合わせ論でいかに頻繁に出てくるかについて,少し述べよう。実は,筆者の拙い紹介を読んでもらうより「カタラン数」というキーワードでインターネット検索をしてもらったほうが,はるかに多くの有用な情報が入手できるが,中には,カタラン数の解釈の仕方は100以上もあると書いてあるようなページもあるから,それが事実なら,カタラン数の定義の仕方も同様にたくさんあるわけだ。邦訳はされていないようだが「Catalan Numbers with Applications」(Thomas Koshy著,Oxford Univesity Press)という400ページを超える本もある。

 カタラン数の組み合わせ論的解釈で一番よく引き合いに出されるのは下図のような街路を通ってA点からB点へ行く最短ルートの総数だろう。下図の場合,答えはCat(5)=42だ。一般には,AとBが街路にして東西にも南北にもn単位離れている場合の答えがCatn)だ。

 この解釈から,先のHT列の総数がCat(9)に等しいことが直ちに出てくる。というのは,Hに南北の街路,Tに東西の街路を1単位ずつ対応させればよいからだ。条件より,最初はT(東西),最後はH(南北)であり,途中は(赤字が解消しないということにより)n=9の場合に上のような街路を進む場合と1対1に対応する。

 カタラン数のもう1つの代表的な解釈は,下図の左のような凸多角形を,中央や右に例示したように,対角線で三角形に分割する仕方の総数だ。凸6角形の場合,答えはCat(4)=14である。一般に凸n角形の場合,答えはCatn−2)になる。

 カタラン数と密接な関係を持つものには,さらに次のようなものもある。今a1a2a3−…−anという式を考えよう。この式の通常の解釈は(…((a1a2)−a3)−…−an)だが,括弧の入れ方,つまりどの引き算を先にやるかによって結果は異なる。このような括弧のない式への括弧の入れ方の総数はCatn−1)となるから,計算結果にも最大それだけのバラエティがある(実は,引き算の場合,生じうるバラエティは2n−2だけだが,もっと別の2項演算ならCatn−1)ということもありうる)。

カタラン数を導く漸化式も多い。たとえば,

などである。特に前者は,自然な組み合わせ論的解釈が可能だし,カタラン数が母関数として

を持つことも帰結される重要な式である。上の母関数において=(1−4x)1/2の部分をニュートンの2項定理によって展開すれば

となるので,Catn)=(2n)!/(n+1)!n!が得られるが,この計算はいささか面倒だし,母関数についての知識も必要なのでそれらに強い人への演習問題としよう。

 じつは,問題の列の総数が18!/(10!×9!)で与えられるということは,カタラン数やその母関数を持ち出さなくとも,ちょっと巧妙な考え方をすれば組み合わせ論的に証明できる。最後の問題を考えながら,このアイデアを説明しよう。最後の問題は「赤字3で始まって,17回コイン投げをしたあげく赤字4で終わった。途中一度も赤字が消えなかったならば,コイン投げの表裏の出方には何通りの可能性があるか?」というものだ。

 問題で述べているようにコイン投げの結果は,表が8回,裏が9回に違いない。そのようなHT列の総数を単純に数えると,結果は17C9(=17C8=24310)だが,この中にはHHHで始まるような列が含まれ,これは3回目で赤字を0にするから条件に適合しない。逆に言えば,このような不適合列がいくつあるか数えることができると,それを24310から引いてやれば答えが得られる。さて,巧妙な考え方とは次のようなものである。今,たとえばHTHHTHHHTTTTTHTHTというような列をとってみよう。この列はHを8個,Tを9個含むが,(赤で示した)7回目のコイン投げにより赤字が0になるので,適合しない。そこで,そこより後のTとHをすべて反転してみよう。上の例ならHTHHTHHTHHHHHTHTHとするわけだ(反転部位を青で示した)。この列にはTが5個とHが12個含まれているが,そのことは一般的に成り立つ。つまり,Hを8個,Tを9個含む列があり,途中で赤字が消える(HがTより3個多くなる)ことがあるならば,初めてそうなった時点から先ですべてのTとHを反転した列は,Tを5個とHを12個含む。これは簡単な算数だ。最初に赤字が消えた時点までのTの個数をtとおくと,その時点までのHの個数はht+3である。だから,元の列における,それより後のTの個数は9−tであり,Hの個数は8−h=5−tだ。ここでTとHを反転させれば,それらの個数が入れ替わるので,新しい列ではTの個数はt+(5−t)=5となりHの個数は(t+3)+(9−t)=12となる。だから,Hを8個,Tを9個含む列で途中で赤字を消すものがあるとし,それに上記のような変換を行うと,Tを5個,Hを12個含む列に変わる。ポイントはこの変換が可逆だということだ。逆にTを5個,Hを12個含む列があったとしよう。赤字3から始めても結果は黒字になって終わるので,必ず赤字が消える瞬間がある。その最初の時点から先でHとTを反転させると,その列はHを8個,Tを9個含む列に変わる。

 つまり,Hを8個,Tを9個含み赤字が途中で消えることがある列と,Tを5個,Hを12個含む列とは,1対1に対応するということだ。したがって,このような列の総数は17C12(=17C5=6188)であり,元の問題の答えは17C917C12=18122ということになる。

 一般に赤字rから始めてm回コインを投げ最終赤字がsで終わった場合,裏が出た回数はt=(msr)/2で表が出た回数はh=(mrs)/2だが,途中で赤字が解消されることがないという条件があると,同様な考察により,そのようなコイン投げの表裏の出方にはmCtmCtr通りあることがわかる。最初に裏が出て,20回目に表が出るまで,赤字が解消しなかったというのは,m=18,rt=1の場合に当たり,18C918C10=18!/(10!×9!)通りある。カタラン数Catn)の式もこの考え方で

と求めることができる。

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

問題はこちらです