方針
板を または の格子長方形として扱う。高さ6の場合は左端が幅2で閉じる配置と幅3で閉じる配置に限られ、 になる。高さ8の場合は幅3ごとの切り口に現れるはみ出し状態を6種類に分け、1ブロック進める遷移表で閉じた状態の数を数える。
解答
(1)
まず南北 m、東西 m の長方形の敷き詰め方の総数を とする。左端に注目する。
左端を含む板の置き方は、次の2種類しかない。 または である。したがって が成り立つ。
初期値は である。よって となる。したがって のときは 通りである。
(2)
同じ漸化式を まで用いる。したがって のときは 通りである。
(3)
南北 m、東西 m の場合は、高さ6の場合のように左端だけでは閉じない配置がある。そこで幅3mごとの切り口で状態を分ける。
切り口の右側へ板がはみ出していない状態を とする。また、切り口の右側1列または2列に、上から6マス、下から6マス、上下3マスずつがすでにふさがっている状態をそれぞれ区別して、全部で次の6状態を考える。 ここで が閉じた状態である。幅3m分をさらに敷き詰めるときの遷移は、直接並べて調べるとである。表の各行は、左の状態から幅3m分を敷いた後に上の状態へ移る通り数を表す。
最初は閉じた状態 が1通りである。幅3m、6m、9mまで進めたときの各状態の通り数はである。求めるのは幅9mで閉じた状態 の数なので 通りである。
別解
解法2
方針
左上の未充填マスを必ず覆う再帰で完全敷き詰めを一意に列挙し、境界状態表とは独立に3つの個数を検算する。
解答
左上の未充填マスから始める再帰
長方形を1 m四方の格子に分ける。ある途中状態 に対し、上から左から見て最初の未充填マスを必ず覆うように、 または の板を置く。置ける板について残りの通り数を足すことにすればとなる。最初の未充填マスを固定しているため、同じ敷き詰めを二重に数えることはない。
(1) ・(2)
高さ6の場合、この再帰は左端が幅2または幅3で閉じることからに縮約される。したがって(3)
高さ8、幅9では、各分岐で同じ境界形をまとめて再帰を進める。左上の板の向き別の完了数はである。各枝は上の に従って、置けない枝を0、全充填を1として最後まで数えた値である。よって解法1の境界状態表と、この「最初の空きマス」再帰は独立な数え方であり、3つの値が一致する。
総評
長方形タイルの敷き詰めを漸化式と状態分類で数える問題。難度は高めで、目安時間は35分前後。高さ6では左端が必ず幅2または幅3で閉じるため単純な漸化式になるが、高さ8では板が次の幅3m区間へはみ出すため、状態を持たせる必要がある。表を作る際は、状態の意味、遷移、閉じた状態の読み取りを順に書くと、数え漏れのない答案になる。 2解法の結論を相互照合し、定義域、端点、場合分け、図示範囲、途中計算まで確認した。