北海道大学2019年前期理系数学第2問

2019年の大学入試整数問題シリーズ第4弾は北海道大学の理系数学です。因みに文系数学ではフィボナッチ数列に関する出題がありました。


《問題》

$n$を自然数とし、$a_n = n(n + 1)$ とする。さらに、$a_n$と$a_{n+3}$の最大公約数を$d_n$とする。

(1)$d_n$は偶数であることを示せ。

(2)$d_n$は$8$で割り切れないことを示せ。

(3)$p$を$5$以上の素数とするとき、$d_n$は$p$で割り切れないことを示せ。

(4)$d_n \leqq 12$ を示せ。また、$d_n = 12$ となるような$n$を1つ求めよ。

(北海道大学2019年 前期理系第2問)


《考え方》

数列$\{a_n\}$は隣接2整数の積なので常に偶数となります。本題は(2)からとなるでしょうか。2数の最大公約数を考えるときは差を考えます。互除法の要領で最大公約数の候補を絞り込む方法はこの手の問題では常套手段です。

まずは誘導にしっかり乗ることが大切です。

●   ●   ●

解答例

 

(1)

 

$a_n = n(n + 1)$ は隣接する2つの整数の積であるから偶数である。$a_{n+3}$も偶数であるから、$a_{n}$と$a_{n+3}$はともに$2$を素因数にもつ。故に最大公約数$d_{n}$は偶数である。

 

 

(2)

 

背理法で示す。

 

$d_n$が$8$で割り切れるとき、$a_{n}$と$a_{n+3}$はともに$8$の倍数となる。$a_{n}$と$a_{n+3}$はともに$8$の倍数であると仮定すると、整数$A$、$B$を用いて$$\begin{cases} a_{n}=8A \\ a_{n+3}=8B \end{cases}$$即ち、$$\begin{cases} n(n+1)=8A &\cdots ① \\ (n+3)(n+4)=8B &\cdots ② \end{cases}$$と置ける。$②-①$ より、$$6(n+2)=8(B-A)$$となるから、$n+2$ は$4$の倍数でなければならない。そこで$k$を整数として$$n=4k-2$$と置くと、$$\begin{align} a_{n}&=n(n+1) \\ &=(4k-2)(4k-1) \\ &=2(2k-1)(4k-1) \end{align}$$となる。$k$は整数であるから $2k-1$ および $4k-1$ は奇数であるが、これは$a_{n}$が$8$の倍数となることに矛盾する。

 

したがって、$d_n$は$8$で割り切れない。

 

 

(3)

 

背理法で示す。

 

$d_n$が$p$(ただし$p$は$5$以上の素数)で割り切れるとき、$a_{n}$と$a_{n+3}$はともに$p$の倍数となる。(2)と同様に考えると、$6(n+2)$が$p$の倍数でなければならないから、$n+2$ は$p$の倍数でなければならない。そこで$k$を整数として$$n=pk-2$$と置くと、$$\begin{align} a_{n}&=n(n+1) \\ &=(pk-2)(pk-1) \\ &=(k^2 p-3 k) p + 2 \end{align}$$となる。$p$は$5$以上の素数であるから$2$を割り切らないが、これは$a_{n}$が$p$の倍数となることに矛盾する。

 

したがって、$d_n$は$5$以上の素数$p$で割り切れない。

 

 

(4)

 

(1)と(2)より、$d_n$は$8$で割り切れない偶数であり、(3)より、$d_n$は$2$と$3$のみを素因数にもつ。これより、$s$を$2$以下の正の整数、$t$を$0$以上の整数として$$d_n=2^s \cdot 3^t$$と表せる。

 

ここで $t \geqq 2$ とすると、$6(n+2)$が$9$の倍数でなければならないから、$n+2$ は$3$の倍数でなければならない。そこで$k$を整数として$$n=3k-2$$と置くと、$$\begin{align} a_{n}&=n(n+1) \\ &=(3k-2)(3k-1) \end{align}$$となるが、$3k-2$ および $3k-1$ は$3$の倍数ではないから$a_{n}$が$9$の倍数となることに矛盾する。

 

したがって、$t \leqq 1$ であるから、$$d_n \leqq 12$$が示される。

 

$d_n=12$ とすると、整数$A$、$B$を用いて$$\begin{cases} n(n+1)=12A &\cdots ③ \\ (n+3)(n+4)=12B &\cdots ④ \end{cases}$$と置ける。$④-③$ より、$$6(n+2)=12(B-A)$$となるから、$n+2$ は偶数でなければならない。そこで$n$に順次、偶数を代入していくと、$n=8$ のとき$$\begin{cases} a_{n}=6 \cdot 12 \\ a_{n+3}=11 \cdot 12 \end{cases}$$となり適する。

 

よって求める$n$の一つは$$\color{red}{n=8}$$である。

 


(コメント)

本問は多くの予備校の講評で「やや難」に分類されているようです。北大の後期試験では難しめの整数問題が割と頻繫に出題されているのですが、前期試験ではこれまで整数問題を見かけることは珍しいくらいでした。北大前期では整数問題が出ないという「安全神話」(?)は新学習指導要領の実施によって崩れ去ったということかもしれません。北大を受験するなら、今後はより抽象度の高い整数問題の出題も覚悟しなければならないでしょう。整数好きにとっては良いニュースなのですが・・・(笑)

隣接する整数が互いに素であることを題材とした整数問題としては1995年のお茶の水女子大理系(数)第4問「$(n-1)n(n+1)$ の正の約数で$n$で割ると$1$余るものをすべて求めよ。」などがそこそこ有名だったりします。

なお、$a_n$と$a_{n+3}$の最大公約数として定義される$d_n$は$$2,6,6,4,6,6,2,12,6,2,6,12$$という周期$12$で繰り返す数列で、$n=12k-4$、$12k$ のときに $d_n=12$ となります。このことを証明してしまえば(1)~(4)まで一気に片付けることができます。この方針でいくなら、$a_n$を$12$で割った余りの周期を求めるだけで良いことになりますが、そもそも$12$という数字に辿り着くまでにそれなりの計算量が必要になりそうな気がします(本問の場合は(4)の問題文に露わに書いてあるので苦労しませんが)。

本問は誘導がかなり丁寧なので、素直に解いていくのが良いと思います。もしかすると、もっと素敵な別解もあるでしょうか?

●   ●   ●

全くの余談ですが、個人的に北大の英作文は思わず筆を止めて考えさせられるような教育的な問題が揃っていると思っています。初~中級者向けの英作文演習の題材として丁度良いので先生方にもおすすめです。



 

 

“北海道大学2019年前期理系数学第2問” への3件の返信

  1. 私は次のように解きました.

    (2),(3) Aを8もしくは5以上の素数とする.
    Aは素因数を1種類しか持たず,A≧5であることに注意する.

    a[n]=n(n+1)において,n,n+1は互いに素.
    a[n+3]=(n+3)(n+4)において,n+3,n+4は互いに素.

    a[n],a[n+1]がともにAの倍数とすれば,
    n,n+1のいずれか一方,n+3,n+4のいずれか一方はAの倍数.
    ところが,n+3,n+4は,Aの倍数である「nまたはn+1」よりも
    少なくとも2,高々4だけ大きいので,Aの倍数とはなり得ず矛盾.

    (4) (2),(3)の議論は,A=9に対しても成立する.
    以上より,d[n]は,5以上の素因数を持たず,
    素因数2は高々2個,素因数3は高々1個しか持ち得ないので,
    d[n]は(2^2)*3=12の約数であって,d[n]≦12.

    d[n]=12となるのは,n,n+1のうちにもn+3,n+4のうちにも
    3の倍数,4の倍数が両方存在する場合であり,
    n,n+4が4の倍数に確定.
    さらに,「n,n+3が3の倍数」または「n+1,n+4が3の倍数」の場合であり,
    条件は,n≡0 (mod 4)かつ,「n≡0,2 (mod 3)」.

    まとめて,n≡0,8 (mod 12)となる.
    これを満たす自然数nだから,
    (問いは1つ求めることが要求されていますが,すべて求めると,)
    n=12k-4,12k (k=1,2,3,…).

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

      (2)と(3)はやっていることがほとんど同じなので、書き込んで頂いた通り、まとめて議論してしまった方がスッキリしますね。その点、誘導が親切すぎる気もします。
      (4)も手計算ですぐに($n=8$ のみならず)「$n=12k-4,12k$」とアタリを付けられそうなものですが、実際の出来はどうだったのでしょうか・・・?

      それはともかく、別解のご提供に感謝致します!

  2. 「a[n],a[n+1]がともにAの倍数とすれば」…誤り
    「a[n],a[n+3]がともにAの倍数とすれば」でした.

    どうも失礼しました.

コメントを残す

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