Задача М650‍‍‍

а) $\{1,2,4,8,16,32,\ldots\}$‍.‍

б) $\{2,3,4,8,16,32,64,\ldots\}$‍.‍ Из подпоследовательности $\{4,8,16,\ldots\}$‍‍ можно получить числа вида $4k$‍,‍ а из $\{2,3\}$‍‍ — числа 2, 3 и 5.

в) $\{-1,2,-4,8,-16,32,-64,\ldots\}$‍.‍

Доказательство. Покажем по индукции, что из набора $(-1,2,-4,\ldots,\pm2^n)$‍‍ можно единственным образом получить в виде (*) все целые числа (кроме нуля) из промежутка от $-1-4-16-\ldots-{}$‍‍(последний отрицательный член набора) до $2+8+32+\ldots+{}$‍‍(последний положительный член набора).

База индукции ($n=1$‍)‍ очевидна.

Индукционный шаг. Предположим, для определённости, что при $2^n$‍‍ — знак «плюс» (т. е. $n$‍‍ — нечётное) и что из набора $(-1,2,-4,\ldots,2^n)$‍‍ можно единственным образом получить все целые числа (кроме нуля) от $-1-4-16-\ldots-2^{n-1}$‍‍ до $2+8+32+\ldots+2^n$‍.‍

Добавив к набору $(-1, 2, -4, \ldots,2^n)$‍‍ член $-2^{n+1}$‍,‍ мы получим серию новых целых чисел, представляемых в виде (*) единственным образом (содержащих член $-2^{n+1}$‍‍ в качестве слагаемого); от $-1-4-16-\ldots-2^{n-1}-2^{n+1}$‍‍ до $2+8+32+\ldots \ldots+2^n-2^{n+1}$‍.‍ Объединяя их со «старыми» числами, мы получим все целые числа от $-1-4-16-\ldots-2^{n-1}-2^{n+1}$‍‍ до $2+8+32+\ldots+2^n$‍:‍ поскольку $$(2+8+32+\ldots+2^n-2^{n+1})+1=-1-4-16-\ldots-2^{n-1},$$ числа «состыковываются» (напоминаем, что мы взяли $n$‍‍ нечётным).

Утверждение доказано.

г) Такой последовательности не существует.

Доказательство от противного. Пусть такая последовательность существует и пусть $a_1$‍‍ — её член, отличный от $-1$‍.‍ Тогда числа $1+a_1$‍‍ и $1-a_1$‍‍ представляются в виде (*) единственным образом, поскольку $a_1\ne0$‍‍ и $a_1\ne1$‍.‍ Если $a_n$‍‍ — член последовательности, отличный от $-1$‍‍ и $a_1$‍,‍ не входящий в представления чисел $1+a_1$‍‍ и $1-a_1$‍,‍ то числа $1+a_1+a_n$‍‍ и $1-a_1+a_n$‍‍ допускают разложения (*), в которых участвует $a_n$‍.‍ С другой стороны, в представлении (*) числа $1+a_n$‍‍ не участвует $a_n$‍‍ (иначе, выкинув $a_n$‍,‍ мы получили бы представление единицы). Если в этом представлении встречается член $a_1$‍,‍ то выкинем его, а если не встречается, то добавим. В любом случае мы получим разложение (*) для одного из чисел $1+a_1+a_n$‍,‍ $1-a_1+a_n$‍,‍ в которое не входит член $a_n$‍.‍ Получили противоречие с единственностью представления в виде (*).