要素の個数について

質問

初めて質問させていただきます。
イラストロジックとかピクロスと呼ばれるパズルで1行にnマスにあったときその行のヒントになりうる要素というのは何通りになりますか？
例えば1行に3マスであればヒントとなりうる要素は
[0],[1],[1,1],[2],[3]の5通り
一行に4マスであれば
[0],[1],[1,1],[2,1],[2],[1,2],[3],[4]の8通りです。
説明がわかりにくいかもしれませんがこのような問題が得意な方いらっしゃいましたらよろしくお願いします。

回答No.1

UKY · ベストアンサー

実際にいくつか求めてみると、

1行に1升 → 2通り
1行に2升 → 3通り
1行に3升 → 5通り
1行に4升 → 8通り
1行に5升 → 13通り

すると、ここである規則に気が付きませんか?

2 + 3 = 5
3 + 5 = 8
5 + 8 = 13

この 2、3、5、8、13 …… という数字の並びはフィボナッチの数列と呼ばれています。
なぜヒントの数がフィボナッチの数列になるのかという証明は、ちょっと長くなるので今は割愛させていただきます。

参考URL：

http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0

お礼

早い回答ありがとうございます。
そういえばフィボナッチ数列になっていますね・・・

フィボナッチ数列は少し前にプログラムの授業の再起のときに習いましたがそんな性質のものなんてあんのかよーと思っていましたがこれがそうだったなんて・・・

今回は証明は必要ないので大丈夫ですが時間があれば是非とも証明を教えてもらいたいですね。
本当にありがとうございました。