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$はかなりギリギリで排除されるんです。