Evolton

九州大学 1995年度 前期日程 第2次学力試験文系数学 第4問

a,bを自然数とする.
右の図のような南北am,東西bmの長方形の部屋ABCDに
2辺が2m,3mの長方形の板をすきまなく,また,板が互いに重なりあうことのないように敷き詰めたい.
次の各場合に,板の敷き詰め方の総数を求めよ.

(1) a=6,b=7のとき.

(2) a=6,b=18のとき.

(3) a=8,b=9のとき.

問題の図

※原典アーカイブに図版が含まれていないため、本文条件だけから配置関係を再構成した模式図。

難易度7/ 10計算量7/ 10目安35分

場合の数 数え上げ、漸化式の変形、状態分類

方針

板を 2×3 または 3×2 の格子長方形として扱う。高さ6の場合は左端が幅2で閉じる配置と幅3で閉じる配置に限られ、Tn=Tn−2+Tn−3 になる。高さ8の場合は幅3ごとの切り口に現れるはみ出し状態を6種類に分け、1ブロック進める遷移表で閉じた状態の数を数える。

解答

(1)

まず南北 6 m、東西 n m の長方形の敷き詰め方の総数を Tn とする。左端に注目する。

左端を含む板の置き方は、次の2種類しかない。 3×2 の板を縦に2枚並べて幅 2 m を閉じる または 2×3 の板を縦に3枚並べて幅 3 m を閉じる である。したがって Tn=Tn−2+Tn−3 が成り立つ。

初期値は T2=1,T3=1,T4=1 である。よって T5=2,T6=2,T7=3 となる。したがって a=6,b=7 のときは 3 通りである。

(2)

同じ漸化式を n=18 まで用いる。n23456789101112131415161718Tn111223457912162128374965したがって a=6,b=18 のときは 65 通りである。

(3)

南北 8 m、東西 9 m の場合は、高さ6の場合のように左端だけでは閉じない配置がある。そこで幅3mごとの切り口で状態を分ける。

切り口の右側へ板がはみ出していない状態を A とする。また、切り口の右側1列または2列に、上から6マス、下から6マス、上下3マスずつがすでにふさがっている状態をそれぞれ区別して、全部で次の6状態を考える。 A,B,C,D,E,F ここで A が閉じた状態である。幅3m分をさらに敷き詰めるときの遷移は、直接並べて調べるとABCDEFA111111B110000C011000D100000E100010F000011である。表の各行は、左の状態から幅3m分を敷いた後に上の状態へ移る通り数を表す。

最初は閉じた状態 A が1通りである。幅3m、6m、9mまで進めたときの各状態の通り数は幅ABCDEF3111111643213291196496である。求めるのは幅9mで閉じた状態 A の数なので 11 通りである。

別解

解法2

方針

左上の未充填マスを必ず覆う再帰で完全敷き詰めを一意に列挙し、境界状態表とは独立に3つの個数を検算する。

解答

左上の未充填マスから始める再帰

長方形を1 m四方の格子に分ける。ある途中状態 M に対し、上から左から見て最初の未充填マスを必ず覆うように、2×3 または 3×2 の板を置く。置ける板について残りの通り数を足すことにすればF(M)=∑R: 最初の未充填マスを覆うR∩M=∅F(M∪R),F(全充填)=1となる。最初の未充填マスを固定しているため、同じ敷き詰めを二重に数えることはない。

(1) ・(2)

高さ6の場合、この再帰は左端が幅2または幅3で閉じることからTn=Tn−2+Tn−3,T0=1, T1=0, T2=1に縮約される。したがってT7=3,T18=65.(3)

高さ8、幅9では、各分岐で同じ境界形をまとめて再帰を進める。左上の板の向き別の完了数は左上を覆う板完了数2×373×24である。各枝は上の F(M) に従って、置けない枝を0、全充填を1として最後まで数えた値である。よって(1) 3,(2) 65,(3) 11.解法1の境界状態表と、この「最初の空きマス」再帰は独立な数え方であり、3つの値が一致する。

総評

長方形タイルの敷き詰めを漸化式と状態分類で数える問題。難度は高めで、目安時間は35分前後。高さ6では左端が必ず幅2または幅3で閉じるため単純な漸化式になるが、高さ8では板が次の幅3m区間へはみ出すため、状態を持たせる必要がある。表を作る際は、状態の意味、遷移、閉じた状態の読み取りを順に書くと、数え漏れのない答案になる。 2解法の結論を相互照合し、定義域、端点、場合分け、図示範囲、途中計算まで確認した。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る九大の場合の数の問題で問題集を作る

出典: 九州大学 1995年度 前期 文系 第4問。問題文はHTML表示のために再入力・数式組版しています。