Азиатско-Тихоокеанская математическая олимпиада, 2017 год

Пусть $A(n)$ равно количеству последовательностей натуральных чисел $a_1\geq a_2\geq \ldots \geq a_k$, для которых $a_1+\ldots+a_k=n$ и $a_i+1$ равно степени двойки для каждого $i=1,2,\ldots,k$. Пусть $B(n)$ равно количеству последовательностей натуральных чисел $b_1\geq b_2\geq \ldots \geq b_m$, для которых $b_1+\ldots+b_m=n$ и неравенство $b_j\geq 2b_{j+1}$ выполнено для каждого $j=1,2,\ldots,m-1$. Докажите, что $A(n)=B(n)$ для всех натуральных $n$.

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

Пусть $\mathrm{S}=\{2^m-1\mid \forall m\in\mathbb N\}$

Тогда $A(n)$ равно количеству способов представить число $n$ в виде суммы элементов из $\mathrm S.$ (элементы из $\mathrm S$ можно использовать насколько раз.)

Построим биекцию $(b_1,\ldots,b_m)\longleftrightarrow (x_1,\ldots,x_m):$

$1) b_m=x_m$

$2) b_i-2b_{i+1}=x_i,\forall i=1,\ldots,m-1;$

Из условия $x_i\in\mathbb{Z_{\ge 0}}$ и $\{ x_1,\ldots,x_m\}\ne\{0,\ldots,0 \}.$ Тогда $$\large{n=\sum\limits_{i=1}^{m} b_i=\sum\limits_{i=1}^{m}}(2^i-1)\cdot x_i$$

Пусть $X(n)$ равно количеству последовательностей $(x_1,\ldots, x_m)$ таких, что $$\large{n=\sum\limits_{i=1}^{m}(2^i-1)\cdot x_i,\quad x_i\ge 0}$$

Из ранее показаной биекции следует, что $X(n)=B(n).$ Так же очевидно, что $X(n)$ равно количеству способов представить число $n$ в виде суммы элементов из $\mathrm S.$ Откуда $A(n)=X(n).$

Значит $A(n)=B(n).$