Evolton

名古屋大学 1981年度 前期日程 第2次学力試験 整数・場合の数理系数学 第4問(a)

p,nは自然数でp≧2とする.
pnより小さい自然数lを,l=∑k=0n−1akpk(akは0≦ak≦p−1なる整数)と表し,s(l)=∑k=0n−1akとおく.
このとき,s(l)+s(pn−l) (1≦l≦pn−1)の最小値とそれを与える自然数lをすべて求めよ.

難易度6/ 10計算量5/ 10目安20分

整数、場合の数 剰余分類、場合分け、一般化

方針

p 進法で下位から見て最初に0でない桁を r とする。pn−l の筆算では、r 桁目が p−ar、それより上が p−1−ak になる。これを s(l) と足すと ak が消え、p+(n−1−r)(p−1) となる。最小化は r を最大にするだけなので、r=n−1 として対応する l を列挙する。

解答

l≧1 であるから、下位から見て初めて0でない桁がある。すなわち a0=a1=⋯=ar−1=0,ar≠0 となる整数 r がただ一つ定まる。ただし 0≦r≦n−1 である。 pn−l を p 進法の筆算で求める。下位 r 桁は0で、r 桁目で初めて借り下がりが起こる。したがって pn−l の各桁は、0 桁目から r−1 桁目までは0、r 桁目は p−ar であり、r+1 桁目から n−1 桁目までは p−1−ak である。

よってs(pn−l)=p−ar+∑k=r+1n−1(p−1−ak)である。一方s(l)=ar+∑k=r+1n−1akであるからs(l)+s(pn−l)=p+∑k=r+1n−1(p−1)=p+(n−1−r)(p−1)である。

これは r が大きいほど小さい。よって最小は r=n−1 のときにとられ、その値は p である。このとき a0=a1=⋯=an−2=0,1≦an−1≦p−1 なので l=apn−1(a=1,2,…,p−1) である。

したがって最小値を与える自然数は pn−1, 2pn−1, …, (p−1)pn−1 である。

別解

解法2(全桁が p-1 の数との補数を使う)

方針

pn−l=(pn−1)−(l−1) と書く。l の末尾の0の個数を r とし、
pn−1 に対する p 進法の補数を利用する。

解答

l の p 進表示の末尾に並ぶ0の個数を r とする。0≦r≦n−1 である。
l から1を引くと、末尾の r 個の0は p−1 となり、その直前の非零桁が1減るのでs(l−1)=s(l)−1+r(p−1).またpn−l=(pn−1)−(l−1)であり、pn−1 の各桁はすべて p−1 である。よってs(pn−l)=n(p−1)−s(l−1).したがってs(l)+s(pn−l)=p+(n−1−r)(p−1).最小値は r=n−1 のときの p であり、そのときl=pn−1,2pn−1,…,(p−1)pn−1.

総評

難度は10段階中6、計算量は10段階中5程度。想定時間は18分から24分程度。十進法版と同じ借り下がりの構造を、一般の p 進法で書く問題である。採点では、最初に0でない桁 r の定義、p−ar と p−1−ak の区別、最小値が r=n−1 で出ることが重要である。記号は増えるが、筆算の構造を崩さなければ難しくない。

Evolton Pro

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

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

出典: 名古屋大学 1981年度 前期 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。