MathLabs

第2問

2a1+2a2+⋯+2a1002^{a_1}+2^{a_2}+\cdots+2^{a_{100}}(a1,a2,…,a100a_1,a_2,\ldots,a_{100} は互いに異なるとは限らない非負整数)の形に表せる正整数を「fancy」と呼ぶ。nn のどの倍数も fancy な数にならないような最小の正整数 nn を求めよ。
ステップ 1/5: 答えを示す
n=2101−1n=2^{101}-1
詳しい解説

主張は、1≤k<2101−11\le k<2^{101}-1 を満たすすべての正整数 kk にはある fancy な倍数が存在する一方、n=2101−1n=2^{101}-1 の倍数はどれも fancy でないというものである。kk を二進法で書くと立っているビットは高々 100100 個なので、ある r≤100r\le100 に対して k=2a1+⋯+2ark=2^{a_1}+\cdots+2^{a_r} と書ける。