パズルの国のアリス

鏡の国はスパイ天国?(回答)

 まず各問題の答えだけを記すと,8駅の場合,答えは順に105通り,24通り,70通り,74通りである。

 最初の2つの問題は,少し考えるだけで簡単な組み合わせ問題に帰着されることがわかる。まず,最初の問題だが,スパイの区別はしないし,他の条件もないことから,拠点駅を2つずつ組み合わせる方法が何通りあるかを考えればよい。西ルーク駅と組み合わせるのは,他の7つの駅のどれでもよいので,その1つを選ぶ。するとまだ組み合わせていない駅が6つ残る。そのうちの一番西の駅を選び,さらに残った5つの駅の1つと組み合わせる。さらに残った駅から一番西の駅を選び,まだ残っている3つの駅の1つと組み合わせる。最後に残った2つの駅は自動的に対になるから,結局,組み合わせの総数は7×5×3×1=105通りだ。

 同じように考えると,一般に駅の数が2nだった場合,組み合わせのB総数が(2n−1)×(2n−3)×…×3×1と書けることがわかる。このように連続する奇数を次々に2n−1まで掛けていく演算は,組み合わせ論では(2n−1)!!と書かれ,頻繁に登場する。「二重階乗」などと呼ばれることがあるが,階乗操作を2度行うのではなく,整数を1つとばしに掛けていくのだ。

 第2問は,見た目は複雑そうな印象だが,冷静に考えると,計算的には最初よりさらに簡単なことがわかる。ポイントは,駅を西側(西ルーク駅からクイーン駅まで)と東側(キング駅から東ルーク駅まで)に2分割して考えることで,全スパイがそれぞれ互いに直接接触するための必要十分条件は,実は,全員が西側のどこかの駅から乗り,東側のどこかの駅で降りることだ。そうであれば,クイーン駅からキング駅までの間は全員が同じ列車に乗り合わせているから,互いにメモを交換できることは明白だし,逆に,もし西側の駅から乗り西側の駅で降りてしまうスパイが1人でもいたら,駅の数は西側も東側も4つずつなのだから,必然的に東側だけで乗り降りするスパイもいることになり,この2人には直接情報交換する機会はない。西ルーク駅から乗ったスパイが東側で降りるには4通りの駅が選べ,次には西ナイト駅から乗ったスパイが降りる駅として残りの3通りの駅が選べ,……という具合で,第2問の解は4×3×2×1=24通りとわかる。一般に駅数が2nの場合,n!になることは明らかだろう。

 おそらく,第3問,第4問の答えはそう簡単に答えは見つからないだろうが,8駅の場合,第1問の答えが105通りだから,それらを全部書き出してしまい,その中から条件に合うものを探すというやり方でも答えは得られる。70通り,74通りというのが正解だが,一般に駅数が2nの場合,どうなるかと考えるにはもう少し情報がほしい。

 そこでn=2,3,4,5の場合に各問題の答えを書き並べると次のようになる。

n=5の場合の全部で945通りを調べるのは根気が要りそうだが,それがなくともある程度の規則性は見えている。すぐ気づくのは第3問の答えが第1問の答えの2/3になっていることで,実は,それは一般に成立する。そのことを証明するのは容易ではないが,次のように考えるのがうまいようだ。

 駅数が2nの場合,先のように駅を西側と東側(8駅の場合,西ルーク駅からクイーン駅までとキング駅から東ルーク駅まで)に2分する。そして西側の一番東の駅A1(8駅の場合はクイーン駅)と対にする駅B1を選び,スパイ1に担当させる。B1の候補はもちろん2n−1通りある。次にA2を決めるのだが,B1が西側から選ばれた場合は,東側の一番西の駅(8駅ではキング駅)とする。B1が東側から選ばれた場合は,残っている西側の駅で一番東の駅(8駅では西ビショップ駅)とする。B2はさらに残っている駅から選び,A2とともにスパイ2に担当させる。これには2n−3通りある。こうしてA1B1A2B2,…と順次決めていくのだが,Ai+1は一般に次のように決める。それまでに決められた
2i個の駅が西側と東側からi個ずつ選ばれていたら,残った西側の駅のうち一番東にあるものをAi+1とし,西側の駅のほうが東側より多く選ばれていたら,残った東側の駅のうち一番西にあるものをAi+1とする。Bi+1は残った駅から任意に選び,Ai+1とともにスパイi+1が担当する。すると,Bn−2が選ばれた時点で,全部で(2n−1)×(2n−3)×…×5通りの選択が行われ,4つの駅が残ることになるが,それらを西から順にa,b,c,dと呼ぶことにしよう。Aiの決め方からすぐわかるように,これらの駅は,西側と東側に2つずつか,西側に1つで東側に3つだ。したがってaは西側にあり,cとdは東側にある。また駅A1,…,An−1 は,中央に近いものから優先的に選ばれていくから,すべてaとcの間にある。したがって,aを担当するスパイがcまたはdをも担当すれば,そのスパイはボススパイの役割を担える。反対に残り2人のスパイXとYの担当がa-bとc-dに分かれてしまったら,誰もボススパイになれないことを証明しよう。

 まず,このXとYの乗車区間には重なりがないので,どちらもボスになれない。そこでAjBjを担当するスパイj(1≦jn−2) がボスになれたと仮定しよう。bが西側にあったとすれば,Ajはbとcの間にあるので,Bjがどこにあろうと,スパイjの乗車区間は,XまたはYの乗車区間の一方とは重なることがない。そこで,さらにBは東側にあると仮定できる。スパイiが担当する駅はAiBiだが,BiAiより西にあれば担当が西向き,東にあれば東向きということにする。スパイjの乗車区間はXやYの乗車区間と重なるのだから,Ajはaとbの間にあり,Bjはさらに東にあるのでスパイjの担当は東向きだ。b,c,dがすべて東側にある場合を考えているのだから,少し考えればスパイn−2の担当は西向きだとわかる。ということは,jより大きい番号kで,スパイk−1の担当は東向きだが,スパイkの担当は西向きというようなものが存在する。これも少し考えればわかるが,k−1が東向きだからAkは西側にあり,Ajより後の番号を持つからAjより西にある。ところが,スパイjの担当は東向きで,スパイkの担当は西向きだから,この2人の乗車区間には重なりがないことになり,jがボスになれるということに矛盾する。

 こうして,ボススパイを作るには最後に残った4駅のうち,一番西のaを担当するスパイがbを担当すると駄目で,cかdならよいということだ。結局,そのための割り当て方の総数は(2n−1)×(2n−3)×…×5×2通りということになる。

 最後の誰も乗っていない区間がないように担当を割り振る問題は,その総数を簡単に計算できる式を見つけるのは難しいようだが,考え方はさほど大変でもない。誰も乗っていない区間がある場合,それがどこかで分類するとよい。西ビショップ駅とクイーン駅の間がそういう区間になる可能性はない。なぜなら,西ビショップ駅を含めそれより西の駅で乗り降りするスパイは延べ3人で奇数だから,西ビショップ駅を出て東に向かう列車に最低1人は乗っていなければならないからだ。同様に西ルーク駅–西ナイト駅,キング駅–東ビショップ駅,東ナイト駅–東ルーク駅の間も必ず1人は乗っているので,誰も乗っていない区間があるとすれば,それは西ナイト駅–西ビショップ駅,クイーン駅–キング駅,東ビショップ駅–東ナイト駅の間のどこかである。

 そこで,式

 7!!−1!!×5!!− 3!!×3!!−5!!× 1!!=66を考えよう。この式の中の一番右の5!!×1!!という項は,3人のスパイが西側6つの駅で乗り降りをし,1人のスパイが東側2つの駅で乗り降りする場合,つまり,東ビショップ駅–東ナイト駅間に誰も乗っていない場合を数えたもので,他の項も同様だ。それらを7!!から引けば誰も乗っていない区間がないような割り振り方の総数になりそうな気がするが,実はそう簡単ではない。そういう区間が2カ所にできる場合があり,それが二重に引かれるからだ。そこで,その分

 1!!×1!!× 3!!+1!!×3!!×1!!+ 3!!×1!!×1!!=9

を足し戻してやらねばならないが,今度はそういう区間が3カ所にできた場合が足しすぎになるので,その場合の

 1!!×1!!×1!!×1!!=1

を引き,結局66+9−1=74と正解が得られる。このように足し引きを繰り返す手法は,包除原理などと呼ばれ組み合わせ論では多用される。一般に2n駅の場合,この原理を用いれば,最後の問題の答えは

という式で書ける。各niは正の整数で,和はnniへの分割全体にわたるから,あまり計算しやすくはない。もう少し計算しやすい式もないではないが,あまり深入りするのも……と思うので,これ以上は読者の研究に委ねよう。

問題はこちらです