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$
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
    $\begingroup$ $2^n/3\,\,\,\,\,\,\,$ $\endgroup$ – Empy2 Apr 18 '16 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$

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.