Alice and Bob play a game. They start with a sequence of consecutive 4097 numbers, 0,... 4096. At the first step Alice removes any 2048 numbers. At the second step Bob removes any 1024 numbers from the remaining sequence of numbers. At the third step Alice removes 512 numbers. At the fourth step Bob removes 256 numbers and so on. At the 11th step Alice removes one number from the remaining three numbers. Let a$<$b be the last two numbers. Bob pays the difference of b − a to Alice. Design a strategy for Alice that guarantees the biggest worst case gain, and a strategy for Bob that guarantees lowest worst case loss regardless of the others strategy.
One approach I thought of was that Alice would always remove every other element, so in the first move she would remove elements 1,3,5,...,4095. That way she can maximise her chances of having a large gap between $b$ and $a$ at the end of the game. Whereas for bob, his optimal strategy would always be to remove as much of the largest or smallest elements of the list that he can.
I'm wondering if anyone can provide a more rigorous approach to these kinds of problems?
I think your approach for Alice works, that she remove $1,3,\dotsc,4095$, then resulting list L'=$0,2,\dotsc,4096$, so every two consecutive numbers in L' differ by $2$. Then afterwards, to simulate a worst case, Alice and Bob play some really unwise moves, so that the ending two numbers differ by $2$, so Alice gains $2$.
Suppose she does not remove some number $z$ from $1,3,\dotsc,4095$, then there are some three consecutive integers $x,z,y$ in the list L''=L',z, i.e. $z-x=1$ and $y-z=1$. So the worst case gain is now $1$.
Alice now has an extra removal, how can Alice fix this? She can't, if she removes $x$, but then $y-z=1$ so the worst case gain is still $1$; likewise if she removes $y$. If she removes some number not $x,y$ then the worst case gain is still $1$. Of course again, they play really unwise moves afterwards and Alice gains $1$. So the best worst case gain is $2$, achieved by your approach.
And I think for Bob the strategy should be a slight variant of what you suggested. At any point the best gain for Alice (worst loss for Bob) is $b-a$ for the largest number $b$ and smallest number $a$ in current list. Let $b'$ be the second largest number and $a'$ be the second smallest number. Then have Bob remove $b$ if $b'-a<b-a'$, and remove $a$ if $b-a'<b'-a$. And Bob should be indifferent between removing $b$ and removing $a$ if $b'-a=b-a'$.
I hope this helps.