今回のテーマは「一筆書き」
・問題
下の図を一筆書きで描く方法は何通りあるか？
くし団子のようなこの形、
団子と団子の間が離れていればとても簡単なのですが、
くっついている為に「1個目→2個目→1個目→2個目」
という動き方も出来るため、少し捻りが必要となります。
ただ書く順番が変わっても、1つの団子を書くのに
6通りの方法があることには変わらないので、
6の4乗に団子の進み方を掛け合わせればOKです。
ちなみに団子の進み方は（@は全部書ききる前に次へ進む印）
1 - 2 - 3 - 4
1 - 2 - 3 @ 4 - 3 - 4
1 - 2 @ 3 - 2 - 3 - 4
1 - 2 @ 3 @ 4 - 3 - 2 - 3 - 4
1 @ 2 - 1 - 2 - 3 - 4
1 @ 2 - 1 - 2 - 3 @ 4 - 3 - 4
1 @ 2 @ 3 - 2 - 1 - 2 - 3 - 4
1 @ 2 @ 3 @ 4 - 3 - 2 - 1 - 2 - 3 - 4
以上の8通りですから、答えは
(6 * 6 * 6 * 6) * 8 = 10368 通りとなります。
この問題は力ずくで解く事も可能なのですが……
竹内薫さんの正解の導出法がとても美しかったです。
その正解の導出法は、一般解になっているので
団子が何個になっても答えを出す事が出来ます。
その鍵は上の書き出しにおいての「@」なのです。
@は手前の団子を全部塗る前に次へ進んでしまう事ですが、
上の書き出したものについて順に調べてみると
○○○
○○×
○×○
○××
×○○
×○×
××○
×××
このように団子と団子の間で行くか戻るかの判定をすれば良い
という法則が見つけられる事になります。
ですから、4つの団子の場合の間は3つですから、
3箇所それぞれで行くか戻るかの2通り、
計8通りのパターンがあることになります。
この解法は言われて見れば「なるほど」という感じだったのですが
自分で見つけろとなるとちょっと難しいかも。
それでも高校生レベルで出来る内容なので、
高校生向けには面白い問題でした。
今度使ってみよう……。
PR
