中学生でも手が届く京大入試問題（２８）

こんにちは。東久留米市の学習塾塾長です。

一昨日以来、熊本では大きな地震が続いているようです。地震が早く収束し、被災された方々が早く日常の生活に戻られることを心からお祈り申し上げます。

さて、今回は平成２０年度京大入試問題（前期、文系）です。

問題は、
「正ｎ角形とその外接円を合わせた図形をＦとする。Ｆ上の点Ｐに対して、始点と終点がともにＰであるような、図形Ｆの一筆がきの経路の数をＮ（Ｐ）で表す。正ｎ角形の頂点をひとつとってＡとし、ａ＝Ｎ（Ａ）とおく。また正ｎ角形の辺をひとつとってその中点をＢとし、ｂ＝Ｎ（Ｂ）とおく。このときａとｂを求めよ。
　注：一筆がきとは、図形を、かき始めから終わりまで、筆を紙からはなさず、また同じ線上を通らずにかくことである。」
です。

まず図１のように、正ｎ角形の頂点のひとつをＡとした場合の図を描いてみましょう。（ここで、頂点ＰnをＡとしました）

▲図１．正ｎ角形の頂点ＰnをＡとした場合の図を描きました

図１で、Ａからの可能な経路は時計回りの２本と反時計回りの２本の合わせて４本ありますが、ここは、初めの移動方向を時計回りに決めて経路数を計算し、最後に２倍する（反時計回りを加える）のが良さそうです。

また、正ｎ角形の頂点間の経路はすべて２本なので、図形Ｆを一筆がきするためには、
（１）同じ方向に２周する
（２）１周目にどこかの頂点Ｐkで折り返し、その後再度頂点Ｐkで折り返す
しかありません。

そこで、初めの移動方向を時計回りとして、（１）と（２）の経路数を調べていきましょう。

まず（１）は、１周回って再度Ａに到達するまでの各頂点で可能な経路が２本なので、経路数は　２^n　です。

そして、２周目では各頂点で可能な経路が１本になるので、経路数は１になり、したがって、（１）の経路数は　２^n　になります。

次に（２）です。

図１のように、折り返す頂点をＰkとすると、１≦ｋ≦ｎです。

Ａから頂点Ｐkまで移動（時計回り）する経路数は　２^kで、頂点Ｐkで折り返してＡに移動（反時計回り）する経路数は１です。

さらに、Ａから頂点Ｐkまで移動（反時計回り）する経路数は　２^(n-k)　で、頂点Ｐkで折り返してＡに移動（時計回り）する経路数は１です。

つまり、頂点Ｐkで折り返した場合、その経路数は、２^k×２^(n-k)＝２^n　です。

ここで、頂点Ｐkはｎ通りあるので、（２）の経路数は　ｎ２^n　になります。

したがって、初めの移動方向が時計回りのときのすべての経路数は、２^n＋ｎ２^n＝（ｎ＋１）２^n　で、これに初めの移動方向が反時計回りの場合を加えると、
ａ＝（ｎ＋１）２^n×２
　＝（ｎ＋１）２^(n+1)
で、これが答えです。

続いて図２のように、正ｎ角形の辺ＰnＰ1の中点をＢとした場合です。

▲図２．正ｎ角形の辺ＰnＰ1の中点をＢとした場合の図を描きました

図２で、ＢＰnとＢＰ1の経路は、１番最初と１番最後に通らなければなりません。つまり、同じ方向に２周回るときも、頂点Ｐkで折り返すときも、頂点Ｐnと頂点Ｐ1を移動するときの経路は１本になるので、ｂはａの１/２になります。

したがって、
ｂ＝ａ÷２＝（ｎ＋１）２^n　で、これが答えです。

ついでにｂを、先程のａと同じように調べてみましょう。

まず、時計回りに２周する経路数です。

Ｂを出発してから始めて頂点Ｐn-1に到達するまで、各頂点で可能な経路は２本なので、その経路数は　２^(n-1)　で、それ以降、各頂点で可能な経路は１本になるので、時計回りに２周する経路数は　２^(n-1)　になります。

次に、頂点Ｐkで折り返す場合の経路数です。

図２のように、折り返す頂点をＰkとすると、１≦ｋ≦ｎです。

Ｂから頂点Ｐkまで移動（時計回り）する経路数は　２^(k-1)　で、頂点Ｐkで折り返して頂点Ｐnに移動（反時計回り）する経路数は１です。

さらに、頂点Ｐnから頂点Ｐkまで移動（反時計回り）する経路数は　２^(n-k)　で、頂点Ｐkで折り返してＢに移動（時計回り）する経路数は１です。

つまり、頂点Ｐkで折り返した場合、その経路数は、２^(k-1)×２^(n-k)＝２^(n-1)　です。

ここで、頂点Ｐkはｎ通りあるので、（２）の経路数は　ｎ２^(n-1)　になります。

したがって、初めの移動方向が時計回りのときのすべての経路数は、２^(n-1)＋ｎ２^(n-1)＝（ｎ＋１）２^(n-1)　で、これに初めの移動方向が反時計回りの場合を加えると、
ｂ＝（ｎ＋１）２^(n-1)×２
　＝（ｎ＋１）２^n
で、先ほどの答えと同じになりました。


各頂点間の経路が２本なので簡単な一筆がきの問題でした。