Blackboard cleaning

Question

The blackboard contains 30 integer numbers from 1..2000. Each minute you are allowed to elect some positive integer number x and subtract x from some (chosen by you) of the numbers on the blackboard with the condition that the resulting numbers remain non-negative. If a number becomes 0 then it is erased from the blackboard. The game ends when all numbers are wiped out.

What is the smallest number of minutes so that you can always win the game with arbitrary 30 integer numbers from 1..2000 on the blackboard?

Answer 1

Dr Xorile's answer of

11 steps

is optimal. Suppose that the numbers 1, 2, 4, 8, ... 512, and 1024 are all on the board. In order to eliminate the number $2^i$, there must be some step where you decrease $2^i$, but none of the numbers $2^0,2^1,\dots, 2^{i-1}$. If this were not true, then the amount you decreased $2^i$ would be at most the amount you decreased the numbers $2^0,2^1,\dots,2^{i-1}$, which is at most $2^0+2^1+\dots+2^{i-1}=2^i-1$, so that $2^i$ wouldn't have been eliminated.

Thus, in this case, there must be eleven distinct steps, since for each $i=0,1,\dots,10$, there must be a step where the smallest number touched was $2^i$.

Answer 2

It can be done in:

11 numbers (ie 10 minutes - assuming regular spacing and timer starting from the first number chosen. If it's just some time during "each minute", then it's $10\pm1$ minutes)

"But how?" you ask. Well, I'm glad you asked:

Convert the numbers to binary, and subtract the bits. Or, to put it another way, subtract 1024 from all the numbers that can afford it. Then subtract 512 from all the numbers that can afford it. Then 256. Then 128. Etc. Down to 1.

This is the best answer. See @Mike Earnest’s proof below!