Money Game with $1025$ cards

Question

Alice is playing a game with Bob. They have $1025$ cards, with the numbers $0,1,2,\cdots , 1024$ written on them. Each card contains exactly one number and each number is written on exactly one card. Starting with Alice, they move alternately, taking $512, 256, 128, 64, 32, 16, 8, 4, 2, 1$ cards in that order. In other words, Alice first takes any $512$ cards, then Bob takes any $256$ cards which are not already taken, then Alice $128$ cards not taken, and so on. Finally two cards, say with numbers $a$ and $b$ are left; then Bob pays Alice $|a-b|$ dollars.

Alice wants to obtain as much money as possible, while Bob wants to lose the least possible amount of money.

Assuming both of them play perfectly, what is the maximum amount of money Alice can ensure for herself?

Author: Orlando Dohring

Answer 1

I think the answer is

$\$32$

Strategy for Alice

At each round skip the first and take alternating cards that are remaining so the $2$nd, $4$th, $6$th $8$th, etc.

Reasoning

On the first round, Alice takes all the odd numbered cards, this guarantees a gap of $2$. No matter what Bob does, if Alice then takes every second card in the next round she guarantees a gap of at least $4$ between consecutive remaining cards and so on. She has five rounds to remove cards giving her the chance to make the minimum gap $2^5 = 32$ and winning $\$32$.

Proof that this is a maximum

Let's say Bob adopts the following strategy:

On the first move, he divides the card into two sets: those which are numbered $ < 512$ and those which are $\ge 512$. In one of these sets, there will be at most $256$ cards remaining so he removes all the cards from this set, thus guaranteeing a maximum gap of $512$.

On his $n$th move, he will be presented with a set of cards with numbers lying on a range of length $2^{11-n}+1$. He can split the range into two and remove all the cards in the half which contains fewer cards.

Given that he has five moves, he can guarantee that the maximum gap at the end is $2^{10-5} = 32$. Hence, this is also the maximum number of dollars that Alice can win.