トップ› 名古屋大学› 1981年› 理系第4問

名古屋大学 1981年理系第4問解説

方針・初手

$s(l)$ は、自然数 $l$ を $p$ 進法で表したときの各桁の数字の和を意味する。 $p^n - l$ の各桁の和 $s(p^n - l)$ を考えるために、$p^n$ から $l$ を引く計算（繰り下がり）を考える。 $l$ を下位の桁から見たとき、連続して $0$ が並ぶ個数によって、繰り下がりの影響が及ぶ範囲が変わる。そこで、$l$ の $p$ 進展開において、$0$ でない最小の桁の位に着目して計算を進める。

解法1

$1 \leqq l \leqq p^n - 1$ であるから、$l$ の $p$ 進法における各桁の数字 $a_0, a_1, \dots, a_{n-1}$ のうち、少なくとも $1$ つは $0$ ではない。そこで、$0$ でない最も下の桁の位を $m$ とする。すなわち、$m$ は $0 \leqq m \leqq n-1$ を満たす整数であり、

$$ a_0 = a_1 = \dots = a_{m-1} = 0, \quad a_m \neq 0 $$

を満たすとする（$m=0$ のときは、$a_0 \neq 0$ とする）。このとき、$l$ は

$$ l = \sum_{k=m}^{n-1} a_k p^k $$

となるから、$s(l)$ は次のように表される。

$$ s(l) = \sum_{k=m}^{n-1} a_k $$

次に、$p^n - l$ の $p$ 進法における各桁の数字を考えるために、$p^n$ を次のように変形する。

$$ p^n = (p-1)p^{n-1} + (p-1)p^{n-2} + \dots + (p-1)p^{m+1} + p \cdot p^m $$

これを用いて $p^n - l$ を計算すると、

$$ p^n - l = \sum_{k=m+1}^{n-1} (p-1)p^k + p \cdot p^m - \sum_{k=m}^{n-1} a_k p^k $$

$$ = \sum_{k=m+1}^{n-1} (p - 1 - a_k)p^k + (p - a_m)p^m $$

となる。ここで、$0 \leqq a_k \leqq p-1$ であり、さらに $a_m \neq 0$ であるから $1 \leqq a_m \leqq p-1$ となる。したがって、各項の係数について、

$$ 1 \leqq p - a_m \leqq p-1 $$

$$ 0 \leqq p - 1 - a_k \leqq p-1 \quad (k = m+1, \dots, n-1) $$

が成り立つため、これが $p^n - l$ の $p$ 進展開そのものである。よって、$s(p^n - l)$ はこの各桁の数字の和であるから、

$$ s(p^n - l) = \sum_{k=m+1}^{n-1} (p - 1 - a_k) + (p - a_m) $$

となる。これより、$s(l) + s(p^n - l)$ を計算する。

$$ s(l) + s(p^n - l) = \sum_{k=m}^{n-1} a_k + \sum_{k=m+1}^{n-1} (p - 1 - a_k) + (p - a_m) $$

$$ = a_m + \sum_{k=m+1}^{n-1} a_k + \sum_{k=m+1}^{n-1} (p - 1 - a_k) + (p - a_m) $$

$$ = (a_m + p - a_m) + \sum_{k=m+1}^{n-1} \{a_k + (p - 1 - a_k)\} $$

$$ = p + \sum_{k=m+1}^{n-1} (p - 1) $$

このシグマの項数は $(n-1) - (m+1) + 1 = n - m - 1$ 個であるから、

$$ s(l) + s(p^n - l) = p + (n - m - 1)(p - 1) $$

となる。ここで、$n, p$ は定数であり、$p \geqq 2$ より $p - 1 > 0$ である。したがって、$s(l) + s(p^n - l)$ の値が最小となるのは、$m$ が最大のときである。 $1 \leqq l \leqq p^n - 1$ であるから、存在しうる $m$ の最大値は $n-1$ である。 $m = n-1$ のとき、最小値は

$$ p + \{n - (n-1) - 1\}(p - 1) = p $$

となる。また、このとき $m = n-1$ であることから、各桁の数字は $a_0 = a_1 = \dots = a_{n-2} = 0$ かつ $a_{n-1} \neq 0$ を満たす。したがって、最小値を与える $l$ は

$$ l = a_{n-1} p^{n-1} $$

の形であり、$a_{n-1}$ は $1 \leqq a_{n-1} \leqq p-1$ を満たす整数である。

解説

本問は $n$ 桁の $p$ 進数（最高位に $0$ が入ることを許す）の各桁の和に関する問題である。十進法で $10^n - l$ を計算する際、下位桁に $0$ が続く場合はその上の桁から繰り下がりが行われる。それと同様の処理を $p$ 進法で一般化して議論すればよい。 $l$ の下から連続する $0$ の個数によって繰り下がりの影響が及ぶ桁数が変わるため、末尾の $0$ の個数（あるいは初めて $0$ でない数字が現れる桁）に注目して文字でおくことが最大のポイントとなる。