２００６年日本数学オリンピック予選　問題１０

解答者　松原　彩香　２００６年１１月

問題文

正十二面体のひとつの頂点Ｘをとる。一匹のアリがＸを出発し、正十二面体の辺上のみを歩き、Ｘ以外のすべての頂点をちょうど１度ずつ通過して、Ｘに戻ってきた。アリの歩いた経路として考えられるものは何通りあるか。ただし、回転で重なり合うような経路や、道順が逆になっただけの経路も、異なるものとして数える。

　解答

正十二面体のひとつの面に穴を開け、広げて平面状にすべての面を押し付ける。その際、各面の形はこの問題を考えるに際して関係ないので、右図�Tのようであるとしてもよい。ただし、元々の正十二面体の対称性から考えて、Ｘを出発した後、赤、青、黄のいずれに進むにしても、その後の経路の個数は同じであると考えられる。よって、青の方向に進んだ後の経路を、3倍すればよい。
図�Tで青の方向に進んだ後、図�Uのように、黄色と赤の2方向に進むことが出来るが、これも正十二面体の対称性から考えて、その後の経路の個数は同じである。 　よって、図�UでＸから青赤と進んだ後の経路を６倍すればよいことになる。 　また、青赤と進んだら、黄色の線は通ることが出来ない。よって、緑の線を通らねばならないことになる。
青赤と進んだ後は、図�Vのように、経路１と２に分かれる。この２つの経路については、対称性がないと考えられるので、順次考えていくことにする。次の図�Wでは、既に選ばれた経路は青で塗り、今から選ぶべき経路は赤と黄に塗ってある。また、既に選ばれた経路により通ることが出来なくなった線は灰色に、通らねばならなく成った線は緑に塗る。
図�Wを用いて経路がどのように決定されるかを説明する。図�Wは、Ｘから出発して図�Vでの青線を通り更に１を選択したところから始まる。ここで、図�Wのえかエを選ぶことになるが、ここではえを選んだものとする。まずあいを通ったことによりアが通れなくなる。すると、ａｂを通らなければならなくなる。次にいうを通ったことによりイが通れなくなる。すると、ｃｄを通らなければならなくなる。ａｃを通ったことによりウが通れなくなる。すると、ｅｆを通らなければならなくなる。うえを通ったことによりエが通れなくなる。すると、ｇｈを通らなければならなくなる。ｄｇを通ったことによりオが通れなくなる。すると、ｉを通らなければならなくなる。えを通ったことによりカを通るとＸに戻ってしまうので、カを通れなくなる。すると、ｊｋを通らなければならなくなる。これであいうえｋと通ってきて１と２を選択することになったが、いずれを選択しても、１通りしか経路が無いことが見て取れるだろう。１を選択した場合３回の選択で順次１１１と選んで経路が決定し、２を選択した場合３回の選択で順次１１２と選んで経路が決定したことになる。この選択のパターンを、図１１１，図１１２のように表していく。ただし、選択が行われているところには数字を書き、選択した経路は青で、選択されなかった線と結果として通れなくなった線を赤で、通らねばならなくなった線を緑で表現する。また、見た目で後一通りしかないと分かるところまでを表現する。

　１１１から２２２２２までの10通りがあるので、求める経路の総数は、１０×６＝６０通りである。

　補足

　２００７年度の新入生に、上図を与えすべての経路を見つけさせてみたが、９通りまでしか見つかられなかった。元々の解答は、正一二面体を上下２つに切って広げていたので更にややこしかった。