# 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.

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

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 |

post by Shen-Fu Tsai