トップ› 北海道大学› 1996年› 文系第3問

北海道大学 1996年文系第3問解説

方針・初手

1次変換 $T$ が格子点を格子点に移し、かつ格子点に移される点が格子点に限られるという条件は、表現行列 $A$ とその逆行列 $A^{-1}$ の成分がすべて整数であることと同値になります。まずはこの条件から $a$ の値を特定します。(2) は、(1) で得られた「$T$ は格子点集合上の全単射である」という性質を利用し、変換前の図形（正方形）に戻して格子点の個数を数え上げるか、面積と境界上の格子点から内部の格子点を求める「ピックの定理」を利用します。

解法1

(1)

点 $(1, 0)$ の $T$ による像は $(8, 9)$ であり、これは格子点である。点 $(0, 1)$ の $T$ による像は $(9, a)$ であり、条件 (イ) よりこれも格子点となるため、$a$ は整数である。

次に、条件 (ロ) より $T$ によって格子点に移される点は格子点に限られる。もし $\det A = 8a - 81 = 0$ とすると $a = \frac{81}{8}$ となり、$a$ が整数であることに矛盾する。よって $\det A \neq 0$ であり、$A$ は逆行列を持つ。任意の点 $(X, Y)$ に対して、$T(x, y) = (X, Y)$ となる点 $(x, y)$ は $(x, y) = A^{-1} (X, Y)$ と一意に定まる。条件 (ロ) は、「$(X, Y)$ が格子点ならば $(x, y)$ も格子点である」と言い換えられる。

$$ A^{-1} = \frac{1}{8a-81} \begin{pmatrix} a & -9 \\ -9 & 8 \end{pmatrix} $$

であるから、格子点 $(1, 0)$ が移される前の点 $(\frac{a}{8a-81}, \frac{-9}{8a-81})$ 、および格子点 $(0, 1)$ が移される前の点 $(\frac{-9}{8a-81}, \frac{8}{8a-81})$ はともに格子点である。よって、$\frac{-9}{8a-81}$ と $\frac{8}{8a-81}$ は整数である。ゆえに、$8a-81$ は $-9$ と $8$ の公約数でなければならない。$-9$ と $8$ は互いに素であるから、公約数は $\pm 1$ のみである。

$8a - 81 = 1$ のとき、$8a = 82$ となり整数 $a$ は存在しないため不適。 $8a - 81 = -1$ のとき、$8a = 80$ より $a = 10$。

このとき、

$$ A^{-1} = \begin{pmatrix} -10 & 9 \\ 9 & -8 \end{pmatrix} $$

となり、$A^{-1}$ の各成分はすべて整数となる。したがって、任意の整数 $X, Y$ に対して $x = -10X + 9Y, y = 9X - 8Y$ も整数となり、条件 (ロ) を満たす。以上より、$a = 10$ である。

(2)

(1) より $a = 10$。与えられた4点は $O(0, 0), P(8k, 9k), Q(9k, 10k), R(17k, 19k)$ である。これらは行列 $A$ を用いて次のように表せる。

$$ A \begin{pmatrix} 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}, \quad A \begin{pmatrix} k \\ 0 \end{pmatrix} = \begin{pmatrix} 8k \\ 9k \end{pmatrix}, \quad A \begin{pmatrix} 0 \\ k \end{pmatrix} = \begin{pmatrix} 9k \\ 10k \end{pmatrix}, \quad A \begin{pmatrix} k \\ k \end{pmatrix} = \begin{pmatrix} 17k \\ 19k \end{pmatrix} $$

すなわち、4点 $O, P, R, Q$ を頂点とする平行四辺形は、1次変換 $T$ によって、4点 $(0,0), (k,0), (k,k), (0,k)$ を頂点とする正方形 $S$ が移された図形である。

(1) で確認したように、$T$ とその逆変換 $T^{-1}$ はともに格子点を格子点に移す。したがって、点 $\boldsymbol{x}$ が平行四辺形 $OPRQ$ の内部にある格子点であることと、点 $T^{-1}(\boldsymbol{x})$ が正方形 $S$ の内部にある格子点であることは同値である。正方形 $S$ の内部に含まれる格子点 $(x, y)$ は、

$$ 0 < x < k \quad \text{かつ} \quad 0 < y < k $$

を満たす整数 $x, y$ の組である。これを満たす整数の組は、$1 \le x \le k-1$ および $1 \le y \le k-1$ であるから、$(k-1)^2$ 個存在する（$k=1$ のときは条件を満たす整数は存在せず、$0$ 個となりこの式を満たす）。よって、求める格子点の個数は $(k-1)^2$ 個である。

解法2

(2) についてピックの定理を用いる解法

頂点がすべて格子点である多角形について、その面積を $S$、周上の格子点の数を $B$、内部の格子点の数を $I$ とすると、ピックの定理により次が成り立つ。

$$ S = I + \frac{B}{2} - 1 $$

与えられた4点 $O(0,0), P(8k, 9k), R(17k, 19k), Q(9k, 10k)$ を頂点とする平行四辺形の面積 $S$ は、2つのベクトル $\vec{p} = (8k, 9k), \vec{q} = (9k, 10k)$ の張る平行四辺形の面積に等しいので、

$$ S = |8k \cdot 10k - 9k \cdot 9k| = |80k^2 - 81k^2| = k^2 $$

である。次に、周上の格子点の数 $B$ を求める。線分 $OP$ 上の格子点は、$\vec{p} = k(8, 9)$ であり、$8$ と $9$ は互いに素であるから、両端点を含めて $k+1$ 個ある。同様に、線分 $OQ$ 上の格子点も、$\vec{q} = k(9, 10)$ であり、$9$ と $10$ は互いに素であるから、両端点を含めて $k+1$ 個ある。平行四辺形の対辺はそれぞれ平行で長さが等しいため、周全体にある格子点の数 $B$ は、各辺がそれぞれ $k$ 個の区間に分割されることを考慮すると、

$$ B = 4k $$

となる。ピックの定理 $S = I + \frac{B}{2} - 1$ に代入すると、

$$ k^2 = I + \frac{4k}{2} - 1 $$

$$ I = k^2 - 2k + 1 = (k-1)^2 $$

よって、内部に含まれる格子点の個数は $(k-1)^2$ 個である。

解説

格子点と1次変換（行列）が絡む典型的な問題です。条件 (イ) と (ロ) は、結果的に「変換を表す行列 $A$ とその逆行列 $A^{-1}$ の成分がすべて整数である」ことを意味しており、これは行列式について $\det A = \pm 1$ となることと同値です。 (2) は、(1) の結果から変換 $T$ が「格子点集合の全単射」となっている性質を見抜き、変換前のシンプルな正方形領域における格子点を数え上げる解法1が最も見通しが良く鮮やかです。解法2として示した「ピックの定理（Pick's Theorem）」を利用すると、図形の変換に気付かなくとも機械的な計算で正確に答えを出すことができます。