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

🕒 2020/02/25 🔄 2023/05/01

問題編

問題

　縦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通りにきまる。