Problem 1495

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.