拾い物 - 球面倶楽部零八式 mark II

今回の数検一級の問題らしく最近これ考えてたけど、面白い pic.twitter.com/N48qLGD2fW
— MARTH (@marth_omc) 2022年4月17日

小中学生の頃、 $11^4=14641$ となり二項係数が並ぶことに気がついた人も多いだろうが、これは $11^5$ でくりあがりが発生してうまくいかない。しかし、
$101^5=10510100501$
とすればうまくいくことを考えたことがある人なら一瞬で終わる問題だ。

次数があるので $f(x)$ は1変数多項式である． $n$ 次だとして $f(x)=a_nx^n+\cdots+a_1 x+a_0$ とする( $a_i\geqq 0$ ， $a_n\gt 0$ )．

$f(N)=a_n N^n+\cdots+a_1N+a_0$
が与えられたとき，位取り記数法の原理から， $N\gt \max_{i}\{a_i\}$ のとき:
$f(N)$ を $N$ でくりかえし割ることによって得られる余りは順番に $a_0,a_1,\ldots, a_n$ となり， $f(x)$ を求めることができる．

よって， $f(x)$ の係数の最大値を求めれば良い．

ここで $f(1)$ は係数の和であるから，
$f(1)=a_n+\cdots+a_0\geqq \max_{i}\{a_i\}$ (等号は $f(x)$ が単項式のとき(条件から1次式以上))
となるので， $N=f(1)+1$ とすれば確実に $N$ は $f(x)$ の係数の最大値より大きくなる．

以上から， $n_1=1$ ， $n_2=f(1)+1$ とおけば $f(x)$ を決定することができる．

特に10進数でわかり易くするためには， $10^M\gt f(1)$ なる $M$ を求めれば良いので、 $M=\lfloor \log f(1)\rfloor +1$ とおくと $n_2=10^M$ ，つまり $f(10^M)$ を計算し，右から $M$ 桁ずつ区切って左から並べれば $a_n,a_{n-1},...,a_0$ が並ぶので、 $f(x)$ を決定することができる．

例えば、 $f(x)=3x^3+10x+1$ のとき， $f(1)=14$ だから $n_2\gt 15$ であれば $f(x)$ を決定できるが， $M=2$ ，つまり $n_2=100$ を代入すると
$f(100)=3001001$
となり，これを右から2桁ずつ区切ると $3|00|10|01$ となり， $f(x)=3x^3+0x^2+10x+1$ と $f(x)$ を求めることができる．

$x$ の多項式は言わばくりあがりのない $x$ 進法という話があり、そのくりあがりがおきないような十分大きな $10$ の羃乗を代入すれば良く、その冪乗を知るためには係数の最大値を評価すれば良いと考えつけば良い(もちろん係数が負となる場合もあるので、あまり厳密な話ではない)。

なお、 $f(10^{M+1})$ を代入して $M+1$ 桁ずつ区切っても良い．10進数を使っている人類にとっては10の冪乗を代入するほうが係数の10進数表記がそのまま得られるのでうれしいという考え方での最低ラインが $10^M$ ということ．

なお， $f(1)=K\neq 1$ （つまり $f(1)\gt 1$ ）であれば $(n_1,n_2)=(1,f(1))$ でも $f(x)$ が決まることに注意しておく．というのも，

(i) $\max_{i}\{a_i\}=K$ を仮定すると， $a_n\neq 0$ より
$f(K)=K\cdot K^n$ であるから， $f(K)$ を $K$ 進数で表すと $10\cdots 0$ となる．

(ii) $\max_{i}\{a_i\}\lt K$ を仮定すると， $f(1)=K$ から少なくとも2つの $a_i$ が非零となり $f(K)$ を $K$ 進数で表すと少なくとも2つの桁が非零となる．

以上から， $f(K)$ を $K$ 進数で表すしたとき $10\cdots 0$ となる場合，
$f(K)=Kx^n$
( $n$ は $f(K)$ を $K$ 進数で表したときの桁数から2を引いたもの)
となり，それ以外の場合は $f(K)$ を $K$ 進数で表したときの数字を右から $a_0,a_1,\ldots,a_n$ としたときの $f(x)=a_nx^n+\cdots+a_1 x+a_0$ となることがわかる．よって $f(1)=K\neq 1$ （つまり $f(1)\gt 1$ ）であれば $(n_1,n_2)=(1,f(1))$ でも $f(x)$ が決まる．