トップ› 名古屋大学› 2008年› 文系第3問

名古屋大学 2008年文系第3問解説

方針・初手

与えられた不等式 $ax + by \leqq c$ を満たす $0$ 以上の整数の組 $(x, y)$ の個数（非負の格子点数）を求める問題である。

このような問題では、$x$ または $y$ のどちらか一方の変数を固定し、もう一方の変数が取りうる整数の個数を求めてから、シグマ計算を用いて足し合わせるのが定石である。固定する変数を変えることで場合分けの数が変わるため、より場合分けが少なくなる方針を選ぶと計算ミスを防ぎやすい。

解法1

(1)

与えられた不等式は $3x + 2y \leqq 8$ であり、$x, y$ は $0$ 以上の整数である。

$y \geqq 0$ であるから、$3x \leqq 8$ が成り立ち、これを満たす $0$ 以上の整数 $x$ は $x = 0, 1, 2$ のいずれかである。各 $x$ について、条件を満たす $y$ の個数を求める。

(i) $x=0$ のとき

不等式は $2y \leqq 8 \iff y \leqq 4$ となる。これを満たす $0$ 以上の整数 $y$ は、$y=0, 1, 2, 3, 4$ の $5$ 個である。

(ii) $x=1$ のとき

不等式は $3 + 2y \leqq 8 \iff 2y \leqq 5 \iff y \leqq 2.5$ となる。これを満たす $0$ 以上の整数 $y$ は、$y=0, 1, 2$ の $3$ 個である。

(iii) $x=2$ のとき

不等式は $6 + 2y \leqq 8 \iff 2y \leqq 2 \iff y \leqq 1$ となる。これを満たす $0$ 以上の整数 $y$ は、$y=0, 1$ の $2$ 個である。

以上より、求める組 $(x, y)$ の個数は、

$$ 5 + 3 + 2 = 10 $$

(2)

与えられた不等式は $3x + 2y \leqq 2008$ であり、$x, y$ は $0$ 以上の整数である。

これを $y$ について解くと、

$$ 2y \leqq 2008 - 3x \iff y \leqq 1004 - \frac{3}{2}x $$

$x$ の値の偶奇によって $y$ のとりうる値の最大値が変わるため、$k$ を $0$ 以上の整数として場合分けを行う。

(i) $x = 2k$ のとき

不等式は $y \leqq 1004 - 3k$ となる。 $y \geqq 0$ であるから、$1004 - 3k \geqq 0 \iff 3k \leqq 1004 \iff k \leqq 334.6\dots$ $k$ は整数であるから、$0 \leqq k \leqq 334$ である。このとき、条件を満たす $y$ は $0$ から $1004 - 3k$ までのすべての整数であるから、その個数は、

$$ (1004 - 3k) - 0 + 1 = 1005 - 3k $$

(ii) $x = 2k + 1$ のとき

不等式は $y \leqq 1004 - \frac{3(2k+1)}{2} = 1002.5 - 3k$ となる。 $y$ は整数であるから、$y \leqq 1002 - 3k$ となる。 $y \geqq 0$ であるから、$1002 - 3k \geqq 0 \iff 3k \leqq 1002 \iff k \leqq 334$ $k$ は整数であるから、$0 \leqq k \leqq 334$ である。このとき、条件を満たす $y$ は $0$ から $1002 - 3k$ までのすべての整数であるから、その個数は、

$$ (1002 - 3k) - 0 + 1 = 1003 - 3k $$

(i), (ii) より、求める組 $(x, y)$ の総数はこれらの合計である。

$$ \begin{aligned} \sum_{k=0}^{334} (1005 - 3k) + \sum_{k=0}^{334} (1003 - 3k) &= \sum_{k=0}^{334} \{ (1005 - 3k) + (1003 - 3k) \} \\ &= \sum_{k=0}^{334} (2008 - 6k) \\ &= 2008 \sum_{k=0}^{334} 1 - 6 \sum_{k=0}^{334} k \\ &= 2008 \times 335 - 6 \times \frac{334 \times 335}{2} \\ &= 335 \times (2008 - 3 \times 334) \\ &= 335 \times (2008 - 1002) \\ &= 335 \times 1006 \\ &= 337010 \end{aligned} $$

解法2

(2)の別解

$y$ を固定して考える。与えられた不等式を $x$ について解くと、

$$ 3x \leqq 2008 - 2y \iff x \leqq \frac{2008 - 2y}{3} $$

$y$ を $3$ で割った余りによって $x$ のとりうる値の最大値が変わるため、$k$ を $0$ 以上の整数として場合分けを行う。

(i) $y = 3k$ のとき

不等式は $x \leqq \frac{2008 - 6k}{3} = 669.33\dots - 2k$ となる。 $x$ は整数であるから、$x \leqq 669 - 2k$ である。 $x \geqq 0$ より $669 - 2k \geqq 0 \iff k \leqq 334.5$ であり、$k$ は整数なので $0 \leqq k \leqq 334$ となる。このとき、条件を満たす $x$ の個数は、

$$ (669 - 2k) - 0 + 1 = 670 - 2k $$

(ii) $y = 3k + 1$ のとき

不等式は $x \leqq \frac{2008 - 2(3k+1)}{3} = \frac{2006 - 6k}{3} = 668.66\dots - 2k$ となる。 $x$ は整数であるから、$x \leqq 668 - 2k$ である。 $x \geqq 0$ より $668 - 2k \geqq 0 \iff k \leqq 334$ であり、$0 \leqq k \leqq 334$ となる。このとき、条件を満たす $x$ の個数は、

$$ (668 - 2k) - 0 + 1 = 669 - 2k $$

(iii) $y = 3k + 2$ のとき

不等式は $x \leqq \frac{2008 - 2(3k+2)}{3} = \frac{2004 - 6k}{3} = 668 - 2k$ となる。 $x$ は整数であるから、$x \leqq 668 - 2k$ である。 $x \geqq 0$ より $668 - 2k \geqq 0 \iff k \leqq 334$ であり、$0 \leqq k \leqq 334$ となる。このとき、条件を満たす $x$ の個数は、

$$ (668 - 2k) - 0 + 1 = 669 - 2k $$

(i), (ii), (iii) より、求める組 $(x, y)$ の総数はこれらの合計である。

$$ \begin{aligned} \sum_{k=0}^{334} \{ (670 - 2k) + (669 - 2k) + (669 - 2k) \} &= \sum_{k=0}^{334} (2008 - 6k) \end{aligned} $$

このシグマ計算は解法1と同様であり、計算結果は $337010$ となる。

解説

不等式の表す領域内の格子点（座標がともに整数である点）の個数を数え上げる典型問題である。

(2)において、$x$ を固定した場合（解法1）は「$2$ で割った余り」による $2$ つの場合分けが生じ、$y$ を固定した場合（解法2）は「$3$ で割った余り」による $3$ つの場合分けが生じる。一般に、係数が大きい方の文字で場合分けを行う（もう一方の文字の係数で割った余りを考える）ほうが、場合分けの数が少なくなるため効率的である。本問では $x$ の係数 $3$ の方が大きいため、$x$ を固定して $y$ の個数を数える方針をとることで場合分けを減らすことができる。

また、シグマの計算において $\sum_{k=0}^{n}$ となっている点に注意が必要である。$\sum_{k=1}^{n}$ の公式をそのまま適用せず、項数が $n+1$ 個であることを意識して計算を進める必要がある。