XV математическая олимпиада «Шелковый путь», 2016 год

Пусть $P(n)$ это количество способов разбить натуральное число $n$ на сумму степеней двойки, при этом порядок не имеет значение. Например $P(5) = 4$, так как $5=4+1=2+2+1=2+1+1+1=1+1+1+1+1$. Докажите, что для любого натурального $n$ верно тождество $$P(n) + (-1)^{a_1} P(n-1) + (-1)^{a_2} P(n-2) + \ldots + (-1)^{a_{n-1}} P(1) + (-1)^{a_n} = 0,$$ где $a_k$ — количество единиц в двоичной записи числа $k$. ( Д. Елиусизов )

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

Для $n=1$ соотношение справедливо, отметим сразу что $P(2k)=P(2k+1)$ (1) где $1 \leq k \leq t$ так как для нечетных $n$ количество способов разбиения равно четному с добавлением $2^0=1$.

1)

Для любого $P(2k)$ число можно рекуррентно представить в виде других предыдущих разбиении, для этого разобьем число $n$ таким образом чтобы первые фиксированные числа были вида $2^a,2^{a-1},2^{a-2}....,2^1$ и плюс к ним соответственно $P(n-2^a),P(n-2^{a-1}),...P(n-2^1)$ где $2^a$ первое максимальное приближенная степень к числу $n$, отметим так же что $n-2^a, n-2^{a-1},....,n-2^1$ должны также разлагаться на слагаемые $2^b \leq 2^a$ (2) и т.д для других и последнее представление числа единицами $\underbrace{2^0+2^0...+2^0}_{\mbox{$n$ слагаемых}}=1$ один способ.

2) Опишем процесс для первых $10$-ти чисел для наглядности, для удобства $P(0)=1$ тогда

$P(10)=P(2)+P(6)+P(8)-(P(0)+P(4))+1$

$P(8)=P(0)+P(4)+P(6)-P(2)+1 $

$P(6)=P(2)+P(4)-P(0)+1$

$P(4)=P(0)+P(2)+1$

$P(2)=P(0)+1$

$P(1)=1 $

Отдельно

$P(6)=P(2)+ \underbrace{P(4)-P(0)}_{\mbox{ }}+1$ обведены количество способов представить число $6-2=4$, слагаемые которых не превышает $2$ а это и есть число способов представить число $P(4)$ минус число способов представить число $P(4)=P(0)+P(2)+1$ начинающие с $4>2$ это $P(2)+1=P(4)-P(0)$

Аналогично $P(10)=P(2)+P(6)+P(8)-(P(0)+P(4))+1$ в скобках $P(8)-(P(0)+P(4))$ это число способов представить число $2$ с той же аналогией как с первым и это есть число способов $P(8)=P(0)+P(4)+P(6)-P(2)+1$ минус число способов представить числа в виде $2^3,2^2$ это $P(8)-1-P(4)=P(6)-P(2)+1$ и т.д для других с разных разбиении вида $2^t$.

3) Назовем инверсией оперцию $P(2k)=P(2k-1)$ по $(1)$ , отметим что при рекуррентном построении чисел $P(2k) , P(2k-2)$ будут присутствовать все числа от $1,P(1)....P(2k)$ так как все $P(a)$ во втором представлении будут понижены на $2$ единицы и так как $P(2k-2)=P(2k-1)$ и инверсировав все числа в представлении $P(2k-2)$ получим в сумме весь набор $P(a),\ 1 \leq a \leq 2k$.

4) Рассмотрим частный случай для $n=16$ (так как весь алгоритм построения $P(n)$ ясен и обобщается аналогично с абсолютно теми же рассуждениями)

$P(16)=P(0)+P(8)+P(12)-P(4)+P(14)-(P(6)+P(10)-P(2))+1$

Числа представленные в виде $P(n-2^a)$ идут со знаком $+$ действительно, так как по построению мы от них отнимаем все те числа которые будут справедливы для построению по (2), тогда его иначе можно представить как

$P(16)=P(16-2^4)+P(16-2^3)+P(16-2^2)-[P(16-2^2-2^3)]+P(16-2^1)-[P(16-2^1-2^3)+P(16-2^1-2^2)-P(16-2^1-2^2-2^3)]+1 $ отметим что числа с четным количеством слагаемых $2^a$ идут со знаком $-$ с нечетным $+$ это связано с "погружением" для рекуррентного построения $P(n)$ по (2). тогда если перенести выражения с право налево получим обратное утверждение с четным количеством со знаком $+$ с нечетным $-$, но с другой стороны по утверждению которое нужно доказать места каждого из них

определяется как соответственно $P(16)+(-1)^{a(16-(16-2^4))} \cdot P(0)+(-1)^{a(16-(16-2^3))} \cdot P(16-2^3) + (-1)^{a(16-(16-2^2))} \cdot P(16-2^2)+.....-1=0$ но в степенях и есть количество единиц в двоичном представлении и которые отвечают за $+$ и $-$ этих слагаемых

Тогда для $P(14)=P(6)+P(10)-P(2)+P(12)-(P(4)+P(8)-P(0))+1$ инверсировав получаем

$P(15)=P(7)+P(11)-P(3)+P(13)-(P(5)+P(9)-P(1))+1$ аналогично для них места относительно $n=16$ по утверждению определяются как

$P(15)=(-1)^{16-(16-2^3)+1} \cdot P(7)+(-1)^{16-(16-2^2)+1} \cdot P(11)+(-1)^{16-(16-2^2-2^3)+1} \cdot P(3)+...+1$ но тогда если оставить выражения справа по аналогии (так как в степени добавляются единицы) и $P(15)$ перенести вправо получим верное утверждение и эти рассуждения обобщаются для любых четных $P(2k)$ значит утверждение в условии для четных $P(2k)$ есть $P(2k)=S_{1}, \ P(2k-2)=S_{2}$ сумма $P(2k)-S_{1}+S_{2}-P(2k-2)=0$

5) Для нечетных аналогично с той лишь разницей что берем один и тот же ряд $P(2k)$ и инверсируем $P(2k)=P(2k+1)$ и $P(2k+1)=S_{1}, P(2k)=S_{2}$ так как по разному представляются, откуда $P(2k+1)-S_{1}+S_{2}-P(2k)=0$ получаем утверждение в задаче при этом рассуждению аналогичны что и с четным.