k^n(n:自然数)

数学とときどき競技クイズ。

2018年東京工業大学数学大問2

またまた整数。どうしても整数から解いてしまう癖がありますね。

2018年東京工業大学数学大問2
次の問いに答えよ
(1)35x+91y+65z=3を満たす整数の組(x,y,z)を一組求めよ
(2)35x+91y+65z=3を満たす整数の組(x,y,z)の中でx^2+y^2の値が最小となるもの、およびその最小値を求めよ

個人的にかなり好きな問題です。
良問なので、考察を挟みながら回答を仕上げていきます。

(考察1)
整数解が求まりづらい不定方程式は、ユークリッドの互除法を用いることが多いですね。
しかし、いつもは2変数。今回は3変数なのでさてどうしよう。
そこでよ~く、方程式を眺めてみると...係数が...
x,yについては7で、y,zについては13で、z,xについては5で括れますね。
2変数をまとめて1変数にしてしまえば3変数の方程式が2変数の方程式になるわけです!やったね!
今回は7で括りたいと思います。なぜかというと、(2)で、x^2+y^2についての話になるので、この2つをまとめておきたいと思ったからです。5で括っても13で括ってもうまくいきます。

(解答)
(1)
\begin{eqnarray}
35x+91y+65z&=&3\\
7(5x+13y)+65z&=&3
\end{eqnarray}
ここで、5x+13y=aとおくと
7a+65z=3
(ユークリッドの互除法などを使って)この方程式の整数解の1つは(a,z)=(19,-2)
a=5x+13y=19を解くと、例えば(x,y)=(-4,3)などが得られる。
よって
(x,y,z)=(-4,3,-2)(など)


(考察2)
さぁ、ここからです。
(1)を踏まえてどのように解答を作っていくのかを考えてみます。
まず、(5x+13y,z)を求めることができ、そこから(x,y)も求められます。
ということは、もしかして変数をいくつか使えば一般解が得られるかも??と想像がついたら勝負ありです。


(解答続き)
(2)
5x+13y=aとおく。
7a+65z=3の整数解の一つは(a,z)=(19,-2)だったから、いつもの不定方程式と同じように引き算してあげれば
7(a-19)+65(z+2)=0が得られ、mを整数として(a,z)=(65m+19,-7m-2)が得られる

次に、a=5x+13y=65m+19を解く。


(考察3)
また3変数(x,y,m)不定方程式が出てきてしまいましたが、13で括れますね。
ここから(1)とのつながりが見え始めます。


(解答続き)
\begin{eqnarray}
5x+13y&=&65m+19\\
5x+13(y-5m)&=&19\\
\end{eqnarray}
(1)から整数解の1つとして(x,y-5m)=(-4,3)などが得られるので、上と同様に
5(x+4)+13(y-5m-3)=0が得られ、nを整数として(x,y)=(13n-4,-5n+5m+3)が得られる。

故にこの方程式の一般解は
(x,y,z)=(13n-4,-5n+5m+3,-7m-2)


(考察4)
さぁ、一般解が得られました。
ですが、ここでx^2+y^2に代入!としてしまっては面倒なことに...(出来ないことはないかも)
x^2+y^2を小さくするためにはどうすればよいでしょう。
そもそもx^2を小さくするためには...?
お判りでしょうか、絶対値を小さくしてあげればよいですね。
|x|,|y|を小さくするように(m,n)を定めてあげれば、完成です。
今回は(結果論ですが)|x|,|y|を同時に小さくすることが可能になってくれているので
(i)|x|の最小化
(ii)|y|の最小化
を分けて考えた方が解答を仕上げやすいと思います。


(解答続き)
x^2+y^2を最小化するには|x|,|y|を最小化することを考えればよい。
(i)|x|を最小化する
 この場合、n=0として、x=-4とするとよい。
 このとき、y=5m+3でこちらはm=-1としてy=-2とするとよい。

(ii)|y|を最小化する
 y=5(m-n)+3だから、m-n=-1として、y=-2とするとよい。
 このとき、n=m+1を代入してx=13(m+1)-4だから、m+1=0すなわちm=-1とし、x=-4とするとよい。
 このとき、n=0

以上(i)(ii)より、(m,n)=(-1,0)とすれば|x|,|y|がともに最小となるため、x^2+y^2も最小値をとる。
このとき、(x,y)=(-4,-2)で、最小値は(-4)^2+(-2)^2=20




最後が見事ですねぇ~、2変数の絶対値を同時に最小化できたので、東工大の優しさを少し感じられました...
この問題は括り方次第で様々な解法が考えられますし、もっと別な解き方もたくさん存在すると思います。
まぁ、定石通りに解くとこんな感じかな??