正n角形とその外接円をあわせた図形をFとする。F上の点Pに対して、始点と終点がともにPであるような、図形Fの一筆がきの経路の数をN(P)で表す。正n角形の頂点をひとつとってAとし、a=N(A)とおく。また正n角形の辺をひとつとってその中点をBとし、b=N(B)とおく。このときaとbを求めよ。
注：一筆がきとは、図形を、かき始めから終わりまで、筆を紙からはなさず、また同じ線上を通らずにかくことである。
まずaを求める。
出発点Aから時計回りに頂点を A1, A2, … An-1とする。
訪問する頂点の並びについてまず考える。
最初にA1方向へ進むかAn-1方向へ進むかの2通りがある。
途中の点Akまで到達したときに、折り返すときは、A1, … Ak, … A1, A, An-1, … Ak, … An-1, A と移動する。
このため、折り返す点Akが k=1からk=n-1までのn-1通りある。
点Aまで一周する場合、すなわち A, A1, … An-1, A と進む場合は、Aに到達した後、もう一周するが、時計回りと反時計回りが可能なので2通りある。
よって、訪問する頂点の並びは2{(n-1)+2}=2(n+1)通りある。 …(a)
次に頂点の間の移動方法を考える。頂点間の移動は全部でnあり、それぞれを2回ずつ通る。
多角形の辺を通るか、円の弧を通るかであるが、最初に通るときには2つのうちから選択できるが、次に通るときはまだ通っていない方が強制されるので、各頂点間について2通りある。
よって、2n通りある。 …(b)
(a) (b) から、a=N(A)=2(n+1)⋅2n =(n+1)2n+1
次にbについて考える。
一筆がきの始点と終点を結んだ輪を考える。輪の任意の1点を切ると、一筆がきに対応する。輪の数をRnとする。
正n角形の頂点を始点とする場合、輪の紐が2本通っているので、どちらを切るかの2通り、切り口のどちらを始点とするかの2通りがある。
すなわち、正n角形の頂点を始点とする一筆がきの数 a=4Rn
正n角形の辺を始点とする場合輪の紐は1本通っているので、切る紐は1つに強制されており、切り口のどちらを始点とするかの2通りがある。
すなわち、正n角形の辺を始点とする一筆がきの数 b=2Rn
2R=½aなので、b=½a=(n+1)2n
一筆がきがテーマであるが、要するに場合の数の問題。数え上げる方針を考えるのも苦労する上、漏れなく数え上げるのも大変なので、相当な難問である。bはaの答えを利用して解くことは推測できるだろう。しかしながら、解答のように一旦紐に置き換えて、紐を切る、という発想はしにくいであろう。この問題が解けなくても全く問題無い。
試験場では手を出すべきではない問題の典型例といえる。数え上げを網羅するのが大変なこともあるが、nが小さい場合で試す(答えの検算をする)のが大変なことが最大の理由。他の問題を着実に解くことを目標としよう。(問題としては面白いので、こういう問題に興味がある人は数学オリンピックへの参加をお薦めする。)
この問題とは直接関係しないが、一筆がきについてはグラフ理論を学ぶと興味深い。