18
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Raystafarian Nov 13 '15 at 18:39
  • $\begingroup$ 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. $\endgroup$ – Andrew Savinykh Nov 15 '15 at 9:16
26
$\begingroup$

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

$\endgroup$
22
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.