5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ There could be multiple strategies although it would depend on the number of players, who goes first and whether the 'taking' is blind (from a bag for example). Quick maths on the part of the participant would probably be important. $\endgroup$ – BreakingMyself Jul 1 '17 at 9:40
  • $\begingroup$ the game is with 2 gamers $\endgroup$ – Dattier Jul 1 '17 at 10:42
  • $\begingroup$ I'm assuming the answer uses modulos, but I'll let someone else type the answer :D $\endgroup$ – Eric Lee Jul 1 '17 at 17:40
  • $\begingroup$ @EricLee : yes. $\endgroup$ – Dattier Jul 1 '17 at 17:50
3
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Bravo, what about the case, when the choice is 1,2 or 4 stones ? $\endgroup$ – Dattier Jul 1 '17 at 20:39
  • 1
    $\begingroup$ This case is more difficult, should I propose it in the form of a new enigma? $\endgroup$ – Dattier Jul 2 '17 at 9:14
  • $\begingroup$ @Dattier yes please! $\endgroup$ – IanF1 Jul 4 '17 at 19:54
  • $\begingroup$ @lanF1 Sorry, I have proposed it (and others) in the chat, and the questions were answered $\endgroup$ – Dattier Jul 4 '17 at 20:48
  • $\begingroup$ @lanF1 (N mod 3)=1 is the losing position. $\endgroup$ – Dattier Jul 5 '17 at 13:13
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You can choose 1 or c(>2) pebbles, not only one. $\endgroup$ – Dattier Jul 1 '17 at 12:28
  • $\begingroup$ I'm not a mathematician so a better description of c(>2) would be appreciated please @Dattier as you didn't confirm my guess above. I couldn't even google it lol $\endgroup$ – BreakingMyself Jul 1 '17 at 13:50
  • $\begingroup$ What if $c=3$ and $N=50$? It wouldn't work then $\endgroup$ – Eric Lee Jul 1 '17 at 17:39
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Sorry, I don't think. This does not depend on the parity of c. I think there are a better strategy. $\endgroup$ – Dattier Jul 1 '17 at 20:06
  • $\begingroup$ I'm not sure I completely understand your logic. Could you give a couple of example games to demonstrated the strategies? Particularly the even one I am having trouble getting straight in my head... $\endgroup$ – Chris Jul 1 '17 at 22:05
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As Eric says that, I think the better strategy used the modulos. $\endgroup$ – Dattier Jul 1 '17 at 20:10
  • $\begingroup$ Well, obviously, as long as N is greater than c, you can divide and calculate the remainder. The key is to know when to remove 1 or remove c and that has to do more with the parity of the remaining pile than the modulus. $\endgroup$ – Eneko Alonso Jul 1 '17 at 20:15
  • $\begingroup$ Read the strategy that propose ffao. $\endgroup$ – Dattier Jul 1 '17 at 20:41
  • $\begingroup$ The final paragraph has the problem that it says "the best strategy would be to remove pebbles in a way that ..." (quote cut off to preserve spoilers). It doesn't actually say how to do that. If N is 200 and C is 5 how many should I remove? This answer doesn't make it clear. And that's why you need modulus - to work out the strategy when you are much further from your target. $\endgroup$ – Chris Jul 1 '17 at 22:10

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.