Problem 1086

We say that a sequence $a_{1} \geq a_{2} \geq \ldots \geq a_{k}$ of positive integers has type $A$ if $a_{i}+1$ is a power of two for $i=1,2, \ldots, k$. We say that a sequence $b_{1} \geq b_{2} \geq \ldots \geq b_{m}$ of positive integer has type $B$ if $b_{j} \geq 2 b_{j+1}$ for $j=1,2, \ldots, m-1$.

Recall that the binary representation of a positive integer expresses it as a sum of distinct powers of two in a unique way. Furthermore, we have the following formula for every positive integer $N$

$$2^{N}-1=2^{N-1}+2^{N-2}+\cdots+2^{1}+2^{0} .$$

Given a sequence $a_{1} \geq a_{2} \geq \ldots \geq a_{k}$ of type $A$, use the preceding formula to express each term as a sum of powers of two. Write these powers of two in left-aligned rows, in decreasing order of size. By construction, $a_{i}$ is the sum of the numbers in the $i$ th row. For example, we obtain the following array when we start with the type A sequence $15,15,7,3,3,3,1$.

| 8 | 4 | 2 | 1 |
| :--- | :--- | :--- | :--- |
| 8 | 4 | 2 | 1 |
| 4 | 2 | 1 | |
| 2 | 1 | | |
| 2 | 1 | | |
| 2 | 1 | | |
| 1 | | | |
| 27 | 13 | 5 | 2 |

Define the sequence $b_{1}, b_{2}, \ldots, b_{n}$ by setting $b_{j}$ to be the sum of the numbers in the $j$ th column of the array. For example, we obtain the sequence 27,13,5,2 from the array above. We now show that this new sequence has type B. This is clear from the fact that each column in the array contains at least as many entries as the column to the right of it and that each number larger than 1 in the array is twice the number to the right of it. Furthermore, it is clear that $a_{1}+a_{2}+\cdots+a_{k}=b_{1}+b_{2}+\cdots+b_{m}$, since both are equal to the sum of all the entries in the array.

We now show that we can do this operation backwards. Suppose that we are given a type B sequence $b_{1} \geq b_{2} \geq \ldots \geq b_{m}$. We construct an array inductively as follows:

- We fill $b_{m}$ left-aligned rows with the numbers $2^{m-1}, 2^{m-2}, \ldots, 2^{1}, 2^{0}$.
- Then we fill $b_{m-1}-2 b_{m}$ left aligned rows with the numbers $2^{m-2}, 2^{m-3}, \ldots, 2^{1}, 2^{0}$.
- Then we fill $b_{m-2}-2 b_{m-1}$ left aligned rows with the numbers $2^{m-3}, 2^{m-4}, \ldots, 2^{1}, 2^{0}$, and so on.
- In the last step we fill $b_{1}-2 b_{2}$ left-aligned rows with the number 1.

For example, if we start with the type B sequence $27,13,5,2$, we obtain once again the array above. We define the sequence $a_{1}, a_{2}, \ldots, a_{k}$ by setting $a_{i}$ to be the sum of the numbers in the $i$ th row of the array. By construction, this sequence has type A. Furthermore, it is clear that $a_{1}+\cdots+a_{k}=b_{1}+\cdots+b_{m}$, since once again both sums are equal to the sum of all the entries in the array.

We have defined an operation that starts with a sequence of type A, produces an array whose row sums are given by the sequence, and outputs a sequence of type B corresponding to the column sums. We have also defined an operation that starts with a sequence of type $\mathrm{B}$, produces an array whose column sums are given by the sequence, and outputs a sequence of type A corresponding to the row sums. The arrays produced in both cases comprise leftaligned rows of the form $2^{N-1}, 2^{N-2}, \ldots, 2^{1}, 2^{0}$, with non-increasing lengths. Let us refer to arrays obeying these properties as marvelous.

To show that these two operations are inverses of each other, it then suffices to prove that marvelous arrays are uniquely defined by either their row sums or their column sums. The former is obviously true and the latter arises from the observation that each step in the above inductive algorithm was forced in order to create a marvelous array with the prescribed column sums.

Thus, we have produced a bijection between the sequences of type A with sum $n$ and the sequences of type $\mathrm{B}$ with sum $n$. So we can conclude that $A(n)=B(n)$ for every positive integer $n$.

Remark The solution above provides a bijection between type A and type B sequences via an algorithm. There are alternative ways to provide such a bijection. For example, given the numbers $a_{1} \geq \ldots \geq a_{k}$ we may define the $b_{i}$ 's as

$$b_{j}=\sum_{i}\left\lfloor\frac{a_{i}+1}{2^{j}}\right\rfloor \text {. }$$

Conversely, given the numbers $b_{1} \geq \ldots \geq b_{m}$, one may define the $a_{i}$ 's by taking, as in the solution, $b_{m}$ numbers equal to $2^{m}-1, b_{m-1}-2 b_{m}$ numbers equal to $2^{m-1}-1, \ldots$, and $b_{1}-2 b_{2}$ numbers equal to $2^{1}-1$. One now needs to verify that these maps are mutually inverse.