# Blackboard cleaning

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?

• Are we told that it's not a valid choice because it will create a negative number? Or is that just a lose condition? Or we won't do that because we can see the numbers? – Raystafarian Nov 13 '15 at 18:39
• When you subtract and get 0, you wipe the number from the blackboard. Presumably, if you subtract and DO NOT get 0, you substitute the old number on the board with the difference. But that's not said in the question so one could assume, that if you do not get 0 the number on the blackboard stays as it is. Perhaps the question can be improved to clarify that. – Andrew Savinykh Nov 15 '15 at 9:16

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$.

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)