京都大学 2008年度 前期日程 第2次学力試験文系数学 第5問

正 $n$ 角形の頂点を、$A_1=A$ から順に$$A_1,A_2,\dots ,A_n$$とする。隣り合う2頂点の間には、正 $n$ 角形の辺と外接円の弧の2本がある。

まず $a=N(A)$ を求める。$A$ を出発するとき、頂点をたどる向きは時計回り・反時計回りの2通りである。向きを一つ固定する。

各 $i$ について、$A_i$ と $A_{i+1}$ の間を最初に通るとき、正 $n$ 角形の辺と円弧のどちらを使うかは2通りである。ただし添字は $n$ の次を1とする。したがって、各区間で最初に使う線の選び方は$$2^n$$通りである。各区間を2回目に通る線は、最初に使わなかった方へ一意に決まる。

この選択を固定した経路には、次の $n+1$ 通りがある。$$\begin{array}{ll}\text{(i)}& \text{折り返さず、同じ向きに2周する};\\ \text{(ii)}& A_1,A_2,\dots ,A_n\text{ のいずれか1頂点で折り返す}\mathrm{.}\end{array}$$実際、未使用の線へ移る位置を決めれば、その後は全ての未使用線を重複なく通って $A$ へ戻る順序が一意に決まる。逆に一筆書きでは、2回目の通過へ移る位置は「なし」または1頂点に限られるから、これで重複も漏れもない。

したがって、最初の向き2通りも掛けると$$a=2\cdot 2^n(n+1)=2^{n+1}(n+1)$$である。

次に、辺 $A_1{A}_n$ の中点を $B$ とする。上で数えた $A_1$ 始点の経路のうち、$A_1{A}_n$ の正 $n$ 角形の辺を最初の周回で使うものはちょうど半数である。各区間の「辺・円弧」の選択を入れ替える対応によって、半数であることが分かる。

そのような閉じた経路を $B$ で切って始点と終点を $B$ に移すと、$B$ 始点の一筆書きが一意に得られる。逆に $B$ 始点の一筆書きを $B$ でつなぎ、始点を $A_1$ へ移せば元の経路へ戻る。よって$$b={\displaystyle \frac{a}{2}}=2^n(n+1)$$である。

以上より$$a=2^{n+1}(n+1),b=2^n(n+1)$$を得る。

隣接頂点間ごとに「辺」と「円弧」の2本がある。