Q.89 「1≦k≦114514におけるf(k)の最大値」

Q.89 ☆8 [1991JMO予選改題]

自然数に対して定義される関数$f$は,

$f(1)=1$

$f(2n)=f(n)$

$f(2n+1)=f(n)+1$

を満たしている。 $1\le k\le 114514$における$f(k)$の最大値, 及びその時の$k$の値を全て求めよ。

解答

$f(n)$は $ n $を2進表示したときの$1$の桁の個数であることを数学的帰納法により証明する。

仮定より$n=1$はOK. $1\le k\le n$ なる任意の自然数$k$で題意が成り立つとする。

$n+1$ の2進表示を $a_{ m }a_{m - 1}\cdots a_{2}a_{1}$ とする。

$n+1$ が偶数ならば $a_{1}=0$である。よって $\dfrac{n+1}{2}$ の2進表示は$a_{ m }a_{m - 1}\cdots a_{2}$ なので

$n+1$と$\dfrac{n+1}{2}$の2進表示の1の個数は同じである。

$f(n+1)=f\left(\dfrac{n+1}{2}\right)$ だから $k=n+1$ のときにも成り立つと言える。

$n+1$ が奇数ならば, $a_1=1$ なので $n$ の2進表示は $a_{ m }a_{m - 1}\cdots a_{2}0$

$\dfrac{n}{2}$ の2進表示は $a_{ m }a_{m - 1}\cdots a_{2}$ で, 帰納法の仮定より$f\left( \dfrac{n}{2}\right)$ は$\dfrac{n}{2}$の2進表示の1の個数。

明らかに$f\left(\dfrac{n}{2}\right) +1 =f(n+1)$ が成り立っている。

以上より 任意の$ n $に対して成り立つ。

$114514=11011111101010010_{2} $

で,これは17桁であり, $ k $ は $\underbrace{11\cdots 11}_{17} {}_{2} $ 未満なので $f(k) < 17$ である。$f(k)=16$ である$ k $ をすべて求めればよい。

このような$ k $のうち,2進法で16桁なら $k=\underbrace{11\cdots 11}_{16} {}_{2} $ に限り, 10進法で$ 65535 $ である。

$17$桁なら, $\underbrace{11 \cdots 11}_{17} {}_{2} - 1\underbrace{0\cdots 00}_{i} {}_{2} $ ($i=0,1,\cdots, 15$)という数字に限られる。10進法で $131071-2^{i}$ と表される。これが114514以下である$i$は $i=15$に限る。このとき, $ k=114514-32768=98303 $

以上より $k=65535,98303$

コメント

2進法って見抜くのが一番のポイントです。見抜けたら大したもんです。 114514, 適当に選んだわけじゃないんですよね。$131071-2^{14}=114687$ となって$i=14$はかなりギリギリで排除されるんです。