Is there a winning strategy in the card removal game?

151 Views Asked by At

A and B play a game with blue, red, and green cards. They start with an even number of $n$ blue cards ("stacks"). Player A starts, and the players take turns. Only two moves can be made: (i) Place a red or green card on an existing stack, but the stack must not have two cards of the same color (a stack cannot have more than three cards). (ii) If the top cards of two stacks have the same color both the stacks can be removed from the game. The reservoir of cards is "infinite", i.e. no player can run out of cards. The player who can't make a permissible move loses.

Can any of the players enforce a winning strategy and what would it be?


This is a strategy I conceived and so far it seems to work in "test games" that I ran in a spreadsheet. Not conclusive, I guess, but am I on the right track?

If $k\equiv2\mod 4$, then A can always force the victory. Otherwise, that is, $k\equiv0\mod 4$, B can force the victory. I begin by showing that if $k\equiv0\mod4$, B can force victory.

Now let $k\equiv0\mod4$. Then B can follow the following strategy to force victory. B will mentally divide the stacks into pairs of two. He will ensure during the game that the top color of each pair is always the same. If A takes away a pair, B will also take away a pair, and if A recolors a stack, B will color the corresponding "partner piece" in the same color. Thus, whenever it is A's turn, all pairs are removable. If A now takes away a pair, the total number $k$ of stacks is reduced by two, so $k\equiv2\mod4$. Thus , there must still be at least one pair that B can take away. Since the height of each stack is at most $3$, there is a finite number of moves and the game will surely come to an end. In this case, player A always leaves a number of stacks with $k\equiv2\mod4$ and B with $k\equiv0\mod4$. Thus, with this strategy, B will certainly always be able to take away the last stack and thus win.

If the game now starts with $k\equiv 2\mod 4$, A can remove $2$ stacks at the beginning. This gives B the starting position of the above strategy (a number of stacks with $k\equiv0\mod4$) and A can force the victory.