一筆書きの問題（１）

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

天気図を見ると、高気圧や低気圧が日々刻々と西から東に移動していて、昨日のような、午前は晴れて、午後は雲が多くなるといった天気が続くようです。

先日、中学生でも手が届く京大入試問題（２８）で、一筆書きの問題を取り上げましたが、「ジュニア数学オリンピック２００９－２０１３」に、一筆書きの場合の数を漸化式を使って求める方法があったので、それを紹介したいと思います。

問題は、
「次の図形を一筆書きで描くとき、描き方は何通りあるか」
です。

▲問題図

問題図では正三角形が６個ですが、ここでは図１のように、ｎ個の正三角形を組み合わせた図形を調べます。

▲図１．ｎ個の正三角形を組み合わせました

図１の図形を一筆書きするとき、Ａ、Ｘから奇数本の辺が出ているので、Ａ、Ｘが始、終点になります。

そこで、Ａが始点、Ｘが終点になる描き方の場合の数ｆ（ｎ）について漸化式を立式します。このとき、Ａからの最初の移動先によって場合分けをします。

（１）Ａ→Ｂでスタートする場合
この場合、Ｂ→Ｃと移動せざるおえません。

つまり、Ａ→Ｂでスタートした場合の描き方の場合の数は、図２にあるｎ－１個の正三角形を組み合わせた図形で、Ｃを始点、Ｘを終点とする描き方の場合の数ｆ（ｎ－１）になります。

▲図２．Ａ→Ｂでスタートする場合

（２）Ａ→Ｃでスタートする場合
図３のように、Ｃに移動したとき、経路Ｃ－Ｂ－Ａは、経路Ｃ－Ａと同じですから、（１）と同様に、Ａ→Ｃでスタートした場合の描き方の場合の数は、Ｃを始点、Ｘを終点とする描き方の場合の数ｆ（ｎ－１）になります。

▲図３．Ａ→Ｃでスタートする場合

（３）Ａ→Ｄでスタートする場合
図４のように、正三角形ＡＢＣを除いてできる、ｎ－２個の正三角形を組み合わせた図形で、Ｄを始点、Ｘを終点とする描き方の場合の数はｆ（ｎ－２）で、さらに正三角形ＡＢＣを周回する方向が２通りあるので、Ａ→Ｄでスタートした場合の描き方の場合の数は、２ｆ（ｎ－２）になります。

▲図４．Ａ→Ｄでスタートする場合

以上から、
ｆ（ｎ）＝ｆ（ｎ－１）＋ｆ（ｎ－１）＋２ｆ（ｎ－２）
　　　　＝２（ｆ（ｎ－１）＋ｆ（ｎ－２））
が成り立ちます。

問題では、ｎ＝６なので、ｆ（１）＝２、ｆ（２）＝６から
ｆ（３）＝２（ｆ（２）＋ｆ（１））＝１６
ｆ（４）＝２（ｆ（３）＋ｆ（２））＝４４
ｆ（５）＝２（ｆ（４）＋ｆ（３））＝１２０
ｆ（６）＝２（ｆ（５）＋ｆ（４））＝３２８
になり、３２８（通り）で、これが答えです。（ＡとＸを区別するときは、３２８×２＝６５６（通り））


次回は、初めに紹介した京大の入試問題に漸化式を使う方法を調べてみたいと思います。