Vrftsjtryk

I have the following question with me:

"There are 1990 boxes containing 1,2,3,....,1990 chips respectively, on a table. You may choose any subset of boxes and subtract the same number of chips from each box. What is the minimum number of moves you need to empty all boxes?"

How do I proceed with the question?

Since 1990 is a rather arbitrary number, let’s generalize the problem for a little bit.

"There are $m$ boxes containing 1, 2, 3, ...., $m$ chips respectively, on a table. You may choose any subset of boxes and subtract the same number of chips from each box. What is the minimum number of moves you need to empty all boxes?"

A quick observation yields that:

(1) If $p<q$, and the problem of $q$ boxes can be cleared within $n$ moves, then the problem of $p$ box can also be cleared within $n$ moves.

(2) If $p<q$, and the problem of $p$ boxes cannot be cleared within $n$ moves, then the problem of $q$ box cannot be cleared within $n$ moves.

(3) The number of boxes that contains the same amount of chips do not affect the result.

Justification of (1): We can deal with the $p$ boxes exactly the same way as we deal with the $q$ boxes, except for the moves that is intended for the boxes including more than $p$ chips are ignored. (3) follows from that whatever moves we made for the scenario without the copies, we can extend the original subsets so as to treat the duplicates as well.

Justification of (2): Proof by contradiction. If $q$ boxes problem can be cleared in $n$ moves, then from (1) we know that there is also a solution for $p$ boxes, since $p<q$, which is not possible.

First let’s prove that if $m=2^n-1$, then $n$ moves is sufficient. Firstly, subtract $2^{n-1}$ chips from the boxes that has at least $2^{n-1}$ chips, then from (3) we learn that this is equal to a $2^{n-1} - 1$ boxes problem, because the boxes now contain 1, 2, ..., $2^{n-1}-1$, 0, 1, 2, $2^{n-1}-1$ chips. Besides, $2^1-1=1$ box problem can be solved with $1$ move. By induction we completed the proof.

Then we will show that if $m=2^n$, then $n$ moves is not enough. I would prefer to use sets to interpret this problem, since (3) tells us that duplicates have no effect on the result. Rephrase the problem in this way:
$defcard{mathrm{card}}$

$S_0subsetmathbb N$ is a set of positive integers from 0 to $m$. You may choose any partition $S_0=P_1cup Q_1$, and a non-negative number $t_1leqmin P_1$. Define $S_1={x-t_1| xin P_1}cup Q_1$. $S_2, S_3, ldots$ are also defined in this way. Find ${P_i}$ and ${t_i}$ to minimize $n$, where $S_n= {0}$.

We want to prove that if $card S_k=s$, then $card S_{k+1}geq s/2$. Actually, if $card S_{k+1}<s/2$, then $card P_{k+1}leq card S_{k+1}<s/2$ and $card Q_{k+1}leq card S_{k+1}<s/2$. But $P_{k+1}$ and $Q_{k+1}$ are actually partition of $S_k$, the sum of cardinals should be $s$. This leads to a contradiction.

When $m=2^n$, $card S_0 = 2^n+1$. After one move, we have $card S_1 leq 2^{n-1} + 1/2$. But $card S_1$ is an integer, so $card S_1 leq 2^{n-1} +1$. Using induction, we know that $card S_n geq 2 >1$, so it cannot be ${0}$.

In this case, $1024leq1990leq2047$. From (1) and (2) we know that 11 is the minimal amount of moves required.

As SmileyCraft said in the comments, it can be done in $11$ moves.

The procedure is, at every step, to remove half the current chip maximum from all boxes containing more than this maximum. I.e. if the current chip maximum is $n_i$, the number of chips to remove is $n_{i+1} = lceil frac{n_{i}}{2} rceil$.

With $n_0=1990$, the number of chips to remove in step $i=1$ is $n_1 = lceil frac{n_0}{2} rceil = 995$. This leaves $2$ sets of boxes with $1$ to $995$ chips. With $n_1=995$, the number of chips to remove in step $i=2$ is $n_2 = lceil frac{n_1}{2} rceil = 498$. This leaves $4$ sets of boxes with $1$ to $497$ chips. With $n_2=497$, the number of chips to remove in step $i=3$ is $n_3 = lceil frac{n_2}{2} rceil = 249$. This leaves $8$ sets of boxes with $1$ to $248$ chips. And so on.

A simpler strategy is to remove the largest power of $2$ that is in any box from all the boxes you can. Now there is an easy inductive proof that you can handle boxes up to $2^n-1$ in $n$ moves because each move clears the high order bit.

To prove this is a minimal number of moves, show that the set up to $2^n-1$ must require $n$ moves because any smaller set of removals cannot clear it. Then any first move that gets all the boxes below $2^n-1$ is acceptable.

The answers so far don't address your question, which is to show the minimum number of moves required to empty the boxes. I will give you a hint:

Suppose the chips are arranged in the boxes in such a way that all the boxes can be emptied in one move. What can you say about the numbers of chips in the boxes?

Now suppose the chips in the boxes are such that the boxes can be emptied in two moves. What must be true about the distribution of the chips?