【京都大学2020年度前期入試数学(理系)第5問】中学受験で出てきそうな場合の数の問題

今回の問題はタイトルにあるのが全てです。まるで中学受験です。

京都大学　百周年時計台記念館
2015年5月5日、Soraie8288撮影、Wikipediaより

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

くり返しになりますが、この問題は中学入試に出てもおかしくない問題です。ということは、京大受験生ができないとかあり得ません。中学生の娘も(退化していなければ)解けると思います。

第4問と同様、問題はいかに素早く解くかです。

まず1行目を考えます。並べ方は 4! = 24 通りです。

並べ方を 1つ 固定して2行目を考えます。例えば1行目を 1, 2, 3, 4 とします。こうしても一般性を失いません。

2行目を考えます。1の置き方は3通りあります。例えば 2列目に置いたとします。どこにおいても対称性から話は一緒です。

このとき、2行目に2をおく置き方は2種類存在します。
(場合1) 2を1列目におく(1行目の1, 2 を2行目で交換) ⇒ 2, 1, 4, 3 という置き方のみ
(場合2) 2をそれ以外の列におく ⇒ 4, 1, 2, 3 もしくは 3, 1, 4, 2 の2通り

(場合1) 3行目を考えると、1, 2 列目には 3 と 4 を、3, 4 列目には1, 2 をおくことができ、その場合は4通りあります。そのそれぞれに対して4行目が一意に定まるので、4! × 3 × 4 通り存在します。

(場合2) 4, 1, 2, 3 の場合に固定します。このとき、3行目を考えます。

このときに、各数字 i が1, 2行目で置かれている場所(何列目か)を集合 X_i で表したときに、X_i = X_j となる i ≠ j が存在しないので、3, 4 行目でおかなければならない場所の集合 {1, 2, 3, 4} - X_i についてもすべて異なることになります。

実際、各数字が3行目と4行目における場所を確認すると、
・1: 3, 4 列
・2: 4, 1 列
・3: 1, 2 列
・4: 2, 3 列
となります。このとき、例えば3行目で 1 を3列目に置くと、3列を含んでいる 4 が2列目になり、2列を含んでいる 3 が1列目になり、1列を含んでいる 2 が4列目になります。このようにして、残り2行の置き方は 3, 4, 1, 2 と 2, 3, 4, 1 のいずれかしかなくなります。

これは 2行目で 3, 1, 4, 2 を採用した場合も同じで、このときには残り2行は 4, 3, 2, 1 と 2, 4, 1, 3 となります。

よって、この場合は 4! × 3 × 2 × 2 通りあります。

場合1 と場合 2 から 4! × 3 × 4 × 2 = 24 × 24 = 576 通りとなります。

この問題は樹形図を作成した気分で数えればいいだけです。ただし、場合2 で2通りしか存在しないことをどこまで説明するのかでもしかすると減点があるかもしれません。注意するとしたらそこでしょうか。

とにかくまともに数えるのが難儀なので、効率よく数え上げることが求められます。面倒な問題ではありますが、先ほどの注意点を除いてある意味で一番簡単な問題だと思います。