Optimal Strategy for Card Split and Discard game

379 Views Asked by At

In a game of 2 players, there are 2 piles of cards.

In every turn, a player has to discard one pile and divide the other into two equal parts (as close as possible). The game ends when a player is not able to make a move. (That is discard and split)

What can be the optimal strategy for this game if the starting pile has m and n cards.

Eg: (4,5)

p1-> discard 4, split 5 (2,3)

p2->discard 3, split 2 (1,1)

p1 cannot move, p2 wins

2

There are 2 best solutions below

1
On BEST ANSWER

Call $1$ a bad number. We will recursively construct further ranges of bad numbers: if $[a,b]$ is a (maximally contiguous) range of bad numbers, then so is $[2b+1,4b+1]$. Thus the bad numbers, organized in ranges, are: $$1,[3,5],[11,21],[43,85],\ldots$$

If both piles are bad, then the position is a losing one; for otherwise the player can split one of the piles into two bad piles.


Addendum: As @Michael alludes to in his comment, these ranges are related to the powers of $2$; they can be written like so: $$\left[\frac{2^1+1}3,\frac{2^2-1}3\right],\left[\frac{2^3+1}3,\frac{2^4-1}3\right],\left[\frac{2^5+1}3,\frac{2^6-1}3\right],\ldots$$ Therefore a number $n$ is bad precisely when $\lfloor \log_23n \rfloor$ is odd.

0
On

If one pile has two cards, it is a win for the player about to play.
If both piles, halved, leave a two-card pile, it is a loss for the one about to play. So if both piles are 3,4 or 5, it is a loss.
It is a win if there is a pile that ...