第2問

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

（

a_1,a_2,\ldots,a_{100}

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

n

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

n

を求めよ。

ステップ 3/5: 指数が小さい場合と結論

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

a_r\le100\Longrightarrow cn\le2^0+2^1+\cdots+2^{100}=n

詳しい解説

一方 $a_r\le100$ なら、二進展開は $\{2^0,2^1,\ldots,2^{100}\}$ から選んだ高々 $100$ 個の二べきの和である。したがって $cn\le2^0+2^1+\cdots+2^{100}=n$ 。 $cn$ は $n$ の正の倍数なので、等号なら $c=1$ であり、さらに $2^0,\ldots,2^{100}$ の $101$ 個すべてが現れなければならない。しかし高々 $100$ 個の二べきしか使っていないので不可能である。この矛盾により $n=2^{101}-1$ の正の倍数は fancy ではなく、下界と合わせてこれが最小の整数である。