|
doba |
|
袋の中の玉の色の組合せに次のように名前をつけます。（以下、色IDと呼びます）
白赤＝a 赤青＝b 青白＝c 青青＝A 白白＝B 青青＝C １回の「作業」による袋の中身の可能な遷移パターンを調べると、以下のことがわかります。 (1) 大文字・小文字を度外視すると、色IDは必ず a→b→c→a→… の順に遷移する。 (2) 小文字からは、大文字・小文字のどちらにも遷移できるが、 大文字からは小文字にしか遷移しない。 この(2)は「大文字は連続しない」ということと同値です。 (1)より、遷移パターンを考える際は、大文字・小文字がどういう順に並ぶかだけを 気にすればよいことがわかります。 この問題では、0回遷移後が小文字（a）で、13回遷移後が大文字（B）であることがわかっており、 明らかに12回遷移後は小文字（a）です。 したがって、(2)を考慮すると、求めるパターン数は、 「『大』『小』の文字を全部で12個並べる順列のうち、『大』の文字が連続せず、最後の文字が『小』であるようなものの数」 と同じです。（1回遷移後から12回遷移後までの色IDの並びに対応します。） これは、実は 「長さ１のブロックと長さ２のブロックを並べて長さ12にする時の並べ方のパターン数」 とも同じです。（長さ１のブロックに「小」、長さ２のブロックに「大小」と書いてあると考えればよい。） いずれも、漸化式からフィボナッチ数が出てくる有名な問題ですね。 |
|
1月26日（木） 3:10:59
38871 |