1
$\begingroup$

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

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ $2^n/3\,\,\,\,\,\,\,$ $\endgroup$
    – Empy2
    Commented Apr 18, 2016 at 7:22
0
$\begingroup$

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 ...

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .