第349問の解答


問題[場合の数]

【元の問題】

算チャレ小学校も新学期が始まりました。

マサル先生クラスは、20人学級です。始業式の日、マサル先生が「友だち何人いますか?」という質問を生徒にしたところ、全員が「3人!」と答えたそうです。

そこで、マサル先生が生徒のトモエさんに、「じゃあお友だち1人紹介してください。」と言うと、トモエさんはツヨシ君を紹介しました。マサルさんがツヨシ君に「じゃあトモエさん以外のお友だち1人紹介してください。」と言うと、マサヒコ君を紹介しました。これをずっと続けたところ、最後トモエさんが紹介されて、全員1回ずつ紹介されたことになったということです。

では、このクラスで同じようにトモエさんから順に友だち紹介していって、全員1回ずつ紹介されて最後にトモエさんにかえってくるような「紹介順」は何通りあるでしょうか。ただし、ある紹介順と完全に逆順になっているものも、それぞれ1通りと数えるものとします。

【解答例で考えた問題】

友達関係グラフで表し、生徒友人関係を結ぶで考えることにします。
友達関係が、正12面体となっている場合について、紹介順の個数を求めて下さい。


解答例

マサルさん、nobuさん、中村明海さん、トトロ@Nさん、むらかみさん、Taroさん、たかまつ ろろさん、高橋 道広さん、まるケンさん、Miki Sugimotoさん、ずぱいさん、 他

生徒の友人関係を図(グラフ)で表したときに、生徒「点」友人関係を結ぶ「辺」で表すことができます。
本問では、「点の数20各点から出ていく辺の数は全て」という条件を満たすグラフを考えることになります。
このとき、「紹介順」は、「全ての点一度ずつ通るように辺をたどり元の点に戻る」という、いわゆるハミルトン閉路(向き有り)のを求めることに帰着されます。

ところが、グラフパターンによってハミルトン閉路は異なるので、一定の個数になるわけではありません。
例えば、下図のケース1では6通りケース2では128通りになります。

まるケンさんがプログラム全てのケースについて求めてみると、6から84までの偶数全部と、8896112128の個数になるパターンがあるようです。

参考図1

今回の問題について、出題者の意図は、「友達関係グラフ正12面体となるケース」を想定していたようです。
従って、以下では、正12面体ケースに限って考えることにしましょう。
また、閉路向きはとりあえず無視することにして、あとから2倍することにしましょう。

正12面体頂点の数20個各頂点から出ていく辺の数は全て」だから、確かに題意を満たすグラフになります。

参考図2

上記、2つのパターン正12面体ハミルトン閉路になっていますが、実は本質的な(回転移動などを除く)パターンは、この2通りしかないことが知られています。

以下では、この事実について考えてみましょう。

参考図3

ハミルトン閉路によって、正12面体表面2つの領域に分割されます。
一つの領域に属する(正5角形)は、同じ領域に属する他の面3個以上接することはありませんので、帯状をしていることになります。

また、領域に含まれる面の個数によって、周囲にある辺の個数は上記のように一意的に求まります。
ところが、ハミルトン閉路となるには、辺の個数頂点の個数20個となる必要がありますので、面の個数はそれぞれ6個ずつに分割されることになります。

さて、6個からなる帯状の領域で、どのようなパターンになるかを、次のように考えてみます。
すなわち、端の面から次の面へ進んだあと、それ以降の面へは、左へ進む右に進む2通りしかありません。
従って、最大2416通りとなりますが、を置き換えることにより、の場合だけ考えることにします。

参考図4
(正12面体を平面に展開した図。外側も1個の面になっている。)

  • 4個続く場合 ・・・ 元の面に接することになり不可

  • 3個の場合 ・・・ いずれも元の面と接することになり不可

  • 左=右=2個の場合 ・・・ がそれぞれ連続するケースのみOK

従って、左左右右または右右左左2ケースのみということが分かります。

では、以上の事実にもとづいて、いよいよハミルトン経路数を求めてみましょう。

参考図5

正12面体のあるとします)を固定して考えます。

を含む領域について、が端から数えて何番目の位置にあるかは、6÷2=3通りとなります。
また、から進む帯の方向辺の数5通りあり、さらに帯のパターンは上記2通りなので、
 合計=3×5×2=30通り
と分かります。

最後に、閉路の向きを考えて、30×2=60通りと求まります。

: 60通り

以上

(参考)

正多面体を解く」(一松信著:東海大学出版会)によれば、ある頂点からハミルトン閉路の辺に沿って進むパターンは、頂点に来るごとに左右どちらかに進むかで考えると、
 左左左左右右右右左右左右(これを2回反復)または右右右右左左左左右左右左(これを2回反復)
のいずれかになるようです。

残念ながら、この証明が記載されてなく、少し考えても思いつきませんでしたので、上記解法を考えてみました。

なお、ハミルトン閉路正12面体4色塗り分けとは関連しています。
下図のように、ハミルトン閉路で分割された2つの領域を、それぞれ2色を使って交互に塗り分けていくと表面全体4色で塗り分けられています。
逆に、4色で塗り分けられたときに、そのうちの2色ずつをとった2つの領域は、それぞれ閉じられた領域になっていて、分割の境界線がちょうどハミルトン閉路になっています。

参考図6


(その他の解法)