# 2017 APMO Problem 3

Let $$A(n)$$ denote the number of sequences $$a_1\ge a_2\ge\cdots{}\ge a_k$$ of positive integers for which $$a_1+\cdots+a_k = n$$ and each $$a_i+1$$ is a power of two. Let $$B(n)$$ denote the number of sequences $$b_1\ge b_2\ge \cdots{}\ge b_m$$ of positive integers for which $$b_1+\cdots+b_m =n$$ and  $$b_j\ge 2b_{j+1}$$ for $$1\leq j\leq m-1$$. Prove that $$A(n) = B(n)$$ for every positive integer $$n$$.

================================

We'll illustrate with an example the one-to-one correspondence.

 128 64 32 16 8 4 2 1 128 64 32 16 8 4 2 1 32 16 8 4 2 1 32 16 8 4 2 1 32 16 8 4 2 1 4 2 1 2 1 2 1 2 1 2 1

and

 128 64 32 16 8 4 2 1 128 64 32 16 8 4 2 1 32 16 8 4 2 1 32 16 8 4 2 1 32 16 8 4 2 1 4 2 1 2 1 2 1 2 1 2 1