座標や図形を利用した整数問題 | 高校数学まるごと解説

要点整理

これまで整数の性質や1次不定方程式について学んできましたが、この単元では、それらの知識を「座標平面(x軸とy軸を使って点の位置を表す平面のこと)」や「図形」と組み合わせて使う問題を扱います。整数問題を図形的に捉え直すことで、見通しよく解けるようになる場合が多くあります。

格子点とは何か

まず、格子点という言葉を確認しておきましょう。格子点とは、x座標とy座標がどちらも整数であるような、座標平面上の点のことです。例えば $(2, 3)$ や $(0, -5)$ は格子点ですが、$\left(\dfrac{1}{2}, 4\right)$ は格子点ではありません(x座標が整数ではないからです)。

座標や図形を利用した整数問題では、この格子点を数えたり、格子点の中から条件に合うものを探したりすることがよく出てきます。

直線上の格子点と1次不定方程式のつながり

例えば、原点 $(0, 0)$ と点 $(12, 8)$ を結ぶ線分の上には、両端以外にも格子点が乗っています。これを見つけるには、前提知識である1次不定方程式の考え方がそのまま使えます。

線分の傾き(x座標が1増えたときにy座標がどれだけ増えるかを表す量)は $\dfrac{8}{12} = \dfrac{2}{3}$ です。この線分上の点 $(x, y)$ は、比例式 $y : x = 8 : 12$ を満たすので、

$8x = 12y$

という関係が成り立ちます。両辺を4でわると、

$2x = 3y$

となります。ここで、2と3は互いに素(最大公約数が1)なので、「$3$ が $2x$ を割り切るならば、$3$ は $x$ を割り切る」という性質が使えます(これは1次不定方程式のときに学んだ、互いに素な整数どうしの関係と同じ考え方です)。つまり $x$ は3の倍数でなければならず、$x = 3k$($k$は整数)とおけます。このように、直線の式を整数の関係式として読み直すことで、格子点を系統的に見つけることができます。

領域内の格子点の数え上げ

もう一つのよくある問題が、「ある不等式を満たす整数の組 $(x, y)$ が何個あるか」を求めるものです。この場合は、不等式が表す図形(領域)を座標平面に描き、y座標(または x座標)を1つずつ固定して、そのときにx座標(またはy座標)が何通りあるかを数えていく、という方法が基本になります。

$x \geq 0,\quad y \geq 0,\quad x + 2y \leq 8$

のような条件であれば、$y = 0, 1, 2, 3, 4$ の場合に分けて、それぞれで $x$ のとりうる整数の個数を数え、最後に合計する、という手順です。図形をイメージしながら数えることで、数え漏れや重複を防ぐことができます。

距離の公式との組み合わせ

座標平面上の2点 $(x_1, y_1)$、$(x_2, y_2)$ の間の距離は、三平方の定理から

$\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$

で求められます。特に原点 $(0, 0)$ と点 $(x, y)$ の距離は $\sqrt{x^2 + y^2}$ です。整数問題の中には、「条件を満たす整数の組をすべて求めたうえで、その中で原点から一番近い(または遠い)ものを選ぶ」という形の問題もあります。この場合、まず1次不定方程式の考え方ですべての整数解を求め、その後で距離を1つずつ計算して比較する、という2段階の作業になります。

例題

例題1(基本)

問題

2点 $A(0, 0)$、$B(12, 8)$ を結ぶ線分上にある格子点(x座標、y座標がともに整数である点)の個数を求めなさい。ただし、両端の点 $A$、$B$ も個数に含めることとします。

解答・解説を見る

線分 $AB$ 上の点 $(x, y)$ は、$A(0,0)$ を通り、傾きが $\dfrac{8}{12}$ の直線上にあります。傾きが等しいことから、比例式

$\frac{y}{x} = \frac{8}{12}$

が成り立ちます(ただし $x = 0$ のときは $A$ 自身なので別に数えます)。両辺に $12x$ をかけて分母を払うと、

$12y = 8x$

となります。両辺を4でわると、

$3y = 2x$

すなわち

$2x = 3y$

という関係式が得られます。

ここで、$2$ と $3$ は互いに素(最大公約数が1)です。$2x = 3y$ より、$3$ は $2x$ を割り切ります。$3$ と $2$ が互いに素なので、$3$ は $x$ を割り切らなければなりません(2の側に約数3を持ち込む余地がないからです)。

したがって、$x$ は3の倍数です。$x = 3k$($k$ は整数)とおくと、

$2(3k) = 3y$

$6k = 3y$

$y = 2k$

となります。

線分 $AB$ の範囲は $0 \leq x \leq 12$ なので、

$0 \leq 3k \leq 12$

各辺を3でわると、

$0 \leq k \leq 4$

を満たす整数 $k$ を考えます。$k$ の値は $k = 0, 1, 2, 3, 4$ の5通りです。

それぞれの $k$ に対応する点は、

$k=0$: $(0, 0)$
$k=1$: $(3, 2)$
$k=2$: $(6, 4)$
$k=3$: $(9, 6)$
$k=4$: $(12, 8)$

の5点です。

よって、線分 $AB$ 上にある格子点(両端を含む)の個数は、

$\boxed{5\ \text{個}}$

です。

例題2(標準)

問題

不等式 $x \geq 0$、$y \geq 0$、$x + 2y \leq 8$ をすべて満たす整数の組 $(x, y)$ の個数を求めなさい。

解答・解説を見る

まず、条件を図形としてイメージします。$x + 2y = 8$ という直線は、$x$ 軸上の点 $(8, 0)$ と $y$ 軸上の点 $(0, 4)$ を通ります。条件 $x \geq 0$、$y \geq 0$、$x + 2y \leq 8$ が表す領域は、原点 $(0,0)$、$(8,0)$、$(0,4)$ の3点を頂点とする三角形の内部と周(境界線)をあわせた部分です。

この領域の中にある格子点を数えるために、$y$ の値を1つずつ固定して、そのときの $x$ の個数を数えていきます。

条件 $y \geq 0$ と $x + 2y \leq 8$ より、$2y \leq 8$ となるので $y \leq 4$ です。したがって、$y$ がとりうる整数値は $y = 0, 1, 2, 3, 4$ です。

それぞれの $y$ について、$x$ の条件は $x \geq 0$ と $x \leq 8 - 2y$ です。$x$ は整数で、$0$ から $8-2y$ まで動けるので、その個数は

$(8 - 2y) - 0 + 1 = 9 - 2y\ (\text{個})$

となります(「最大値 $-$ 最小値 $+ 1$」で整数の個数を数える、という基本の考え方です)。

$y$ ごとに整理すると、

$y = 0$ のとき: $x$ の個数は $9 - 2(0) = 9$ 個
$y = 1$ のとき: $x$ の個数は $9 - 2(1) = 7$ 個
$y = 2$ のとき: $x$ の個数は $9 - 2(2) = 5$ 個
$y = 3$ のとき: $x$ の個数は $9 - 2(3) = 3$ 個
$y = 4$ のとき: $x$ の個数は $9 - 2(4) = 1$ 個

したがって、格子点の総数は、これらをすべて足し合わせて、

$9 + 7 + 5 + 3 + 1 = 25$

よって、求める整数の組 $(x, y)$ の個数は、

$\boxed{25\ \text{個}}$

です。

例題3(応用)

問題

$3x + 4y = 60$ を満たし、かつ $x > 0$、$y > 0$ である整数の組 $(x, y)$ をすべて求めなさい。さらに、それらの点のうち、原点 $O(0, 0)$ からの距離が最小になる点を求めなさい。

解答・解説を見る

ステップ1: 1次不定方程式として整数解を求める

$3x + 4y = 60$ の整数解を求めます。まず、$x = 0$ とすると $4y = 60$ より $y = 15$ です。よって $(x, y) = (0, 15)$ は1つの解(特殊解)です。

$3x + 4y = 60$ と $3(0) + 4(15) = 60$ の両辺をそれぞれ引くと、

$3(x - 0) + 4(y - 15) = 0$

$3x + 4(y - 15) = 0$

$3x = -4(y - 15)$

$3$ と $4$ は互いに素なので、$3$ が右辺 $-4(y-15)$ を割り切ることと、$3$ が $(y - 15)$ を割り切ることは同値です。よって $y - 15 = 3s$($s$ は整数)とおけます。これを代入すると、

$3x = -4(3s) = -12s$

$x = -4s$

ここで $t = -s$ とおき直すと、$s = -t$ なので、

$x = -4(-t) = 4t$

$y = 15 + 3(-t) = 15 - 3t$

したがって、一般解は

$x = 4t,\quad y = 15 - 3t\quad (t\ \text{は整数})$

と表せます(検算: $3(4t) + 4(15-3t) = 12t + 60 - 12t = 60$ となり、確かに成り立っています)。

ステップ2: $x > 0$、$y > 0$ の条件で $t$ の範囲を絞る

$x = 4t > 0$ より $t > 0$ です。$t$ は整数なので $t \geq 1$ です。

$y = 15 - 3t > 0$ より $3t < 15$、両辺を3でわって $t < 5$ です。$t$ は整数なので $t \leq 4$ です。

以上より、$t = 1, 2, 3, 4$ の4通りです。それぞれ計算すると、

$t = 1$: $x = 4, y = 12$ → $(4, 12)$
$t = 2$: $x = 8, y = 9$ → $(8, 9)$
$t = 3$: $x = 12, y = 6$ → $(12, 6)$
$t = 4$: $x = 16, y = 3$ → $(16, 3)$

ステップ3: 原点からの距離を比較する

原点 $O(0,0)$ から点 $(x, y)$ までの距離は $\sqrt{x^2 + y^2}$ ですが、根号のままだと比較しづらいので、根号の中身である $x^2 + y^2$ の大小を比較すれば十分です($x^2+y^2$ が大きいほど距離も大きくなるからです)。

$(4, 12)$: $4^2 + 12^2 = 16 + 144 = 160$
$(8, 9)$: $8^2 + 9^2 = 64 + 81 = 145$
$(12, 6)$: $12^2 + 6^2 = 144 + 36 = 180$
$(16, 3)$: $16^2 + 3^2 = 256 + 9 = 265$

これらのうち、$x^2+y^2$ が最小なのは $145$ で、点 $(8, 9)$ のときです。

したがって、求める整数の組は

$(x, y) = (4, 12),\ (8, 9),\ (12, 6),\ (16, 3)$

の4組であり、そのうち原点からの距離が最小になるのは、

$\boxed{(x, y) = (8, 9)\ \left(\text{距離は}\ \sqrt{145}\right)}$

です。

練習問題

問題

不等式 $x \geq 0$、$y \geq 0$、$2x + 3y \leq 12$ をすべて満たす整数の組 $(x, y)$ の個数を求めなさい。

答え

$19$ 個。

($y = 0$ のとき $x$ は $0$ 〜 $6$ の7個、$y=1$ のとき $0$〜$4$ の5個、$y=2$ のとき $0$〜$3$ の4個、$y=3$ のとき $0$〜$1$ の2個、$y=4$ のとき $x=0$ の1個で、$7+5+4+2+1=19$ 個。)