数学A 整数問題 問題 99 解説

方針・初手

$5x+4y$ と $3x+2y$ を新しい座標 $k,\ell$ と見る。連立方程式を逆に解くと $x,y$ が $k,\ell$ で表せるので、格子点の条件は $k,\ell$ の偶奇条件に変換できる。

そのうえで、領域 $D_n$ 内の格子点の個数は、正方形 $0\leqq k\leqq n,\ 0\leqq \ell\leqq n$ 内で $k,\ell$ の偶奇が一致する整数組の個数を数えればよい。

解法1

(1)

実数 $x,y$ に対して

$$ k=5x+4y,\qquad \ell=3x+2y $$

とおく。この連立方程式を $x,y$ について解く。

$$ \begin{aligned} k&=5x+4y,\\ \ell&=3x+2y \end{aligned} $$

より、消去して

$$ x=2\ell-k,\qquad y=\frac{3k-5\ell}{2} $$

を得る。

まず、$x,y$ がともに整数であるとする。このとき $k=5x+4y,\ \ell=3x+2y$ はともに整数である。また、$2$ を法として考えると

$$ k=5x+4y\equiv x \pmod 2 $$

かつ

$$ \ell=3x+2y\equiv x \pmod 2 $$

である。したがって $k\equiv \ell \pmod 2$ であり、$k,\ell$ はともに偶数であるか、ともに奇数である。

逆に、$k,\ell$ がともに偶数であるか、ともに奇数であるとする。このとき $k,\ell$ は整数であり、$k\equiv \ell \pmod 2$ である。

先ほどの式

$$ x=2\ell-k $$

より、$x$ は整数である。また、

$$ y=\frac{3k-5\ell}{2} $$

について、$3k-5\ell\equiv k-\ell\equiv 0\pmod 2$ であるから、$3k-5\ell$ は偶数である。よって $y$ も整数である。

以上より、条件 （i） と条件 （ii） は同値である。

(2)

$D_n$ は

$$ 0\leqq 5x+4y\leqq n,\qquad 0\leqq 3x+2y\leqq n $$

で表される領域である。ここで

$$ k=5x+4y,\qquad \ell=3x+2y $$

とおくと、領域の条件は

$$ 0\leqq k\leqq n,\qquad 0\leqq \ell\leqq n $$

となる。

（1） より、$D_n$ 内の格子点 $(x,y)$ は、整数組 $(k,\ell)$ のうち、$0\leqq k,\ell\leqq n$ を満たし、さらに $k,\ell$ の偶奇が一致するものと一対一に対応する。

したがって、$0,1,2,\ldots,n$ の中にある偶数の個数と奇数の個数を数えればよい。

(i) $n=2m$ のとき

$0,1,2,\ldots,2m$ の中で、偶数は

$$ 0,2,4,\ldots,2m $$

の $m+1$ 個であり、奇数は

$$ 1,3,5,\ldots,2m-1 $$

の $m$ 個である。

$k,\ell$ がともに偶数である組は $(m+1)^2$ 個、$k,\ell$ がともに奇数である組は $m^2$ 個であるから、求める個数は

$$ (m+1)^2+m^2=2m^2+2m+1 $$

である。$n=2m$ より、これは

$$ \frac{n^2}{2}+n+1 $$

である。

(ii) $n=2m+1$ のとき

$0,1,2,\ldots,2m+1$ の中で、偶数は

$$ 0,2,4,\ldots,2m $$

の $m+1$ 個であり、奇数は

$$ 1,3,5,\ldots,2m+1 $$

の $m+1$ 個である。

したがって、求める個数は

$$ (m+1)^2+(m+1)^2=2(m+1)^2 $$

である。$n=2m+1$ より、これは

$$ \frac{(n+1)^2}{2} $$

である。

解説

この問題の核心は、斜めの帯で囲まれた領域をそのまま $xy$ 平面で数えないことである。$k=5x+4y,\ \ell=3x+2y$ とおくと、領域 $D_n$ は $k\ell$ 平面上の正方形に変わる。

ただし、すべての整数組 $(k,\ell)$ が格子点 $(x,y)$ に対応するわけではない。対応する条件が「$k,\ell$ の偶奇が一致すること」であり、これを （1） で確認している。

したがって （2） は、正方形内の整数格子点のうち、チェッカーボード状に半分程度を数える問題に帰着される。

答え

(1)

条件 （i） と条件 （ii） は同値である。

(2)

$D_n$ に含まれる格子点の個数は

$$ \begin{cases} \dfrac{n^2}{2}+n+1 & (n\text{ が偶数}),\\[6pt] \dfrac{(n+1)^2}{2} & (n\text{ が奇数}) \end{cases} $$

である。