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

問題編

問題

　縦4個、横4個のマス目のそれぞれに 1, 2, 3, 4 の数字を入れていく。このマス目の横の並びを行といい、縦の並びを列という。どの行にも、どの列にも同じ数字が1回しか現れない入れ方は何通りあるか求めよ。下図はこのような入れ方の1例である。

1	2	3	4
3	4	1	2
4	1	2	3
2	3	4	1

考え方

やるべきことはすぐにわかりますが、なかなかどう取り組んでいけばいいかわからないですね。場合分けをして攻めていくことになりますが、とにかくある程度までグループ化してまとめて数えて、あとは書き出すようにしてもいいでしょう。

---

解答編

問題

　縦4個、横4個のマス目のそれぞれに 1, 2, 3, 4 の数字を入れていく。このマス目の横の並びを行といい、縦の並びを列という。どの行にも、どの列にも同じ数字が1回しか現れない入れ方は何通りあるか求めよ。下図はこのような入れ方の1例である。

1	2	3	4
3	4	1	2
4	1	2	3
2	3	4	1

解答

左上を基準とし、上から $i$ 行目、左から $j$ 列目を $(i,j)$ で表すとする。

「どの行にもどの列にも同じ数字が1回しか現れない」という条件を (A) と置く。この条件を満たす入れ方に対し、4つの列を並び替えれば、1以上4以下の $i$ に対して、 $(i,i)$ の数字に 1 が入るようにできる。

1
	1
		1
			1

よって、この場合に条件(A) を満たす入れ方の総数を数え、それに $4!=24$ を掛ければ、(A)を満たす入れ方の総数が求められる。

以下、条件(A)を満たし、どの $(i,i)$ にも 1 が入っている場合を考える。1行目が、 1, a, b, c という順番に並んでいたとする。1列目も上から順番に 1, a, b, c と入っていた場合、条件(A)を満たす入れ方は次のようになる。なお、1列目の入れ方を決めると、他のマスの入れ方は1通りにきまる。

1	a	b	c
a	1	c	b
b	c	1	a
c	b	a	1

また、1列目と4列目のa, bを入れ替えたもの、1列目と2列目のb, cを入れ替えたもの、1列目と3列目のc, aを入れ替えたものも条件(A)を満たす。これらも1列目の入れ方を決めると、他のマスに入る数字は1通りにきまる。

なお、1列目の入れ方は、他に2通りある。まず、次の場合を考える。

1	a	b	c
b	1
c		1
a			1

この場合、 $(2,3)$ には c が入り、 $(2,4)$ には a が入るしかないが、3行目に a が入る場所がなくなってしまう。

また、次の場合を考える。

1	a	b	c
c	1
a		1
b			1

このばあ、 $(2,3)$ には a が入るしかないが、そうすると4行目に a が入るところがない。

このことから、1行目の入れ方を決めた場合、条件(A) を満たす入れ方は4通りあることがわかる。

よって、条件(A)を満たす入れ方は、1行目の入れ方が $3!=6$ 通り、そのそれぞれに2行目以降の入れ方が $4$ 通り、そして、列を並び替えの方法が $4!=24$ 通りなので、求める場合の数は\[ 6\times 4\times 24=576 \]通りとなる。

（終）