今回は、簡単そうで奥が深い一筆書きの問題。


そもそも、一筆書きとは、鉛筆を線から離さず、同じ線を通らないように図形を描くこと。
そして、一筆書きできる図形の条件というのがあって、、

@すべて偶点(偶数本の線が出ている点)
A奇点(奇数本の線が出ている点)が2個






では本題。。今回は何通りの書き方があるのかを考えてみます。
まずは簡単な問題でウォーミングアップ!



まず、ア〜エの葉っぱをどの順番で完成させるかで4×3×2×1=24通り。
そして、それぞれを左回り、右回りのどちらで回るかで2×2×2×2=16通り。
だから、、答えは24×16=384通り





今度はちょっと難しい。



まず、4つの交差点をア〜エとして、これをどういう順番で通っていくかという考え方をします。
ア→イ→ア→…であれば、アからイへ行くのに3通りあり、イからアに戻るのにさっきの線は通ることができないので2通り、…という具合です。



すると、次の4通りの場合があることがわかります。

ア→イ→ア→イ→ウ→イ→ウ→エ→ウ→エのとき、3×2×1×3×2×1×3×2×1=216通り
ア→イ→ア→イ→ウ→エ→ウ→イ→ウ→エのとき、3×2×1×3×3×2×2×1×1=216通り
ア→イ→ウ→イ→ア→イ→ウ→エ→ウ→エのとき、3×3×2×2×1×1×3×2×1=216通り
ア→イ→ウ→エ→ウ→イ→ア→イ→ウ→エのとき、3×3×3×2×2×2×1×1×1=216通り

だから、216×4=864通り



≪おまけ≫

このようにして、だんごが3個だと求められますが、、、これ以上増えると一気に複雑になってしまう。。
そこで、何個の場合でもいける、もっと効率的な方法を考えてみたくなる。

だんごが1個のときは、右に進んで、左に進んで、右に進むと完成するから、3×2×1=6通り・・・☆
ここで、だんごがn個のときの書き方がf(n)通りあるとして、だんごがn+1個のときにどう表されるかを考えてみます。
1)n個がすでに完成していて、最後のだんごを書き上げる書き方があり、これはf(n)×通り
2)n個がまだ完成していなくて、最後のだんごの2本の線を書き(3本のうち2本の選び方と、それを左回り、右回りのどちらで書くか)
  戻って、n個を完成させてからゴールに向かう書き方があり、これは×f(n)×通り
1)と2)を合わせて、、f(n+1)=f(n)×6+f(n)×6=f(n)×12・・・★
☆★より、「6通り→×12→72通り→×12→864通り→×12→…」と、だんごが1個増えると書き方は12倍で増えていくことがわかり、
これは等比数列なので、だんごがn個のときの書き方は、6×12n-11/2×12n通り


[←戻る]