Vtgyjfy

Alex and Bob plays a game

A box contains numbers from 1 to 1024

Alex goes first

Alex removes 512 numbers

Bob removes 256 numbers

Alex removes 128 numbers

Bob removes 64 numbers

Alex removes 32 numbers

Bob removes 16 numbers

Alex removes 8 numbers

Bob removes 4 numbers

Alex removes 2 numbers

this goes on until 2 numbers remain in the box x,y

Alex plays to maximize the value of |x-y| in the end

Bob plays to minimize this value

Both play optimally what are the 2 numbers that remain in the box in the end

My work:

I made a program for this such the Alex's task is to remove pairs with least value of |i-j|

And Bob's task is to remove pairs with max value of |i-j|

Answer I got was x=171,Y=854 which isn't correct please help me with this

Bob: I’d suggest minimizing the range. Essentially, remove all the highest/lowest numbers, whichever reduces the range the most. It isn’t perfect, but it’s logical, and doesn’t make as many mistakes as your previous method. Of course, I’m sure there are more optimal ways, and maybe strategies for Alex to exploit this protocol, but it’s a decent heuristic I’d reckon.

For Alex, I’d suggest essentially getting rid of all the numbers $n equiv c(mod 2^k)$, which doubles the minimum difference with each move. I believe there should always be some value $c$ for which you get all numbers equivalent to c in mod form, but I’ll leave the specifics for you to work out.

Explanation of Alex Method:

After his k-th turn, the remaining numbers are one of two values a, b mod $2^{k+1}$, which we will say belong to sets $A$ and $B$. In his (k+1)-th turn, he can remove half of the remaining numbers. Since either $A$ or $B$ has less then half the numbers, he can remove every number in one of these sets, after which, again, all the remaining numbers will either be one of two values a, b mod $2^{(k+1)+1}$.

Let's play the game with $16$ numbers. Whatever $4$ number are left at the end, Alex will remove the two middle ones, right? So when there are eight numbers left, say $x_1<x_2<cdots<x_8,$ Bob will choose to leave $x_k, x_{k+1}, x_{k+2}, x_{k+3}$ so as to make $x_{k+3}-x_k$ smallest. (Obviously, Bob will want to leave $4$ consecutive numbers.)

What can Alex do at his first turn to frustrate Bob? It does no good to try to leave large intervals, because they will naturally be compensated by small ones, and Bob will take care to leave only the small ones. The beast thing Alex can do is to make all the intervals equal.

So at his first turn, Alex chooses all the odd numbers or all the even ones. Say he leaves $2,4,6,cdots16.$ The best Bob can do is to remove the biggest $4$ numbers leaving $2,4,6,8.$ Then Alex removes $4$ and $6$ leaving a difference of $6$. There are other plays for Bob that result in $6,$ but none that results in a smaller difference.

Now generalize this.