Азиатско-Тихоокеанская математическая олимпиада, 2016 год

Натуральное число назовем чудесным, если оно может быть представлено в виде \[{{2}^{{{a}_{1}}}}+{{2}^{{{a}_{2}}}}+\ldots +{{2}^{{{a}_{100}}}},\] где ${{a}_{1}}$, ${{a}_{2}}$, $\ldots$, ${{a}_{100}}$ — неотрицательные целые числа, не обязательно различные. Найдите наименьшее натуральное $n$ такое, что ни одно натуральное число, делящееся на $n$, не является чудесным.

Комментарий/решение

Решение: Заменим $n=100.$ Докажем, что ответ $2^{n+1}-1.$

Минимальность: Заметим, что

$$ 2^{n+1}-2=2^n+2^{n-1}+\ldots+2^{1}=B,$$

$$2^n-1=2^{n-1}+\ldots+2^{1}+2^{0}=A,$$

а так же для любого $0 \le x \le 2^n - 1$ существует следующая запись

$$x = \sum_{i=0}^{n-1}\varepsilon_i \cdot 2^i ,\forall i: \varepsilon_i\in \{0,1\}$$

тогда $x+A$ пробегает все значения от $A$ до $B,$ при этом оно является чудесным.

Так же очевидно, что для любого $1\le x \le 2^n-2$ на отрезке $[A,B]$ найдется число кратное $x.$ $\square$

Делимость: Заметим, что $2^{n+1+k}\equiv 2^{k}\pmod {2^{n+1}-1}$

Допустим некоторое число чудесное число $2^{a_1}+...+2^{a_n}$ делится на $2^{n+1}-1.$

Ясно, что можно принять $0\le a_i \le n.$ Если среди этих степеней двоек найдутся два одинаковых, скажем $2^k,$

то просуммируем их и рассмотрим остаток $2^{k+1}$ по модулю ${2^{n+1}-1}.$

Продолжаем данный процесс пока не останутся только различные степени. В конце количество слагаемых будет не более чем $n,$ они все различные и степени лежат от $0$ до $n.$ Очевидно это число будет не более чем $2^1+\ldots+2^n=2^{n+1}-2$ и больше 0, что не может делится на искомое число. $\square$