The player with the most valuable coins wins

Question

There are $25$ coins with values $1,2,\dots,25$. Two persons, $A$ and $B$, play the following game with these coins. Person $A$ chooses a coin and person $B$ decides whether to keep the coin for himself or to hand over the coin to him. Each player with the most coins must choose the next coin and the other player must decide whether to keep the coin or give it to another player. If the number of coins is equal, the previous state is repeated. The game continues in the same way until all the coins are selected. At the end, the player with the most valuable coins wins the game. Which player has a winning strategy?

---

I think $B$ has the winning strategy, but I can't prove it. I will be grateful if someone helps me to solve this problem.

Answer 1

I am sure you are right in thinking that B has a winning strategy. I think the following strategy works but it requires a full proof.

B's Strategy

Accept a coin if and only if A offers a coin in the range $20-25$ or already has $12$ coins.

Always offer the highest available coin in the range $19-1$.

Two examples (but not a full proof)

Suppose A fails to offer a coin in the range $20-25$ for $12$ turns. Then B accepts all further coins and the best possible score for A is then $8+9+ ... +19=162$. B then has $163$ and wins.

Suppose A offers $20$ and it is accepted and then refuses all coins. B ends up with at least the coins 9-20, a score of $174$, and wins.

Answer 2

Let $X(\mathcal{C}, k)$ be the largest difference in scores achievable by the player with the next move when he has $k \ge 0$ more coins than the other player and the set of remaining coins is $\mathcal{C}$. He will choose some $c\in \mathcal{C}$. The other player may decide to let him keep that coin, giving him a score of $c + X(\mathcal{C}\setminus c, k+1)$. Or the other player may take the coin herself, leading to a score for the first player of $-c + X(\mathcal{C}\setminus c, k-1)$ (for $k\ge 1$). The $k=0$ case is special; in that case, if the second player takes the coin, she then has strictly more coins and moves into the choosing role. She will score $c + X(\mathcal{C}\setminus c, 1)$ with optimal play, so the first player's score is $-c-X(\mathcal{C}\setminus c, 1)$. All told, we have that $$ X(\mathcal{C}, k)=\max_{c\in \mathcal{C}}\min\{c+X(\mathcal{C}\setminus c, k+1),-c+X(\mathcal{C}\setminus c, k-1)\}, $$ with boundary conditions $X(\emptyset, k)\equiv 0$ and $X(\mathcal{C}, -1)\equiv -X(\mathcal{C},1)$.

Playing with this analysis for smaller sets of coins (say, $\{1,2,\ldots,N\}$) suggests the following:

• When $N\equiv 0,3$ (mod $4$), the first player can force a draw against optimal play.
• When $N\equiv 1,2$ (mod $4$), the second player can win by a single unit of value.

If this pattern (checked through $N=18$) holds, then $B$ has the winning strategy for $N=25$.