Evolton

北海道大学 2020年度 前期日程 第2次学力試験理系数学 第2問

座標平面上の2点(116, 0),
(0, 19)を通る直線lを考える。

(1) l上にある格子点の座標をすべて求めよ。
ただし,格子点とはその点のx座標とy座標がともに整数であるような点のことである。

(2) l上の格子点のうち,原点との距離が最小となる点をAとする。
また,l上のA以外の格子点のうち,原点との距離が最小となる点をBとする。
さらに,Aのx座標とBのy座標をそれぞれx座標とy座標とする点をCとする。
三角形ABCの内部および周上にある格子点の個数を求めよ。

難易度6/ 10計算量5/ 10目安18分

整数、図形と方程式 合同式、座標設定、数え上げ

方針

(1) は直線を16x+9y=1と直し、一次不定方程式の整数解を求める。(2)では一般解を距離の2乗に代入し、整数mで最小・次小となる点A,Bを決める。三角形ABCは斜辺ABが元の直線、BCが水平、ACが垂直な直角三角形になるので、格子点はx座標ごとに下端の整数を切り上げて数える。別解として、A,B,Cが格子点であることからPickの定理で内部点と境界点を分けて総数を求めることもできる。

解答

(1)
2点 (116,0), (0,19) を通る直線は、切片の形で x1/16+y1/9=1 と表せる。したがって 16x+9y=1 である。

格子点を求めるには、この一次不定方程式の整数解を求めればよい。9を法として見ると 16x≡1(mod9) であり、16≡7(mod9) だから 7x≡1(mod9) である。7⋅4=28≡1(mod9) より x≡4(mod9) である。よって x=4+9m(m は整数) と書ける。これを 16x+9y=1 に代入すると y=1−16(4+9m)9=−7−16m である。したがって求める格子点は (x,y)=(4+9m,−7−16m)(m は整数) である。

(2)
(1)の格子点と原点との距離の2乗は (4+9m)2+(−7−16m)2 である。展開すると (4+9m)2+(−7−16m)2=337m2+296m+65 である。この二次式の軸は m=−2962⋅337=−148337 であり、−1<m<0 にある。したがって整数 m で最小となる候補は m=0 と m=−1 である。

実際に値を比べると m=0⇒65,m=−1⇒106 であるから、最小となる点は A=(4,−7) である。また次に小さいのは m=−1 の点で、B=(−5,9) である。したがって問題文の定義より C=(4,9) である。

三角形 ABC は、BC が水平、AC が垂直である。斜辺 AB はもとの直線 16x+9y=1 上にあるので、三角形内および周上の点は −5≦x≦4,1−16x9≦y≦9 をみたす。

整数 x を −5,−4,…,4 と動かして数える。各 x に対して、整数 y の個数は 9−⌈1−16x9⌉+1 である。順に書くと 1,2,4,6,8,9,11,13,15,17 である。したがって求める格子点の個数は 1+2+4+6+8+9+11+13+15+17=86 である。

別解。最後の数え上げはPickの定理でも確認できる。三角形 ABC は底辺 BC=9、高さ AC=16 の直角三角形なので面積は 12⋅9⋅16=72 である。境界上の格子点数は、AB では gcd⁡(9,16)+1=2 個、BC では10個、CA では17個であり、頂点の重複を引くと 2+10+17−3=26 個である。Pickの定理より内部の格子点数は 72−262+1=60 であるから、内部および周上の格子点数は 60+26=86 である。

別解

解法2(一次不定方程式とPickの定理)

方針

拡張された互除法の等式1=16⋅4−9⋅7から格子点の一般形を直ちに作る。原点からの距離は隣り合う候補を比較してA,Bを決める。三角形の面積と各辺上の格子点数を求め、Pickの定理から内部点と境界点の総数を出す。

解答

(1)
直線の方程式は16x+9y=1である。1=16⋅4−9⋅7 だから (4,−7) は1つの整数解である。任意の整数 m に対して(x,y)=(4+9m,−7−16m)も解となる。逆に、2つの整数解の差は 16Δx+9Δy=0 を満たし、16,9 は互いに素なので Δx=9m,Δy=−16m と書ける。したがってこれがすべての格子点である。

(2)
原点からの距離の2乗は(4+9m)2+(−7−16m)2=337m2+296m+65である。軸は −148/337 なので、最小候補は m=0,−1 である。値はそれぞれ 65,106 であり、さらに外側の整数では増加する。よってA=(4,−7),B=(−5,9),C=(4,9)である。

三角形 ABC は直角三角形で、その面積はS=12⋅9⋅16=72である。線分 AB の座標差は (9,−16) で互いに素だから、AB 上の格子点は両端の2個だけである。BC 上は10個、CA 上は17個なので、境界上の格子点数 B0 はB0=2+10+17−3=26である。内部の格子点数を I とすると、Pickの定理より72=I+262−1だから I=60 である。したがって内部および周上の格子点はI+B0=60+26=86個である。

総評

一次不定方程式と格子点数え上げを組み合わせる問題。目安時間は18分。(1)は16x+9y=1に直して合同式で一般解を出す。(2)は距離の2乗をmの二次式として扱い、最小点Aと次小点Bを確定するところまでが前半の山である。三角形内の格子点はx座標ごとの直接数え上げが高校範囲では安全だが、格子点三角形なのでPickの定理による検算も有効である。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る北大の整数の問題で問題集を作る

出典: 北海道大学 2020年度 前期 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。