Evolton

名古屋大学 1999年度 前期日程 第2次学力試験理系数学 第4問

nを2以上の自然数とする.条件k1≧1,⋯ ,kn−1≧1,kn≧0をみたすn個の整数の組(k1, k2, ⋯ , kn)に対して,
自然数m(k1, k2, ⋯ , kn)を次のように定める.m(k1, k2, ⋯ , kn)=2k1+k2+⋯+kn−2k2+⋯+kn−2k3+⋯+kn−⋯−2kn(1) 1999=m(k1, k2, k3, k4)となる(k1, k2, k3, k4)を求めよ.

(2) m(k1, k2)=m(l1, l2)であれば,k1=l1,k2=l2が成り立つことを示せ.

(3) n≧3のとき,m(k1, k2, ⋯ , kn)=m(l1, l2, ⋯ , ln)であれば,kj=lj(j=1, 2, ⋯ , n)が成り立つことを示せ.

難易度7/ 10計算量6/ 10目安25分

整数、数列、論証・証明 素因数分解、数学的帰納法、一意性証明

方針

式の末尾から 2kn をくくると、残った括弧が奇数になる構造を利用する。具体値1999では、奇数であることからまず k4=0 を決め、次に 1999+1 の2の累乗部分を読んで k3,k2,k1 を順に決める。一般の一意性は、m(k1,…,kn)=2kn{m(k1,…,kn−1)−1} と書き、2で割れる回数と奇数部分を比較して後ろから帰納的に示す。

解答

(1) n=4 のとき m(k1,k2,k3,k4)=2k4{2k1+k2+k3−2k2+k3−2k3−1} である。括弧の中は「偶数 − 偶数 − 偶数 −1」なので奇数である。1999 は奇数だから、2k4 の部分は 1 でなければならず、k4=0 である。

したがって 2k1+k2+k3−2k2+k3−2k3−1=1999 であり、移項して 2k3(2k1+k2−2k2−1)=2000 となる。ここで括弧内は奇数である。一方 2000=24⋅125 だから k3=4 であり、奇数部分について 2k1+k2−2k2−1=125 すなわち 2k2(2k1−1)=126 である。2k1−1 は奇数で、126=2⋅63 だから k2=1, 2k1−1=63 となる。よって k1=6 である。したがって (k1,k2,k3,k4)=(6,1,4,0) である。

(2) n=2 のとき m(k1,k2)=2k1+k2−2k2=2k2(2k1−1) である。ここで 2k1−1 は奇数である。したがって m(k1,k2) を2で割れるだけ割った回数、すなわち2の累乗部分から k2 が一意に決まる。 k2 が決まれば、奇数部分 2k1−1 も一意に決まる。関数 k1↦2k1−1 は自然数 k1 に対して単調に増加するので、k1 も一意に決まる。よって m(k1,k2)=m(l1,l2) ならば k1=l1,k2=l2 である。

(3) n≧3 とする。定義式から末尾の 2kn をくくると m(k1,k2,…,kn)=2kn{m(k1,k2,…,kn−1)−1} である。ここで、元の条件では kn−1≧1 なので、m(k1,k2,…,kn−1) は偶数である。したがって m(k1,k2,…,kn−1)−1 は奇数である。

同様に m(l1,l2,…,ln)=2ln{m(l1,l2,…,ln−1)−1} で、括弧内は奇数である。いま m(k1,k2,…,kn)=m(l1,l2,…,ln) と仮定すると、両辺の2の累乗部分を比べて kn=ln が分かる。さらに奇数部分を比べて m(k1,k2,…,kn−1)−1=m(l1,l2,…,ln−1)−1 だから m(k1,k2,…,kn−1)=m(l1,l2,…,ln−1) である。

この議論を後ろから繰り返すと、kn=ln,kn−1=ln−1,…,k3=l3 が順に得られ、最後に m(k1,k2)=m(l1,l2) が残る。これは(2)より k1=l1,k2=l2 を与える。したがって kj=lj(j=1,2,…,n) である。

別解

解法2

方針

与えられた自然数 m から添字を復元する手順を構成する。まず m を2で割れる回数が末尾の kn であり、奇数部分に1を足すと1段短い m が戻る。この復号操作を繰り返せば、全ての kj が一意に決まる。

解答

(1)
1999 を、2で割れるだけ割った回数と残る奇数部分に分けながら復号する。1999は奇数なのでk4=0,m(k1,k2,k3)=2000.2000=24⋅125 よりk3=4,m(k1,k2)=126.126=2⋅63 よりk2=1,2k1−1=63,したがって k1=6 である。よって(k1,k2,k3,k4)=(6,1,4,0).(2)m(k1,k2)=2k2(2k1−1)であり、2k1−1 は奇数である。従って、両辺が等しければ2で割れる回数から k2=l2 が分かり、残る奇数部分から2k1−1=2l1−1となるので k1=l1 である。

(3)
一般にm(k1,…,kn)=2kn{m(k1,…,kn−1)−1}に注意する。kn−1≧1 だから短い方の m は偶数であり、括弧内は奇数である。

従って、与えられた m を2で割れるだけ割った回数は必ず kn である。奇数部分を q とすればm(k1,…,kn−1)=q+1となる。これを繰り返せば、末尾から kn,kn−1,…,k3 が一意に復元され、最後はm(k1,k2)=2k2(2k1−1)から、(2)によって k2,k1 も一意に復元される。同じ値を与える2組にこの操作を並行して施せばkj=lj(j=1,2,…,n)が従う。

総評

各段階で2の累乗部分と奇数部分を分離する問題である。末尾の指数を2進付値として読み、奇数部分へ1を足して1段短い数へ戻す復号手順が一意性をそのまま証明する。1999からは順に k4=0,k3=4,k2=1,k1=6 が復元される。添字条件 kn−1≧1 が括弧内を奇数にする。

Evolton Pro

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

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

出典: 名古屋大学 1999年度 前期 理系 第4問。問題文はHTML表示のために再入力・数式組版しています。