Maths strategy games

Question

Two stacks of cards are given initially. They may contain arbitrary numbers of cards; the numbers are known to the players. A player whose turn comes must take one card from one of the stacks or take one card from each of the stacks. The players choose what moves they want to make. Player A begins. The last player who can make a move has won the game.

How should the players behave? Is there a strategy by which one of the players can force a win, no matter what the opponent does? How does it depend on the initial numbers of cards? For given numbers of cards, how many rounds must at least be played before the game ends? What is the longest possible game? Are there any other possible interesting questions I could explore?

Answer 1

After a few tests, one realizes the following :

For any stacks $(a;b)$ with $a\geq b$ :

• if $a$ is odd; first player wins.
• else : if $b$ is odd first player wins, else second player wins.

Assuming we've proven point $2$, point $1$ is trivial :

• if $b$ is odd, first player can turn $(a;b)$ into $(a-1; b-1)$ where both $a-1$ and $b-1$ are even, resulting in a win for them.
• if $b$ is even, first player can turn $(a;b)$ into $(a-1; b)$ where $a-1$ and $b$ are even, resulting in a win for them.

In order to prove point $2$, just use a recurrence :

assuming $n$ is even and our two points hold for all $(p;k)$ with $p<n$ and $k\leq p$, observe that :

• $(n;0)$ can only be turned into $(n-1;0)$ which is a win for the second player as $n-1$ is odd;
• $(n;1)$ can be turned into $(n;0)$ which is a win for the first player;
• assume $\forall k<p, (n;k)$ is a win for the first player if $k$ is odd and second player if $k$ is even, then :
  • if $p$ is even, $(n;p)$ can only be turned into a win for the second player; since $(n-1; p)$, $(n-1;p-1)$ and $(n; p-1)$ are wins for the first player.
  • if $p$ is odd, $(n;p)$ is a win for the first player since it can be turned into $(n;p-1)$ which we just showed is a win for the second player.

This a bit messy and could very much be simplified but I hope you get the point.

Answer 2

Main idea

Consider a one-stack version of this game. Then the only move is to take $1$ from the stack, so it's a win for the next player ($\mathcal{N}$-position) if the stack has odd size, and a win for the other player ($\mathcal{P}$-position) if the stack has even size. You can prove this with induction.

To handle a two-stack (or any finite number of stacks if you can remove $1$ card from any nonempty selection of stacks) version of this game, if at least one stack would be an $\mathcal{N}$-position on its own, the next player should (make the winning) move in all of those. If no stack would would be a win for the first player, then the next player to move is doomed since every move would change at least one stack to an $\mathcal{N}$-position.

---

Proof for multiple stacks

To expand on why the claim above is true, let's say that we have a $p$-position if and only if all of the individual stacks are $\mathcal{P}$-positions and an $n$-position otherwise. Then we can prove by induction that the $\mathcal{P}$-positions (where the next player does not have a winning strategy) are precisely the $p$-positions (where the next player does not have a winning strategy in any of the individual stacks if they were played alone).

First note that if all of the stacks are empty, it's a $\mathcal P$-position by the rules of the game, and a $p$-position because every stack is empty (even size). Now suppose at least one stack is nonempty, and assume as an inductive hypothesis that all the $p$/$n$ determinations are correct for any collection of stacks you could reach in a single move (all of the "options" of the current position).

Case 1: All of those positions are $\mathcal N$-positions, so that every move is to a position where the next player will have a winning strategy, so the current position is a $\mathcal P$-position. But since those $\mathcal N$-positions are $n$-positions by hypothesis, every move must be to a position where at least one stack is an $\mathcal N$-position on its own. Since you can freely select which stacks you move in, the only way this could happen is if all of the stacks are $\mathcal P$-positions now (otherwise you could skillfully make winning moves in all the stacks that were $\mathcal N$-positions). Therefore, this is a $p$-position, too.

Case 2: One of the positions you can move to is a $\mathcal P$-position, so that that move is to a position where the next player will not have a winning strategy, so the current position is a $\mathcal N$-position. But since the $\mathcal P$-position you can move to is a $p$-position by hypothesis, that move must be to a position where all of the stacks are $\mathcal P$-positions on their own. Since moving in a $\mathcal P$-position stack would yield an $\mathcal N$-position stack, it must be the case that there is at least one $\mathcal N$-position stack to move to. Therefore, this is an $n$-position, too.

So by structural induction (or rephrasing this argument to be induction on the total number of cards, if you prefer), this $p$/$n$-position condition must be correct for every initial position.

---

Comment on general idea

The above argument works very generally for any game where the two players have the same moves available from any position ("impartial") that is built out of smaller games and you move in one or more of the smaller games on each turn (and you lose when you can't move). This sort of combination is called the "selective compound" (as opposed to the usual "disjunctive sum/compound"), and is covered in "Winning Ways" and "Combinatorial Game Theory" and this idea was also posted by Ted as an answer here.