漸化式タイプの場合の数

最後に着目するタイプ

例題1

横が10cm、たてが20cmの長方形のタイルと、1辺の長さが20cmの正方形のタイルがそれぞれたくさんあります。これらのタイルで、たて20cm、よこ60cmの長方形のかべをすき間がないようにしきつめます。ただし、正方形のタイルを2枚以上連続してしきつめることはできません。例えば、図1のようにしきつめることはできますが、図2のようにしきつめることはできません。

中学受験算数カンガープリント 場合の数・フィボナッチ型最後に着目2410
(1)タイルのしきつめ方は全部で何通りありますか。
(2)たて20cm、よこ80cmの長方形のかべをしきつめる場合、タイルのしきつめ方は何通りありますか。

解説

吹き出し用まなぶくんイラスト

「タイルのしきつめ」は階段上りのように解くことができると前に学びました。

吹き出し用カンガルー先生イラスト

そうだよね。

吹き出し用まなぶくんイラスト

この問題はさらに「一番最後に着目」という要素が入ってます。
左から右へタイルをしきつめていくとき、
一番最後(右)が正方形のタイルか、そうでないのか、これがこの問題のポイントになっています。

吹き出し用カンガルー先生イラスト

その通り!
今まで学んできたことを使いこなして解きましょう!
1人でできそう?

吹き出し用まなぶくんイラスト

ちょっと自信ないですけど・・・

吹き出し用カンガルー先生イラスト

先生が表のまとめかたを教えるからね。

10cmのしきつめは1通り(階段の1段上りが1通り)
これは下図のAです。

20cmのしきつめは2通り(階段の2段上りが1通り)
これは下図のB、Cです。

一番右のタイルがどうなっているか区別する必要があるので、下図のように、A,B、Cと区別します。

Cを連続して並べてはいけません。

中学受験算å数カンガープリント 場合の数・フィボナッチ型最後に着目2412
吹き出し用カンガルー先生イラスト

20cmのしきつめ方は、
10cmしきつめてから10cmしきつめるのが1通り
20cmを一気にしきつめるのが2通り

合計で3通り。
一番右のタイルがAかBかCか、表に入れていきます。
Cが連続することはないですね。

中学受験算å数カンガープリント 場合の数・フィボナッチ型最後に着目2414
吹き出し用カンガルー先生イラスト

では続きをやってみようか。
30cmのしきつめ方です。

吹き出し用まなぶくんイラスト

30cmのしきつめ方は、
20cmしきつめてから10cmしきつめるのが3通り
10cmをしきつめてから、残り20cmを一気にしきつるのが1×2=2通り

合計で5通り。
ここでも、Cが連続することはないですね。

一番右のタイルがAかBかCか、表に入れていきます。

中学受験算å数カンガープリント 場合の数・フィボナッチ型最後に着目2416
吹き出し用カンガルー先生イラスト

とてもいいですね!

では40cmのしきつめ方です。
ここから注意が必要ですよ!

吹き出し用まなぶくんイラスト

40cmのしきつめ方は、
30cmしきつめてから10cmしきつめるのが5通り。

20cmをしきつめてから、残り20cmを一気にしきつめるのは・・・
なるほど!
注意が必要ですね。
Cを連続して並べてはいけないから。

20cmをしきつめてから、Bをしきつめるのが3通り。
20cmをしきつめてから、Cをしきつめるのが2通り。
よって、5通り。

40cmのしきつめ方は全部で、5+5=10(通り)

中学受験算å数カンガープリント 場合の数・フィボナッチ型最後に着目2418
吹き出し用カンガルー先生イラスト

はい!
そういうことです。

つまり、
「最後がA」は「1つ前の合計」
「最後がB」は「2つ前の合計」
「最後がC」は「2つ前のA+B」
ということなのです!

中学受験算å数カンガープリント 場合の数・フィボナッチ型最後に着目2419
吹き出し用まなぶくんイラスト

では、あとは表をうめていくだけですね!

50cmのしきつめは下表。

中学受験算å数カンガープリント 場合の数・フィボナッチ型最後に着目2420
吹き出し用まなぶくんイラスト

では、あとは表をうめていくだけですね!

60cmのしきつめは下表。

中学受験算å数カンガープリント 場合の数・フィボナッチ型最後に着目2421
吹き出し用まなぶくんイラスト

求まりました。
横60cmのしきつめの総数は、37通りです。

吹き出し用カンガルー先生イラスト

はい、正解です。

もう残りも簡単だよね。
同じように表をうめるだけだからね。
答えは下表のようになります。
横80cmのしきつめの総数は、137通りです

中学受験算å数カンガープリント 場合の数・フィボナッチ型最後に着目2422

別解

吹き出し用カンガルー先生イラスト

60cmのしきつめを、普通の場合の数の問題として解くこともできます。
6を1と2と2´に分解します。
2´は連続して並べることはできません。
(2、2、2)・・・1通り
(2、2、2´)・・・3通り
(2、2´、2´)・・・1通り
(2´、2´、2´)・・・0通り
(2、2、1、1)・・・6通り
(2、2´、1、1)・・・12通り
(2´、2´、1、1)・・・3通り
(2、1、1、1、1)・・・5通り
(2´、1、1、1、1)・・・5通り
(1、1、1、1、1、1)・・・1通り

以上、合計37通り