Number of moves required to empty all the boxes as per the given rules

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?

• I have a question on the rules. Suppose I pick $4$ as the first number. What action do I take on the first $3$ boxes? – saulspatz Dec 15 '18 at 14:45
• Interesting question. Let's generalize this to $n$ boxes. Do I understand correctly that we can do $n=3$ in $2$ moves? $[1,2,3];[0,2,2];[0,0,0]$ – SmileyCraft Dec 15 '18 at 14:46
• I believe you can do $n=1990$ in $11$ moves. Hint: look at the binary representations of the numbers. I am not sure whether this is optimal though. – SmileyCraft Dec 15 '18 at 14:47
• Ok I am sure that this is optimal. If you want me to explain, just ask and I'll write a complete answer. – SmileyCraft Dec 15 '18 at 14:53
• @saulspatz it is not possible to take 4 chips from a box with fewer than 4 chips. – MJD Dec 15 '18 at 16:26

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, 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, 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, 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: $$\def\card{\mathrm{card}}$$

$$S_0\subset\mathbb N$$ is a set of positive integers from 0 to $$m$$. You may choose any partition $$S_0=P_1\cup Q_1$$, and a non-negative number $$t_1\leq\min P_1$$. Define $$S_1=\{x-t_1| x\in 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}, then $$\card P_{k+1}\leq \card S_{k+1} and $$\card Q_{k+1}\leq \card S_{k+1}. 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, $$1024\leq1990\leq2047$$. From (1) and (2) we know that 11 is the minimal amount of moves required.

• Are your observations 1 and 2 correct? I feel you interchanged p and q there..... – saisanjeev Dec 16 '18 at 7:07
• @saisanjeev I rearranged the answer for a little bit, hopefully this is helpful for understanding. – fantasie Dec 16 '18 at 7:33
• Can you please elaborate the part after you have rephrased the required problem into that of a set theory problem. I have some trouble with the subscripts 'k+1' and 'k' coz I am unable to relate them directly as you have – saisanjeev Dec 16 '18 at 7:42
• @saisanjeev Ok. $\{S_k\}$ is a sequence of sets of non-negative integers. I added zero in them just for convenience. $S_0$ is what you have originally got, i.e. boxes 1, ..., m chips, and an additional empty one. After each move, we generate another set from $\{S_k\}$. So after move 1 we got $S_1$, and after move 2 we got $S_2$, etc. The numbers in $a_1, \ldots, a_u$ in $S_k$ indicates that after $k$ moves, you have some boxes with $a_1$ chips, some boxes with $a_2$ chips, ..., ... with $a_p$ chips. You choose some boxes to subtract t chips, whose amount of chips is $P$. Is this clear? – fantasie Dec 16 '18 at 7:59
• $P_k$ and $Q_k$ may not be disjoint, but this does not influence the result. – fantasie Dec 16 '18 at 8:03

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.

• Can you prove that it cannot be done with less than 11 moves? – fantasie Dec 16 '18 at 1:54
• No, I cannot. Can you? – Jens Dec 16 '18 at 1:56
• I am thinking of it, but I don’t have any idea by now. – fantasie Dec 16 '18 at 1:58
• See if this may work out: To clear 1...$2^n$, we know that it requires n moves. However, if there is 1...$2^n+1$ instead, whatever first move are made, there are at least $2^{n-1}+1$ boxes that contains different amount of chips (plus, they are not empty). Use induction and we may conclude that after n moves, at least 1 box is not empty. For $m>2^{n}+1$, we know that the first $2^n+1$ boxes that cannot be dealt with n moves. This completes the proof. – fantasie Dec 16 '18 at 2:08
• @fantasie Hmmm. Not sure. If you can do the proof in detail, you should add it as an answer. – Jens Dec 16 '18 at 2:41

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.

• Not exactly, even if we know 2047 boxes can be dealt with 11 moves and 1023 boxes requires at least 10 moves, there is no information about numbers in the middle. – fantasie Dec 16 '18 at 4:29

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?