Hellenic Mathematical Olympiad

We suppose that at the first step we select from all sets $k_1$ elements, at the second step we select from the remaining sets $k_2$ elements and similarly at the $n$-th step we select $k_n$ elements. After the depletion of the elements of all sets $A_1,A_2,\dots ,A_n$, then each $i=|A_i|$, $i=1,2,\dots ,160$, must be the sum of some of the numbers $k_1,k_2,\dots ,k_n$. We observe that the number of all possible sums with terms some of the numbers of the set $\{k_1,k_2,\dots ,k_n\}$ is $2^n$, because for the creation of these sums for each term there are only two possible cases, that is a term must be or not to be in the sum. Therefore we must have $2^n\ge 160$, and so $n\ge 8$ with minimal possible value of $n$ to be $8$.

Next we are going to prove that the value $n=8$ can be obtained because we can apply the procedure at $8$ steps.

At the first step we consider the sets $A_{81},\dots ,A_{160}$ and we subtract from each of them $80$ elements. Therefore the set $M_1$ will consist of $80\cdot 80=6400$ elements.

After subtracting the $80$ elements, we denote the remaining sets as $A_{81}^1,\dots ,A_{160}^1$. Now the sets $A_i$, that is $A_{80+i}^1$, $i=1,2,\dots ,80$ contain $i$ elements. At the second step we consider the sets $A_{41},\dots ,A_{80}$, $A_{121}^1,\dots ,A_{160}^1$ and we subtract from each of them $40$ elements. Therefore the set $M_2$ will consist of $80\cdot 40=3200$ elements.

We continue in this way to obtain the set $M_3$ with $80\cdot 20=1600$ elements, and the sets $M_4,M_5,M_6,M_7$ and $M_8$ with $1600$, $800$, $400$, $288$, $128$ and $64$ elements, respectively.