The game of pebbles

Question

The game of pebbles is a two-player game. The game starts with $N$ stones, and a number $c>2$ is fixed. On a player's turn, he or she must remove either $1$ or $c$ stones. The player who does not take the last stone is the winner.

Is there a winning strategy?

Answer 1

The losing positions for the first player are those for which:

The remainder of the division of N by c+1, which I'll call f (N) = N mod (c+1) , is odd.

Proof:

Note that decreasing N by 1 decreases f (N) by 1 and decreasing N by c increases f (N) by 1.

From a losing position, if f (N) is odd, then either move brings us to a position when f is even, which is winning.

From a winning position, if f (N) is even, then at least one move brings us to a position where f is odd, and is losing. (One of them might cause us to wrap-around and go from 0 to c, but in this case the other one surely does not.)

Answer 2

The english, as the way it's written, is completely over my head. I'm reading it as:

A game of $m$ players with $N$ stones, players take $a \geq 1$ stones as each turn. The winner is the one to take the penultimate stone.

Which is very trivial (and similar to the puzzle mentioned in this numberphile video), (100% sure my answer is worng because I didn't understand the problem correctly):

The first person takes $N-1$ pebbles. He wins. Period.

Answer 3

There is an optimal strategy, but not a winning strategy. I'm assuming that c and N are fixed before the game starts, and this is a request for a general solution. Winning is primarily determined by c, N and start position.

First, I'm assuming everyone wants to win, so if given the choice between drawing c and drawing 1, no one will draw c and lose if the number of pebbles left is less than or equal to c.

If c is odd, than there is no difference in strategy. The first player wins if N is even, and loses if N is odd. This is because each person drawing changes the number of pebbles left from even to odd. So one player always draws when it is even and one player always draws when it is odd. The winner is the person who leaves someone only 1 pebble to draw. 1 is odd.

If c is even, then obviously things are a bit more demanding. At that point, the second player has control over whether an even or odd number of pebbles is drawn by the pair of players. Therefore, the second player can ensure that the number of pebbles stays even if it starts even (by matching the first player with 1 or c), or becomes even (by choosing the opposite).

Answer 4

Assuming the pile of pebbles is visible and the players can see the amount of remaining stones, there is some strategy that can help win the game. However, it is not possible to win in all scenarios.

Restating the game rules:

• Game is for two players only.
• Starting player is selected randomly (eg. flipping a coin).
• Constant c is greater than 2 and defined before the game starts (eg. by throwing one or multiple dice).
• On each turn, players can remove 1 or c pebbles from the pile.
• The player who removes the last pebble loses the game.

Now, lets evaluate the different scenarios.

When c > N

If c is greater than the number of pebbles, the only option left for the player is to remove 1 pebble until there is only one left.

In this scenario, if the number of pebbles in the pile is even, the current player always wins. If the number of remaining pebbles is odd, the current player always loses.

This is very important to know, because it is key to win the game.

When c = N

When c is equal to the number of pebbles in the pile, the player will still have the option to remove 1 or to remove all. Removing all would end the game and the player would lose (would have removed the last pebble together with the other ones).

Thus, when c is equal to N, the only possible way for the player to win is by removing one pebble. However, as we saw before, the outcome at this point will depend on the parity of the pebbles in the pile. If the number of remaining pebbles is even, the current player will win the game. If the number is odd, the current player will lose whether it removes one pebble or the entire pile (c).

When c < N

This should be the starting point for most games (where N is greater than c). And it is the only scenario where the players can play some strategy.

As we just saw, once c is less or equal to N, the winning player is automatically predetermined by the party of the number of remaining pebbles.

With this information, we can conclude that...

as long as N is greater than c, the best strategy would be to remove pebbles in a way that leaves an odd number of pebbles equal to or less than c.