преобразования двоичных представлений

[maxal]

Над числами записанными в двоичной системе счисления разрешается производить следующее преобразование: вставить знаки "+" в произвольных местах и трактовать получающееся выражение как сумму двоичных чисел меньшей длины.
Пример возможного преобразования:

$$110101_2 \rightarrow 11_2 + 01_2 + 01_2 = 3 + 1 + 1 = 5 = 101_2.$$

Доказать, что любое натуральное число можно превратить в 1 за не более чем два преобразования.

[TOTAL]

Число, имеющее в двоичной записи $n$ единиц, разобьем на куски из 4 единиц
(и несколько кусков по 3 единицы): $n=A \cdot 4 + B \cdot 3, \;\; B=0,1,2,3$

Любой кусок из 3 единиц можно разбить на части с суммой 4.
Любой кусок из 4 единиц можно разбить на части с суммой 4 и 8.
Любой кусок из 5 единиц можно разбить на части с суммой 8 либо 16.
Любой кусок из 9 единиц можно разбить на части с суммой 16.

Кусками из 4 единиц можно регулировать общую сумму так, чтобы она составляла степень двойки. Действительно, среди чисел $A + k +B, \;\; k=0,1,2,...,A$ всегда найдется степень двойки, за исключением случая $A=2^s-2, \; B=3.$ Но в этом случае заменим троешные куски на кусок из девяти единиц с суммой 16.

[Sonic86]

upd: фигня удалена

[TOTAL]

Sonic86 в сообщении #510715 писал(а):

Случай $n=1 \dots 1$ - 2 варианта:
$n=1 \dots 01 \vee n=1 \dots 11$
Случай $1 \dots 11 \to 1 \dots 1+1$ сводится к случаю $n=1 \dots 0$.
Случай $1 \dots 01 \to 1+ \dots 0+1$ сводится к случаю $n=1 \dots 0$ (вставили 2 знака $+$).

Где здесь степень двойки за одно преобразование?

[Sonic86]

TOTAL в сообщении #510720 писал(а):

Где здесь степень двойки за одно преобразование?

Блин, сейчас удалю...

[maxal]

TOTAL в сообщении #510713 писал(а):

Число, имеющее в двоичной записи $n$ единиц, разобьем на куски из 4 единиц
(и несколько кусков по 3 единицы): $n=A \cdot 4 + B \cdot 3, \;\; B=0,1,2,3$

Любой кусок из 3 единиц можно разбить на части с суммой 4.
Любой кусок из 4 единиц можно разбить на части с суммой 4 и 8.
Любой кусок из 5 единиц можно разбить на части с суммой 8 либо 16.
Любой кусок из 9 единиц можно разбить на части с суммой 16.

Кусками из 4 единиц можно регулировать общую сумму так, чтобы она составляла степень двойки. Действительно, среди чисел $A + k +B, \;\; k=0,1,2,...,A$ всегда найдется степень двойки, за исключением случая $A=2^s-2, \; B=3.$ Но в этом случае заменим троешные куски на кусок из девяти единиц с суммой 16.

Утверждения про куски нужно бы доказать.
И, кстати, зачем вам утверждение про 5 единиц?
А в последнем случае, как я понимаю, вы берете $k=2^s-14$. Но что если, например, $s=3$?

[TOTAL]

maxal в сообщении #510747 писал(а):

И, кстати, зачем вам утверждение про 5 единиц?
А в последнем случае, как я понимаю, вы берете $k=2^s-14$. Но что если, например, $s=3$?

Утверждение про 5 нужно потому, что исходное число может иметь 5 единиц.

В последнем случае $k=2^s-2$ (каждый четверошный кусок разбит на части с суммой 8)

Утверждения про куски доказываются простым перебором.
Например, кусок в 9 единиц разбиваем на куски 2, 2, 5. Из куска в 2 единицы всегда можно составить сумму 2 и 3. А из куска в 5 единиц можно составить одну из сумм 10, 11, 12. Поэтому из куска в 9 единиц всегда можно составить сумму 16.