Problema 3 APMO 2017

[tuvie]

Sea [math]A(n) la cantidad de sucesiones [math]a_1\geq{}a_2\geq{}...\geq{}a_k de enteros positivos tales que [math]a_1+a_2+...+a_k=n y cada [math]a_i+1 es una potencia de dos [math](i=1,2,...,k). Sea [math]B(n) la cantidad de sucesiones [math]b_1\geq{}b_2\geq{}...\geq{}b_m de enteros positivos tales que [math]b_1+b_2+...+b_m=n y se cumple la desigualdad [math]b_j\geq{2b_{j+1}} para todo [math]j=1,2,...,m-1.
Demostrar que [math]A(n)=B(n).

[enigma1234]

Spoiler: mostrar

Considere el conjunto:

[math]S{=} \left \{ (2^k-1) \, | \, k \geqslant 1 \right \}.

Veamos que la cantidad de maneras de escribir [math]n como suma de elementos(no necesariamente distintos) de [math]S es igual a [math]A(n)=B(n).
Para [math]A(n) esto es claro dado que cada [math]a_i esta en [math]S,para [math]B(n) consideremos la siguiente biyeccion: [math](b_1, \dots, b_m) \mapsto (x_1, \dots, x_m) tal que [math]x_m=b_m y para todo [math]1 \leqslant j \leqslant m-1 tenemos que [math]x_j=b_j-2b_{j+1}. De esto es claro que:

[math]n=b_1+\dots+b_m=\sum (2^k-1)x_k ...(1)

Donde podemos elegir cualquier sucesion [math](x_1, \dots, x_m) que cumplan (1) y entonces la cantidad de sucesiones [math](x_1, \dots, x_m) que cumplen (1) es la cantidad de formas de escribir [math]n como suma de elementos(no necesariamente distintos) de[math]S que es igual a [math]B(n) por la biyeccion.Por lo tanto tenemos que [math]A(n)=B(n) para todo [math]n \geqslant 1