XV математическая олимпиада «Шелковый путь», 2016 год
Комментарий/решение:
Для $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$ получаем утверждение в задаче при этом рассуждению аналогичны что и с четным.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.