Selected Problems from Open Contests

Divide the set $A$ into subsets such that the subset $A_k$ consists of only those numbers which have exactly $k$ ones in their binary representation. Then $A_0=\{0\},A_1=\{1,2,4,\dots ,2^{n-1}\},\dots ,A_n=\{2^n-1\}$. Let us show that both conditions are met.

The first condition is met because the numbers with $k$ ones are in one-to-one correspondence with the numbers with $n-k$ ones: given a number, simply replace all ones in its binary representation by zeros and vice versa.

To show that the second condition is met, choose an arbitrary number $z$ from the set $A_{s+t}$. Its binary representation contains exactly $s+t$ ones. Construct a binary number $x$ by choosing $s$ ones from the binary representation of $z$ and filling all other binary places by zeros, analogously construct a second number $y$ based on remaining ones in $z$. Then $x\in A_s,y\in A_t$ and $x+y=z$.

---

Alternative solution.

Let us prove the statement by induction. If $n=1$, then $A=\{0,1\}$, and taking $A_0=\{0\}$ and $A_1=\{1\}$ we get a partition that satisfies both of the requirements.

Assume now that we have a partition $C_0,C_1,\dots ,C_n$ for the set $C=\{0,1,\dots ,2^n-1\}$. Construct a partition of the set $A=\{0,1,\dots ,2^{n+1}-1\}$ based on that. First, generate the sets $B_0,B_1,\dots ,B_n$ as follows: the elements of the subset $B_i$ are derived from the elements of the subset $C_i$ by adding $2^n$ to them. The subsets $B_0,B_1,\dots ,B_n$ form a partition of the set $A\setminus C=\{2^n,2^n+1,\dots ,2^{n+1}-1\}$ and from the construction for all $i=0,1,\dots ,n$ the corresponding subsets $B_i$ and $C_i$ have the same number of elements.

Now, let $A_i=C_i\cup B_{i-1}$ for all $i=1,2,\dots ,n$ and in addition to that, $A_0=C_0$ and $A_{n+1}=B_n$. Then, $|A_0|=|A_{n+1}|=1$, and if $k+l=n+1$, then also $k,l\ne 0$, $|A_k|=|B_{k-1}|+|C_k|=|C_{k-1}|+|C_k|$ and $|A_l|=|B_{l-1}|+|C_l|=|C_{l-1}|+|C_l|$. As $(k-1)+l=k+(l-1)=n$, we see that $|C_{k-1}|=|C_l|$ and $|C_k|=|C_{l-1}|$; thus $|A_k|=|A_l|$.

To verify that the second condition is met, let $z$ be an arbitrary element of $A_{s+t}$. If $t=0$, then $A_s=A_{s+t}$ and $A_t=A_0=\{0\}$, so we can take $x=z$ and $y=0$. Now assume $t\ge 1$. If $z<2^n$, then $z$ is an element of $C_{s+t}$ and thus there exist elements $x$ and $y$ in the sets $C_s\subset A_s$ and $C_t\subset A_t$, respectively, such that $x+y=z$. If $z\ge 2^n$, then $z$ is an element of $B_{s+t-1}$, i.e. $z-2^n$ is an element of the set $C_{s+t-1}$ and thus the sets $C_s$ and $C_{t-1}$ contain elements $x$ and $y$, respectively, such that $x+y=z-2^n$. But now $x+(y+2^n)=z$, where $x$ and $y+2^n$ are elements of the sets $C_s\subset A_s$ and $B_{t-1}\subset A_t$, respectively. So the statement holds for all positive $n$.