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

---

post by Shen-Fu Tsai