Two math. wizards play in the following manner:
From a row of integers 0,1,2,…1023,1024 A erases 512 numbers
of his choice, - following this B erases 256 numbers of B’s choice.
Step 3: A erases 128 numbers, etc…
So at Step 10 player B chooses one of the 3 remaining numbers and erases it to define the amount of (dollars, pounds, euros, marbles) to be paid by A i.e. the difference between the two remaining numbers.
Clearly, A chooses a strategy to minimize this amount while
his opponent wants to maximize the outcome.
Assuming both follow the best strategy (Which?),
what will be the outcome of the game?
2 is the best answer possible for A.
If we show that A can use a strategy to force an outcome of 2, then 2 will also be the only answer.
Basically the idea is the show that A can always keep the remaining numbers clusterd in one segment after his turn.
if this is true then B will be left with a segment of [a,a+1,a+2]. Obviously B will then choose to erase a+1 and thus the answer will be 2.
So to sum up so far: if A is able to cluster the numbers, this is also the best strategy for him and therefore also the answer.
So:
When it is A's turn, he can erase 2^i numbers. currently on the board (after B deleted 2^(i+1) numbers) are 2^i+1 numbers.
If this is the 3rd turn, A is about to delete 2^7 numbers and there are now 2^8+1 numbers on the board.
Let's look at the previous turn (B's turn), remebering that by induction, there is now only one segment on the board - in any case, the smallest segment he could have left is 2^i - by deleting the numbers in the middle.
Now, in his turn, A can delete this segment (as he can delete 2^i - exactly equal to the smallest possible segment) and we are left with only one segment - As requested.
|
|
Posted by Omri
on 2015-01-26 08:03:27 |
Maybe?
