Learn / Library / Brainteasers

Piles with a joint move

BrainteasersHard

There are $2$ piles of cards with $7$ and $10$ cards. $2$ players alternate. A move either takes any positive number of cards from one pile, or takes the same positive number of cards from both piles. The player who takes the last card wins. You move first and both players play optimally. How many different first moves guarantee you a win?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

List the lost positions for the player to move, starting from $(0, 0)$ , and see which of them you can reach.

Solution

Call a position lost if the player to move loses; $(0, 0)$ is lost, and the next lost positions, up to order, are $(1, 2)$ , $(3, 5)$ , $(4, 7)$ and $(6, 10)$ .
Each new lost pair starts with the smallest number not used so far, and the gap between its entries is one more than in the previous pair.
From $(7, 10)$ you can reach $(6, 10)$ by taking $1$ card from the first pile, $(7, 4)$ by taking $6$ from the second, and $(4, 7)$ by taking $3$ from each pile.
No other lost position, such as $(1, 2)$ or $(3, 5)$ , can be reached in one move, since that would need unequal amounts from both piles.
So the number of winning first moves is $3$ .

Answer: $3$

Next question Back to the library