トップ› 京都大学› 2020年› 文系第5問

京都大学 2020年文系第5問解説

方針・初手

どの行にも、どの列にも同じ数字が1回しか現れない配置（数学的には「ラテン方陣」と呼ばれます）の総数を求める問題です。
全てを無作為に数え上げるのは困難なため、対称性を利用して場合分けを大幅に減らす工夫をします。
まず一番上の行（1行目）の並べ方を固定し、次に一番左の列（1列目）の並べ方を固定したうえで、残りのマスの埋め方を具体的に数え上げます。

解法1

1行目の4マスの数字の並べ方は、$4! = 24$ 通りある。各行・各列の条件は数字を入れ替えても対称であるため、1行目が左から $1, 2, 3, 4$ の順である場合を考え、最後に求まった数に 24 を掛けることとする。

1行目が $1, 2, 3, 4$ に固定された状態を考える。このとき、1列目の残り3マス（2～4行目）には $2, 3, 4$ のいずれかが入る。この1列目の数字の並び方は $3! = 6$ 通りある。ここで、2～4行目の行全体を上下にどのように入れ替えても、「各行・各列に同じ数字が1回しか現れない」という条件は保たれる。したがって、1列目の並び方が 6 通りのうちどのパターンの場合でも、条件を満たす全体の配置の数は同じになる。そこで、1列目が上から $1, 2, 3, 4$ の順である場合について、残りのマスの埋め方が何通りあるかを数え、あとで $3! = 6$ を掛ける。

1行目と1列目がともに $1, 2, 3, 4$ の順である配置は以下のようになる。

1	2	3	4
2
3
4

2行目の残り3マス（2〜4列目）には $1, 3, 4$ が入る。各列に同じ数字が入らない条件から、2列目には $2$ 以外（すでにクリア）、3列目には $3$ 以外、4列目には $4$ 以外が入る必要がある。これらを満たす2行目の並びは以下の3パターンがある。 (i)

$2, 1, 4, 3$ (ii)

$2, 3, 4, 1$ (iii)

$2, 4, 1, 3$

それぞれのパターンについて、3行目と4行目の入れ方を考える。

(i) 2行目が $2, 1, 4, 3$ のとき

1	2	3	4
2	1	4	3
3
4

3行目の残り3マスには $1, 2, 4$ が入る。 2列目はすでに $2, 1$ があるため $4$ に確定する。残りの $1, 2$ は、3列目（すでに $3, 4$ がある）、4列目（すでに $4, 3$ がある）のどちらに入れても列の重複条件を満たす。よって、3行目は $3, 4, 1, 2$ または $3, 4, 2, 1$ の 2 通りとなる。 3行目が決まれば、4行目は各列の残りの数字を入れることで一意に決まり、これらは行の条件も自動的に満たす（それぞれ $4, 3, 2, 1$ と $4, 3, 1, 2$ になる）。したがって、この場合は 2 通り。

(ii) 2行目が $2, 3, 4, 1$ のとき

1	2	3	4
2	3	4	1
3
4

3行目の残り3マスには $1, 2, 4$ が入る。 4列目はすでに $4, 1$ があるため、残りの候補のうち $2$ に確定する。 3列目はすでに $3, 4$ があり、残りの候補は $1, 4$ だが $4$ は入れないので $1$ に確定する。すると残る2列目は $4$ に確定する。よって、3行目は $3, 4, 1, 2$ のみに確定し、4行目も空いた数字を入れて $4, 1, 2, 3$ のみに決まる。したがって、この場合は 1 通り。

(iii) 2行目が $2, 4, 1, 3$ のとき

1	2	3	4
2	4	1	3
3
4

3行目の残り3マスには $1, 2, 4$ が入る。 2列目はすでに $2, 4$ があるため、残りの候補のうち $1$ に確定する。 4列目はすでに $4, 3$ があるため、残りの候補のうち $2$ に確定する。すると残る3列目は $4$ に確定する。よって、3行目は $3, 1, 4, 2$ のみに確定し、4行目も空いた数字を入れて $4, 3, 2, 1$ のみに決まる。したがって、この場合は 1 通り。

以上より、1行目と1列目がともに $1, 2, 3, 4$ の順である配置は $2 + 1 + 1 = 4$ 通りある。

全体の総数は、（1行目の並べ方） $\times$ （1列目の並べ方） $\times$ （固定したときの配置の数） $= 4! \times 3! \times 4$ $= 24 \times 6 \times 4$ $= 576$

解説

「数独（ナンプレ）」のようなルールの配置ですが、このような方陣を数学用語で「ラテン方陣」と呼びます。今回は $4 \times 4$ のサイズのラテン方陣の総数を求める問題でした。場合の数の難問においては、このように「特定の行や列を固定して数え、あとで並べ替えの総数（階乗）を掛ける」というアプローチが極めて有効です。行の入れ替えや数字の置換を行っても条件が崩れないという「対称性」を見抜くことができれば、実際に数え上げるパターンを 4 通りまで劇的に減らすことができます。