Alice and Bob play the following game. In the beginning there is list of numbers

$$\{0, 1, 2,\dotsc, 1024\}.$$

Alice starts, and removes 512 numbers of her choice. Bob continues and removes 256 numbers of his choice. Alice continues and removes 128 numbers of her choice, and so on, until only 2 numbers remain. Then Alice pays Bob the difference between the two numbers.

What are the optimal strategies for Alice and for Bob, respectively?

  • 1
    $\begingroup$ When finding strategies for games like this, it's often a good idea to either play a smaller game (start with numbers from 0 through 4 or 8), or work backwards (who had last play, what would they want, and how can their opponent stop that when they do their second to last play). Have you tried that? $\endgroup$ – Arthur Mar 10 at 12:02
  • $\begingroup$ Pretty intuitive to think that Alice should remove numbers from both ends($0, 1024, 1, 1023, \dots$) and Bob should remove numbers from the middle (eg. $512, 513, 511, 514, \dots$) $\endgroup$ – ab123 Mar 10 at 12:03
  • 2
    $\begingroup$ @ab123, to follow your intuitive strategy, Alice may as well remove her half from just one end. But Bob, I think, will do better to remove every other number instead of a consecutive stretch from the middle. $\endgroup$ – Barry Cipra Mar 10 at 12:34
  • 3
    $\begingroup$ @RodrigodeAzevedo $1025 - 512 - 256 - 128 - 64 - 32 -16 - 8 - 4 - 2 - 1 = 2$ $\endgroup$ – ab123 Mar 10 at 12:43

Given a set $X$, let $A(X)$ denote the largest distance between any two points in $X$ and $B(X)$ denote the smallest distance between any two different points in $X$. For a two-element set, $A(X)=B(X)$. We start with $A(X)=1024$ and $B(X)=1$. I will show Alice can halve $A(X)$ at each of her turns, and Bob can double $B(X)$ at each of his turns. Since both players have 5 turns, this means that Alice can ensure that the result is at most 32 and Bob can ensure the result is at least 32.

Note that at each turn, the player to move is given a set with an odd number of elements.

Given $X=\{x_0,\dots,x_{n/2},\dots,x_n\}$ sorted ascending, we have $A(X)=x_n-x_0 = (x_n - x_{n/2}) + (x_{n/2} - x_0)=A(\{x_{n/2},\dots,x_n\})+A(\{x_0,\dots,x_{n/2}\})$. At least one of the two summands is $\leq A(X)/2$. Therefore, Alice removes all topmost or all bottommost elements on each of her turns, depending on the situation.

Given $X=\{x_0,x_1,..,x_{n}\}$, Bob removes $x_i$ such that $i$ is odd. It's easy to see that this guarantees that $B(X)$ is at least doubled.

A slight generalization: in your problem Alice and Bob have the same number of turns. In general, if we start with $\{0,1,\dots,2^n\}$ and remove almost-half of remaining elements at every turn, then the optimal payoff will be $2^k$ where $k$ is the number of turns controlled by Bob and $n-k$ the number of turns controlled by Alice; the players don't have to alternate.

  • $\begingroup$ both have 5 turns? i count bob only having 4 {256,64,16,4} while alice has 5 {512,128,32,8,2} $\endgroup$ – Nullman Mar 12 at 18:36
  • $\begingroup$ @Nullman Bob has one more turn where he removes 1 element. See ab123's comment on top of this page. Note the set has 1025 elements at the beginning. $\endgroup$ – sdcvvc Mar 14 at 21:38

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.