第2問

2^{a_1}+2^{a_2}+\cdots+2^{a_{100}}

（

a_1,a_2,\ldots,a_{100}

は互いに異なるとは限らない非負整数）の形に表せる正整数を「fancy」と呼ぶ。

n

のどの倍数も fancy な数にならないような最小の正整数

n

を求めよ。

ステップ 4/5: 反例が最小のとき：指数が大きい場合

前のステップ次のステップ

cn=2^{a_1}+\cdots+2^{a_r},\ r\le100,\ a_r\ge101\Longrightarrow 2^{a_r}=2^{a_r-101}n+2^{a_r-101}

詳しい解説

背理法として、 $n=2^{101}-1$ のある倍数 $cn$ が fancy であるとする。重複する二べきを二進法の繰り上がりでまとめれば、高々 $100$ 個の相異なる二べきによる表示が得られるので、そのような表示で $c$ を最小に取り、最大指数を $a_r$ とする。 $a_r\ge101$ ならば $2^{a_r}=2^{a_r-101}n+2^{a_r-101}$ なので、 $2^{a_r}$ を $2^{a_r-101}$ に置き換えると $cn$ は $2^{a_r-101}n$ だけ減少し、高々 $100$ 個の二べきをもつ $n$ のより小さい正の倍数が得られ、 $c$ の最小性に矛盾する。