Азия-тынық мұхит математикалық олимпиадасы, 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$