7
$\begingroup$

This is a game for 2 players - Each player uses a different coloured marker or pencil, there are 15 pebbles in total.

Players take turns to colour 1, 2 or 3 pebbles (player chooses how many). When all pebbles have been coloured, the winner is the one who colours the odd number. You cannot recolour the pebbles.

For example - If you get seven and your opponent gets eight, you win. If you get six and your opponent gets nine, they win.

What strategy would you incorporate in order to be sure that you win? If there is no such strategy, what is the optimal strategy that increases the likelihood of winning?

Edit: Can the strategy be generalized for $c$ Players with the total number of pebbles as $N$?

Edit 2: Adding another player would cause many instances of draw, therefore $c=2$ for all purposes.

$\endgroup$
  • $\begingroup$ Can you colour pebbles which have previously been coloured? $\endgroup$ – hexomino Jun 19 at 11:55
  • 1
    $\begingroup$ No we cannot do that. However that would make the question much more interesting I think. $\endgroup$ – IE Irodov Jun 19 at 12:03
  • $\begingroup$ @hexomino recoloring pebbles could result in an infinite game $\endgroup$ – melfnt Jun 19 at 12:31
  • $\begingroup$ Who is the winner in the $c$ players variant? $\endgroup$ – melfnt Jun 19 at 12:34
  • $\begingroup$ @melfnt you're right, it would many cases where multiple players have odd number of pebbles thereby requiring more conditions to win. I am removing that part of the edit. Adding more conditions would it unnecessarily convoluted. But we could have a variant of colouring over previously coloured pebbles provided there are uncoloured pebbles left. This is assuming players won't be coloring the same initial pebbles again and again. $\endgroup$ – IE Irodov Jun 19 at 12:44
6
$\begingroup$

As with pretty much all the variants, this one can be solved by starting from the end and working backwards. With the original total number of stones being an odd number (15, as given in the title) the players will have the same parity whenever there's an odd number of pebbles left, so it's easy to work out the best strategies: they are the ones that put the opponent to a known-losing position. If no such move exists, the position is losing.

 Pebbles left | Opp. parity |  Odd   | Even
            0 | Diff        | W      | L
            1 | Same        | L      | W (1)
            2 | Diff        | W (2)  | W (1)
            3 | Same        | W (2)  | W (3)
            4 | Diff        | L      | W (3)
            5 | Same        | W (1)  | L
            6 | Diff        | W (1)  | W (2)
            7 | Same        | W (3)  | W (2)
            8 | Diff        | W (3)  | L
            9 | Same        | L      | W (1)
           10 | Diff        | W (2)  | W (1)
           11 | Same        | W (2)  | W (3)
           12 | Diff        | L      | W (3)
           13 | Same        | W (1)  | L
 
To mechanically construct the table, first fill in row 0, and then for each position, look how many steps up you need to go to hit an "L". If "Opp. parity" is "Diff", then go up the other column instead.

As we can see, the pattern repeats after eight steps, so we don't have to count all the way to 15, but we can instead just subtract 8, and look at the strategy for 7 pebbles. Since we have an even number of pebbles, and presumably we get to start, we should colour

2 pebbles

which leaves the opponent in a losing position that's actually included in the table.

This table works for all sensible starting positions with two players: if the starting number of pebbles were even, the only possible result would be a tie (both win, or both lose.)

Since the table may seem a bit hard to memorise, here's the strategy again in "condensed form":

If your opponent has an odd number of pebbles, leave 1 or 4 pebbles (mod 8).
If your opponent has an even number of pebbles, leave 0 or 5 pebbles (mod 8).

| improve this answer | |
$\endgroup$
5
$\begingroup$

The strategy is to do a move that

either
- gives you an odd total of coloured pebbles and leaves 0,1,8, or 9 uncoloured pebbles in the pile (or more generally $8k+0$ or $8k+1$),
or
- gives you an even total of coloured pebbles and leaves 4,5,12, or 13 uncoloured pebbles in the pile (or more generally $8k+4$ or $8k+5$).

In particular, for $15$ pebbles, your first move would be

$2$ pebbles, leaving $13$ and an even score.

The reason this works is more interesting than with other single-pile nim variants.

It is clear that your final winning position is to leave 0 or 1 pebble and have an odd number of coloured pebbles.
As with other variants, you can force the pile to reduce by 4 pebbles by replying to a move of $m$ pebbles with a move of $4-m$ pebbles. Since you want to end up at $0$ or $1$, the size of the pile of remaining pebbles follows the sequence $...,16,12,8,4,0$ or $...,17,13,9,5,1$. As long as your opponent makes a move $m=1$ or $m=3$, this works out fine, and your score changes parity every time, and ends up as odd when you reach $0$ or $1$.
If the opponent does move $m=2$ however, you must not take $2$ yourself because you need the parity of your score to change. You can however take $1$ or $3$ to reduce the pile by $3$ or $5$ this round instead of $4$. You must choose the move such that you switch between the $...,16,12,8,4,0$ and the $...,17,13,9,5,1$ pile size sequences.

| improve this answer | |
$\endgroup$
0
$\begingroup$

as @Bass mention I think you can lower the table to

        Pebbles left |  you have Odd number stones  | you have Even number  stones 

        0            | W                            | L

        1            | L                            | W (1)

        2            | W (2)                        | W (1)

        3            | W (2)                        | W (3)

Let say K is the number pebble left.

when you count the next step as if k is odd then:

If your nunber of pebbles odd then you open number pebvles even.

Find losing game for k-1,k-2,k-3 For the even column If you find one you win else you lose.

same principle for even:

this why I think

        Pebbles left |  you have Odd number stones  | you have Even number  stones 

        4            | L                            | W (3)

        5            | W(1)                      | L

(sorry cant comment not enough points)

| improve this answer | |
$\endgroup$
  • $\begingroup$ When there are 5 pebbles left, and you have an odd number of pebbles, opponent also has an odd number of pebbles. That's why you look for the losing position in the same column. You can always check the result by playing out all the variations: Let's say we both have 5 pebbles, so there's 5 left. I take 1. If you take 1, I take 3 and win. If you take 2, I take 3 and win. If you take 3, I take 1 and win. So 5 pebbles with odd is winning. $\endgroup$ – Bass Jun 25 at 2:30
  • $\begingroup$ Yes i see my mistake, in my solution when taking stone ithink I change parity for my oponnent so I think fixing my solution you need to: calc openent party and find in 3 stone below if their is a losing game for this parity $\endgroup$ – Vlad Barkanass Jun 25 at 4:47
  • $\begingroup$ Sorry now I see that you write" To mechanically construct the table, first fill in row 0, and then for each position, look how many steps up you need to go to hit an "L". If "Opp. parity" is "Diff", then go up the other column instead." So yes my bad I think you have full solution. $\endgroup$ – Vlad Barkanass Jun 25 at 4:59

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.