Evolton

東京大学 1994年度 後期日程 第2次学力試験理系(後期)数学 第1問

正の整数mとk=1,2,⋯ ,mに対して0≦ak≦kを満たす整数a1,⋯ ,amがあたえられたときに[am,am−1,⋯ ,a1]m=am⋅m!+am−1⋅(m−1)!+⋯+a1⋅1!とおく.ただしam≠0とする.

(1) [m,m−1,⋯ ,1]m=[1,0,⋯ ,0]m+1−1を証明せよ.

(2) すべての正の整数は[am,am−1,⋯ ,a1]mの形にただ一通りに表示できることを証明せよ.

(3) nが5以上の整数のときn!5を[am,am−1,⋯ ,a1]mの形に表示せよ.

難易度8/ 10計算量7/ 10目安30分

整数、数列、論証・証明 和の計算、帰納的定義の利用、一意性証明、場合分け

方針

(1) は k⋅k!=(k+1)!−k! で望遠和にする。(2)は最大の階乗から順に整数の除法を行い、存在と一意性を示す。(3)は n=5q+r と分け、同じ除法を上位桁から行う。

解答

(1) [m,m−1,…,1]m=∑k=1mk⋅k!=∑k=1m{(k+1)!−k!}=(m+1)!−1であるから、所要の等式が成り立つ。

(2) 正の整数 N に対し、m!≦N<(m+1)! となる m を選ぶ。整数の除法によりN=amm!+Rm,0≦Rm<m!とする。上の範囲から 1≦am≦m である。次に Rm を (m−1)! で割り、この操作を 1! まで続けるとN=amm!+am−1(m−1)!+⋯+a11!,0≦ak≦kを得るので表示は存在する。各段階の商と余りは整数の除法によりただ一通りであるから、表示も一意である。

(3) n=5q+r (0≦r≦4) とおく。書いていない下位桁を0とすればn!5={[q,0,…,0]n−1,r=0,[q,q,0,…,0]n−1,r=1,[q,2q,2q,0,…,0]n−1,r=2,[q,3q+1,q,q,0,…,0]n−1,r=3,[q,4q+2,2q,4q,4q,0,…,0]n−1,r=4.実際、n!/5=(q+r/5)(n−1)! に (2) の除法を順に適用すればこの桁列を得る。例えば r=3 の下位への余りは 15(n−2)!,15(n−3)!,0 と続き、r=4 でも同様に計算できる。各桁は対応する上限以下である。

別解

解法2

方針

階乗進法の桁上限を使って、存在は最大桁からの除法、一意性は最上位の相違から示す。(3)は n=5q+r として余りを下位桁へ送る。

解答

(1) k⋅k!=(k+1)!−k!なので、k=1,…,m について加えると∑k=1mk⋅k!=(m+1)!−1.右辺は [1,0,…,0]m+1−1 である。

(2)
m!≦N<(m+1)! を満たす m を選び、N を m!、
(m−1)!,…,1! で順に割る。各商を am,am−1,…,a1
とすれば、余りが次の階乗未満なので 0≦ak≦k となり、
am≠0 である。これで存在が分かる。

一意性は最上位の異なる桁を j として示せる。2つの表示の差では、
第 j 桁の差の絶対値は少なくとも j! である。一方、それより下の
桁で打ち消せる最大値は (1) より∑k=1j−1k⋅k!=j!−1にすぎない。矛盾だから表示は一意である。

(3) n=5q+r (0≦r≦4) とする。省略した末尾はすべて0と約束すればn!5={[q,0,…,0]n−1(r=0),[q,q,0,…,0]n−1(r=1),[q,2q,2q,0,…,0]n−1(r=2),[q,3q+1,q,q,0,…,0]n−1(r=3),[q,4q+2,2q,4q,4q,0,…,0]n−1(r=4).これはn!5=(q+r5)(n−1)!から始め、分数部分に (n−1)=5q+r−1 を掛けて次の桁へ送れば順に得られる。
例えば r=4 では分数部分の分子が4, 2, 4, 4, 0と移り、上の5桁になる。各桁はそれぞれの桁番号以下であり、(2)の一意性から
これが求める表示である。

総評

難度は8、計算量は7。階乗進法の桁上限、一意性、n mod 5 の5場合を整数計算で照合した。 2解法の結論を照合し、定義域、端点、必要十分性、等号条件を再確認した。 図は論証を補助するものに限定し、図の縮尺に依存しない式による説明も併記している。

Evolton Pro

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

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

出典: 東京大学 1994年度 後期日程 第2次学力試験 数学。問題文はHTML表示のために再入力・数式組版しています。