[math][東京医科歯科大学][場合の数]1988年東京医科歯科大学数学問題2

Table of Contents

問題

$n$を整数$(n\geq 2)$とし、$n$以下の正の整数の集合を$N$とする。また行列$\displaystyle \begin{pmatrix}0 & 1 \\ 1 & 0\end{pmatrix}$の表す座標平面上の$1$次変換を$f$とする。いま座標平面上の点の集合$X$に関する次の条件を考える。
条件$A: $$X$は空集合ではない。
条件$B: $ 点$P(A, B)$が$X$に属するならば、$a$と$b$は$N$の要素で、$a\ne b$である。
条件$C: $ 点$P$が$X$に属するならば点$f(P)$も$X$に属する。
条件$D: $ $N$の任意の要素$a$に対し、直線$y = a$の上には$X$に属する点がちょうど$3$点ある。
このとき次の問に答えよ。
$(1)$ $n = 3$のとき、条件$A, B, C$を同時に満たす集合$X$にはどのようなものがあるか。そのような$X$をすべて求めよ。
$(2)$ 条件$A, B, C$を同時に満たす集合$X$の個数を$n$を用いて表わせ。
$(3)$ $n = 6$のとき、条件$A, B, C, D$を同時に満たす集合$X$で、$4$点$P_1(1, 2), P_2(1, 3), P_3(1, 4), P_4(2, 3)$を含むものをすべて求めよ。なお複数個の解が得られた場合は、各集合$X$についてそれぞれ別の座標平面上で、$X$に属する点を図示することにより解答せよ（証明は不要）。

方針

決して難しいことを聞いている問題ではないが、試験場では差がつくかもしれない。

解答

$(1)$ 平面上の任意の点$(x, y)$に対して、$$\begin{pmatrix}0 & 1\\ 1 & 0\end{pmatrix}\begin{pmatrix}x \\ y\end{pmatrix} = \begin{pmatrix}y \\ x\end{pmatrix}$$であるから、$1$次変換$f$は、平面上の点を直線$y = x$に関して対称移動させる変換である。条件を満たすような点は下の図のようになる。

点$(x, y)$が集合$X$に含まれるとき、必ず点$(y, x)$も同じ集合に含まれることに注意すると、求める答えは次の$7$個である。$$X = \{(1, 2), (2, 1)\}, \{(1, 3), (3, 1)\}, \{(2, 3), (3, 2)\}, \\ \{(1, 2), (2, 1), (1, 3), (3, 1)\}, \{(1, 2), (2, 1), (2, 3), (3, 2)\} \{(1, 3), (3, 1), (2, 3), (3, 2)\}\\ \{(1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2)\}$$

$(2)$ 平面上で、座標がともに$n$までの正の整数であるような点で、直線$y = x$上にないものの個数は、$n^2-n$個である。この点は、各々直線$y = x$に関して対称な点とペアになっている。このペアが集合に含まれるか含まれないかで、$2^{\frac{n^2-n}{2}}$通りの場合の数がある。しかし、全部含まれない$1$通りは除いて考えないといけない。よって、求める答えは$\underline{2^{\frac{n(n-1)}{2}}-1}$通りである。

$(3)$ $4$点$P_1(1, 2), P_2(1, 3), P_3(1, 4), P_4(2, 3)$が集合$X$に含まれるとき、点$(2, 1), (3, 1), (4, 1), (3, 2)$も集合$X$に含まれる。

$(i)$ 点$(4, 2)$が集合$X$に含まれるとき、点$(2, 4)$も同じく集合$X$に含まれる。直線$y = 1, y = 2$の上にはすでに集合$X$に含まれる点が$3$つあるので、点$(5, 1), (6, 1), (5, 2), (6, 2)$は集合$X$に含まれない。すると、$(1, 5), (1, 6), (2, 5), (2, 6)$も集合$X$には含まれない。

このとき、直線$y = 6$上の$3$点は$(3, 6), (4, 6), (5, 6)$と決まり、点$(6, 3), (6, 4), (6, 5)$も集合$X$に含まれることになる。直線$y = 5$をみると、残りの点は$(3, 5), (4, 5)$と決まる。すると点$(5, 3), (5, 4)$も集合$X$に含まれることになる。ところが、直線$y = 3$上にはすでに$3$個の点があり、矛盾する。つまり、点$(4, 2)$は集合$X$に含まれない。

$(ii)$ 点$(5, 2)$が集合$X$に含まれるとき、点$(2, 5)$も同じく集合$X$に含まれる。直線$y = 1, y = 2$の上にはすでに集合$X$に含まれる点が$3$つあるので、点$(5, 1), (6, 1), (4, 2), (6, 2)$は集合$X$には含まれない。すると、$(1, 5), (1, 6), (2, 4), (2, 6)$も集合$X$には含まれない。

このとき、直線$y = 6$上の$3$点は$(3, 6), (4, 6), (5, 6)$と決まり、点$(6, 3), (6, 4), (6, 5)$も集合$X$に含まれることになる。直線$y = 5$をみると、残りの点は$(3, 5), (4, 5)$のどちらかである。ところが、直線$y = 3$上にはすでに$3$個の点があるので、直線$y = 5$上の残りの点は点$(4, 5)$と決まる。すると、点$(5, 4)$も集合$X$に含まれ、すべての点が決まる。

$(iii)$ 点$(6, 2)$が集合$X$に含まれるとき、点$(2, 6)$も同じく集合$X$に含まれる。直線$y = 1, y = 2$の上にはすでに集合$X$に含まれる点が$3$つあるので、点$(5, 1), (6, 1), (4, 2), (5, 2)$は集合$X$に含まれない。すると、$(1, 5), (1, 6), (2, 4), (2, 5)$も集合$X$には含まれない。

直線$y = 5$を見ると、残りの点は$(3, 5), (4, 5), (6, 5)$と決まる。点$(5, 3), (5, 4), (5, 6)$も集合$X$に含まれる。$y = 3$を見ると、すでに$3$個の点があり、点$(6, 3)$は集合$X$に含まれないので、点$(3, 6)$も含まれない。したがって、直線$y = 6$上の残りの点は点$(4, 6)$と決まる。そうすると、点$(6, 4)$も集合$X$に含まれるから、全ての点が決まる。