学習院大学2018年理系第2問

平昌オリンピックでは銀が4枚、銅が3枚(2018/02/17午前現在)と、日本代表が素晴らしいパフォーマンスを発揮しています!肖りたいものですね!

余談ですが、日本のメダルラッシュについて少し触れておきましょう。実は今大会、平昌付近に日本独自のサポートセンターを設置し、選手のケアや相手国選手のビデオ研究ができるような施設が用意されているのです。前々大会頃(バンクーバー五輪)から準備を進め、国を挙げてスポーツ選手をサポートしているそうで、その甲斐あってか日本人選手の活躍には目覚ましいものがあります。当然ながら選手当人の努力がその根底にあるのは言うまでもありませんが、同じ東アジアとはいえ、異国の地で日本同様のサポートを受けられるというのは選手たちにとって大変心強いのではないかと思います。

昨今では際限なく膨張を続ける防衛費が政権批判の的になっていますが、国民の税金はこういうところにこそ使って欲しいものです!


《問題》

自然数$m$、$n$に対して $x=8m+n$、$y=5m+2n$ とおく。$x$、$y$ の最大公約数を$d$とする。

(1)$m$、$n$が互いに素ならば、$d=1$ または $d=11$ であることを示せ。

(2)$m=2$ のとき、$d=11$ となる最小の自然数$n$を求めよ。

この問題については、答えだけでなく、答えを導く過程も書くこと。

 

(学習院大学2018年理系 第2問)


《考え方》

連立1次不定方程式の問題です。(1)は定石通り、差を取っていきます。ある数$A$と、ある数$B$の最大公約数$D$は、ある数$A$とそれらの差 $A-B$ の最大公約数に一致します。勿論$D$は、ある数$B$とそれらの差 $A-B$ の最大公約数にも一致します。これを利用して2数の最大公約数を求めるアルゴリズムが「ユークリッドの互除法」です。最大公約数がテーマとなっているときは2数の差を取ることで解答の道筋が見えてくる場合が多くあります。今回もそのパターンですね。

●   ●   ●

$x$と$y$の最大公約数が$d$なので $x-y$ も$d$の倍数となります。これより、整数$k$を用いて$$x-y=3m-n=dk$$とおくことができ、$$n=3m-dk$$となります。ここで$m$、$n$が互いに素なので、$d \geqq 2$ のとき、$m$、$n$はいずれも$d$を約数にもたないことに注意しましょう。

さて、これより$x$の式から$n$を消去して整理すれば$$x+dk=11m$$を得ます。$d$は$x$と$y$の最大公約数なので$x$は$d$の倍数です。よって左辺は$d$の倍数となるので右辺も$d$の倍数となることが必要です。先ほど説明した通り、$m$は$d$を約数にもたないことから、$d$は$11$の約数でしかあり得ません。したがって、$m$、$n$が互いに素ならば、$d=1$ または $d=11$ であることが示されました。

続いて(2)ですが、まずは $m=2$ を代入しましょう。このとき$$\begin{cases} x=n+16 \\ y=2n+10 \end{cases}$$となります。例によって、差 $y-x=n-6$ も$d$の倍数となりますから、$0$以上の整数$N$を用いて$$n=dN+6$$と表されます。これより、$d=11$ のとき$$n=11N+6$$となります。$N$に$0$から順に小さい整数を入れていき、$x$と$y$の最大公約数を調べると、$N=1$、すなわち $n=17$ のとき $x=33$、$y=44$ となり、$d=1$ となります。故に$$n=\color{red}{17}$$が求める最小値となります。


(コメント)

連立1次不定方程式の問題としては易しめですので、あまり落としたくない問題でしたね。(2)で$n$の最小値を求める際、早とちりして $n=6$ としないようにしましょう。このとき $x=22$、$y=22$ となるので最大公約数$d$は$11$ではなく$22$です。



2次試験まで残すところあと1週間ほどになりました。最近日本列島で猛威を奮っているインフルエンザを予防するためにも、無理をして夜更かしせず、早めの就寝を心掛けましょう!

“学習院大学2018年理系第2問” への2件の返信

  1. 問題文で,「$d=1$」(わざと全角にしました)だけは,
    なぜかTeXの処理がされずに,そのまま表示されているようです.

    また,解答中で,「$x-y$ の最大公約数も $d$」とあるのは変で,
    「$x-y$ も $d$ の倍数」であるべきですね.

    大して違いはありませんが,私は次のように解きました.

    (1)($m,\ n$ の連立方程式と見て,$m,\ n$ を $x,\ y$ で表す方針)
    $-5x+8y=11n$ と $2x-y=11m$ はともに $d$ の倍数.
    よって,$d$ は $11n$ と $11m$ の公約数であり,
    $m,\ n$ が互いに素であれば $11$ の約数であって,$1,\ 11$ のいずれか.

    (2) まず,$m=2$ より,$m,\ n$ が互いに素でないとき,$n$ は偶数となり,
    このとき,$x,\ y$ はともに偶数となるから,条件を満たさない.
    よって,$n$ は奇数であることが必要で,
    このとき,(1) より $d$ は $1$ または $11$.

    (1) で得た $-5x+8y=11n$ から,
    $x$ が $11$ の倍数であれば $y$ も $11$ の倍数となり,$d=11$ となる.
    よって,「$n$ は奇数」という条件下で,
    $x=8m+n=16+n$ が $11$ の倍数となるような $n$ を求めればよく,
    \[n\equiv 1\ (\mathrm{mod}\ 2),\qquad n+16\equiv 0\ (\mathrm{mod}\ 11)\]
    から,
    \[n\equiv 17\ (\mathrm{mod}\ 22)\]
    を得て,最小の自然数 $n$ は $n=17.$

    1. たけちゃん さん
      コメントありがとうございます。

      たまにTeX形式の変換が上手くいかないときがあるのですが、確認せずに投稿してしまいそのままになってしまいました。原因は不明ですね・・・(笑)
      また、「最大公約数~」とあったのは単に不注意でしたので修正させて頂きました。ご指摘ありがとうございます。

      (1)は たけちゃん さんの方針では$11$という数字が自然に出てきますし、「互いに素」という条件が分かりやすい形で使えるアプローチになっていますね。良い解法だと思います。
      (2)は正直それほど手間のかかる問題でもないので、答えを求めるだけなら解答例のように特に何も考えなくても十分かとは思います。ただ、たけちゃん さんが示された解答のように「互いに素」という条件が効いてくることに触れた方が、出題サイドの文脈に沿ったものになるでしょうね。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です