トップ› 九州大学› 1995年› 文系第4問

九州大学 1995年文系第4問解説

方針・初手

板の置き方（縦置き、横置き）と、それが長方形の行・列をどのように分割するかを考える。板の幅と高さの制約から、敷き詰め方が「縦方向の列の組み合わせ」または「横方向の行の組み合わせ」に限定されることを見抜くのが鍵となる。

解法1

まず、板の置き方を「横置き（縦 $2\text{m}$、横 $3\text{m}$）」と「縦置き（縦 $3\text{m}$、横 $2\text{m}$）」の2種類とする。横置きの板は高さ2、幅3であり、縦置きの板は高さ3、幅2である。

部屋の左下を原点とし、敷き詰められた板の配置について考える。仮に、ある縦の列において、横置きの板と縦置きの板が混在して配置されたとする。横置きの板は幅3、縦置きの板は幅2であるため、これらが混在すると板の右端の $x$ 座標が一致せず、隣接する列に幅1の隙間が生じる。しかし、用意された板の最小の辺の長さは2であるため、この幅1の隙間をすきまなく埋めることは不可能である。したがって、任意の敷き詰め方において「同じ列には同じ幅の板しか置けない」または「同じ行には同じ高さの板しか置けない」の少なくとも一方が成り立つ。

これにより、敷き詰め方は以下の2つのタイプのいずれかに分類される。

タイプV（縦割り）：部屋が垂直な直線によって、幅2の列と幅3の列に分割される。
タイプH（横割り）：部屋が水平な直線によって、高さ2の行と高さ3の行に分割される。

各列・各行が敷き詰め可能であるための条件は以下の通りである。

幅2の列：縦置きの板（高さ3）のみで埋めるため、縦の長さ $a$ が3の倍数である必要がある。このとき敷き詰め方は1通り。
幅3の列：横置きの板（高さ2）のみで埋めるため、縦の長さ $a$ が2の倍数である必要がある。このとき敷き詰め方は1通り。
高さ2の行：横置きの板（幅3）のみで埋めるため、横の長さ $b$ が3の倍数である必要がある。このとき敷き詰め方は1通り。
高さ3の行：縦置きの板（幅2）のみで埋めるため、横の長さ $b$ が2の倍数である必要がある。このとき敷き詰め方は1通り。

これをもとに各場合を計算する。

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

縦 $a=6$ は2の倍数かつ3の倍数である。横 $b=7$ は2の倍数でも3の倍数でもない。

したがって、タイプH（横割り）の場合、高さ2の行（幅が3の倍数必要）も高さ3の行（幅が2の倍数必要）も敷き詰めることができず、条件を満たさない。よって、タイプV（縦割り）のみを考えればよい。

横幅7を幅2と幅3の列に分割する。使用する幅2の列の数を $x$、幅3の列の数を $y$ とすると、

$$2x + 3y = 7$$

$x, y$ は0以上の整数であるから、解は $(x, y) = (2, 1)$ のみである。すなわち、幅2の列が2つ、幅3の列が1つである。これらの列の並べ方の総数は、

$$\frac{3!}{2!1!} = 3$$

各列内部の敷き詰め方はそれぞれ1通りに定まるため、求める総数は3通りである。

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

縦 $a=6$ は2の倍数かつ3の倍数。横 $b=18$ も2の倍数かつ3の倍数である。

まず、タイプV（縦割り）の敷き詰め方を考える。横幅18を幅2と幅3の列に分割する。

$$2x + 3y = 18$$

非負整数解 $(x, y)$ は以下の4通りであり、それぞれの並べ方の数は次のようになる。

$(9, 0)$ のとき、並べ方は $\frac{9!}{9!0!} = 1$ 通り
$(6, 2)$ のとき、並べ方は $\frac{8!}{6!2!} = 28$ 通り
$(3, 4)$ のとき、並べ方は $\frac{7!}{3!4!} = 35$ 通り
$(0, 6)$ のとき、並べ方は $\frac{6!}{0!6!} = 1$ 通り

合計すると $1 + 28 + 35 + 1 = 65$ 通りとなる。

次に、タイプH（横割り）の敷き詰め方を考える。縦幅6を高さ2と高さ3の行に分割する。

$$2m + 3n = 6$$

非負整数解 $(m, n)$ は $(3, 0)$ と $(0, 2)$ の2通りである。

$(3, 0)$ はすべて高さ2の行（横置きの板のみ）であり、これはタイプVの $(x, y) = (0, 6)$ と全く同じ配置である。
$(0, 2)$ はすべて高さ3の行（縦置きの板のみ）であり、これはタイプVの $(x, y) = (9, 0)$ と全く同じ配置である。

したがって、タイプHの配置はすべてタイプVに含まれるため、重複して数える必要はない。よって、求める総数は65通りである。

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

縦 $a=8$ は2の倍数であるが、3の倍数ではない。横 $b=9$ は3の倍数であるが、2の倍数ではない。

タイプV（縦割り）について考える。縦 $a=8$ が3の倍数ではないため、幅2の列（高さ3の板が必要）を作ることはできない。したがって、すべて幅3の列で構成するしかない。横幅9をすべて幅3の列で構成すると、必要な列の数は $9 \div 3 = 3$ 列となり、敷き詰め方は1通りである。

タイプH（横割り）について考える。横 $b=9$ が2の倍数ではないため、高さ3の行（幅2の板が必要）を作ることはできない。したがって、すべて高さ2の行で構成するしかない。縦幅8をすべて高さ2の行で構成すると、必要な行の数は $8 \div 2 = 4$ 行となり、敷き詰め方は1通りである。

このとき、タイプVにおける1通り（すべて横置きの板）と、タイプHにおける1通り（すべて横置きの板）は全く同じ配置を指している。よって、求める総数は1通りである。

解説

長方形のタイリング（敷き詰め）問題において、「タイルの辺の長さの組み合わせによって、直線的な分割線（断層）が必ず生じる」という性質を利用する難問である。板の向きを混在させると必ず「幅1の隙間」が生じて破綻するという事実に気づけるかどうかが鍵となる。これに気づけば、単なる不定方程式の非負整数解の個数と、同じものを含む順列の計算に帰着できる。