前の結果から次が決まる【問題研究】
こんにちは。TANUKIです。
中学受験算数のなかでも最難関の入試でたびたび出題される前の結果から次の結果が決まる問題についての記事です。
フィボナッチ数列に代表されます。
例えばこんな問題です。
1と2と3だけの和で8をつくる方法は何通りありますか。ただし順番を代えたものも別の式と考えます。
8をつくるために最後に足される数に注目すると
5＋3 6＋2 7＋1 の3パターンがあります。なので5をつくるための場合の数と6をつくるための場合の数と7をつくるための場合の数をだしてたしたら求められます。
このように前の結果を利用できることから小さい順に調べていけば求めることができます。
1をつくる 1のみ1通り
2をつくる 1＋1 2 の2通り
3をつくる 2＋1 1＋1＋1 1＋2 3 の4通り
4について
1をつくってから3を足す
2をつくってから2を足す
3をつくってから3を足す
の3通りが考えられるので1＋2＋4＝7
5について
2をつくってから3を足す
3をつくってから2を足す
4をつくってから1を足す
の3通りが考えられるので13通り
以上のように前の結果が利用して次の結果が決まることを意識して表にすると
和をつくる数 １ ２ ３ ４ ５ ６ ７ ８
最後に１足す １ １ ２ ４ ７ 13 24 44
最後に２足す ０ １ １ ２ ４ ７ 13 24
最後に３足す ０ ０ １ １ ２ ４ ７ 13
場合の数の和 １ ２ ４ ７ 13 24 44 81
44＋24＋13＝81通り
(フィボナッチの3つバージョン、トリボナッチ数列になっている)
高校生で学習する漸化式での解法です。
nをつくる場合の数をP(n)とします。
式で書くとP(8)＝P(7)＋P(6)＋P(5)
となります。
同様に
P(7)＝P(6)＋P(5)＋P(4)
P(6)＝P(5)＋P(4)＋P(3)
P(5)＝P(4)＋P(3)＋P(2)
P(4)＝P(3)＋P(2)＋P(1)
P(3)＝4 P(2)＝2 P(1)＝1
を利用して式変形します。
P(8)＝P(7)＋P(6)＋P(5)
＝P(6)×2＋P(5)×2＋P(4)
＝P(5)×4＋P(4)×3＋P(3)×2
＝P(4)×7＋P(3)×6＋P(2)×4
＝P(3)×13＋P(2)×11＋P(1)×7
＝4×13＋2×11＋1×7
＝81
もう少し難しい似たタイプの問題がこちらです。
1、2、3だけを合わせて6個使って列をつくります。ただし2の後には3を、3の後には2と3を並べることはできません。その場合何通りありますか。
7個並べた状態から最後の1個を置いたら8個になりますが、7個目の数によっておける数字に制限があります。
1個並べる場合
1、2、3の3通り
2個並べる場合
11 21 31 12 22 13の6通り
1はどの数字の後にもおける
2は1と2の後における
3は1の後にしかおけない
この推移を表にまとめる
並べる個数 １２３４ ５ ６
１を最後に １３６14 31 70
２を最後に １２５11 25 56
３を最後に １１３６ 14 31
以上より70＋56＋31＝157通り
前の結果を利用する規則性の問題
ぜひ身に付けたいところです。
