Азия-тынық мұхит математикалық олимпиадасы, 2017 жыл

$A(n)$ саны келесі шарттарды қанағаттандыратын натурал сандардан құралған тізбектердің санына тең болсын: $a_1\geq a_2\geq \ldots \geq a_k$, $a_1+\ldots+a_k=n$ және барлық $i=1,2,\ldots,k$ үшін $a_i+1$ саны екінің дәрежесіне тең. Ал $B(n)$ саны келесі шарттарды қанағаттандыратын натурал сандардан құралған тізбектердің санына тең болсын: $b_1\geq b_2\geq \ldots \geq b_m$, $b_1+\ldots+b_m=n$ және барлық $j=1,2,\ldots,m-1$ үшін $b_j\geq 2b_{j+1}$ теңсіздігі орындалады.
Кез келген натурал $n$ үшін $A(n)=B(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).$