Single-pile Nim with Three Players

Question

Three perfectly rational logicians (Alice, Bob and a Quetzalcoatlus) are playing a game. (Charlie couldn't make it, so he asked the Quetzalcoatlus to fill in for him.)

The rules are very simple:

• There are three players.
• Initially, there are 40 candies in a pile.
• On his, her or its turn, a player has to take 1 - 5 candies off the pile.
• The player that takes the last candy will lose.
• The other two players both win.

Bob has won the coin toss (done with a fair three-sided coin, probably) and gets to choose the seating order.

Given that the players are well known to be perfectly rational and impartial, only wanting to maximise their own chance of winning, even if by the tiniest amount, should Bob choose to go first, second, or third?

---

_{This particular game with these exact parameters was suggested by Kevin L, he asked if there was a strategy to guarantee a win for one of the players without collusion. Turns out, those parameters are also pretty much perfect for this question, which is a bit more difficult. At least for some very large values of "a bit".}

---

HINT 1: (contains no spoilers)

If the answer required brute force calculating the exact winning probabilities for each player at 40 candies, I wouldn't have posted it as a puzzle. Finding the shortcut is what this puzzle is all about.

HINT 2: (a little more spoileriffic)

I have commented on a partial answer, that the approach is a good one.

Answer 1

I will assume that

Given several equally desirable options, the players will randomly choose one.

Doing so, it is easy to work out what happens when there are $n$ candies;

• If $n=1$, then player 1 certainly loses.
• If $n=2$, then player 2 certainly loses.
• If $n=3$, then player 1 is indifferent between taking one and two candies, so player 2 or 3 loses with equal odds.
• If $n\in \{4,5,6\}$, the same thing happens. Moving down to $3$ or $4$ or $5$ is not safe, so but leaving one or two candies is equally desirable to player 1.
• If $n=7$, then player 1 will take 5 candies, so player 3 will lose.
• If $n=8$, then player 1 is indifferent between leaving 3, 4, 5 or 6 candies, all which result in them losing with probability 50%. In all of these cases, player 3 loses the other 50% of the time.

• If $n=9$, then things get interesting. Player 1 is indifferent between taking 1, 3, 4 or 5 candies (if they take 2, leaving 7, they certainly lose). In all four cases Player 1 loses with probability 50%. If they take 1 candy, then player 2 loses the other 50% of the time, and if they take 3-5 candies, then player 3 loses the other 50%. Since player 1 chooses randomly among these four options, the changes of player 2 losing are 12.5%, and of player 3 losing are 37.5%.

• If $n=10$, then taking one candy is the best option as it is the only one which gives a 37.5% chance of defeat, all other options giving 50% or 100%. This means player 2 loses with probability 50% and player 3 with probability 12.5%.

• If $n\in [11,15]$, then player 1's best bet is to move down to 10 candies, which gives them a 12.5% percent chance of losing. In all these cases, Player 2 loses with probability 37.5%, and player 3 loses with probability 50%.

From here on after, the pattern displayed in the range 9, 10, 11, ... , 15 repeats. At n = 16, player 1 is indifferent among dropping to 11 through 15. At n = 17, player 1 will take one candy, and at n = 18...24, player 1 will be eager to leave 17 candies.

The findings are summarized in this table. You can see that at $n=40$, player 1 will prefer to go first.

 n    P1   P2   P3
 1     1    0    0
 2     0    1    0
 3     0  1/2  1/2
 4     0  1/2  1/2
 5     0  1/2  1/2
 6     0  1/2  1/2
 7     0    0    1
 8   1/2    0  1/2
 9   1/2  1/8  3/8
10   3/8  1/2  1/8
11   1/8  3/8  1/2
12   1/8  3/8  1/2
13   1/8  3/8  1/2
14   1/8  3/8  1/2
15   1/8  3/8  1/2
16   1/2  1/8  3/8
17   3/8  1/2  1/8
18   1/8  3/8  1/2
19   1/8  3/8  1/2
20   1/8  3/8  1/2
21   1/8  3/8  1/2
22   1/8  3/8  1/2
23   1/2  1/8  3/8
24   3/8  1/2  1/8
25   1/8  3/8  1/2
26   1/8  3/8  1/2
27   1/8  3/8  1/2
28   1/8  3/8  1/2
29   1/8  3/8  1/2
30   1/2  1/8  3/8
31   3/8  1/2  1/8
32   1/8  3/8  1/2
33   1/8  3/8  1/2
34   1/8  3/8  1/2
35   1/8  3/8  1/2
36   1/8  3/8  1/2
37   1/2  1/8  3/8
38   3/8  1/2  1/8
39   1/8  3/8  1/2
40   1/8  3/8  1/2

Answer 2

Even though the question says I'm Bob, I'd like to start by stating my intention to be the Quetzalcoatlus, thanks very much.

I believe that the key to this game is that

you lose if you leave a specific number of candies on the table. As @Bass noted in the comments above, C would lose if they left 7 candies on the table, because then A takes $n$ candies, $n \in \{1,2,3,4,5\}$, and then B takes $6-n$ candies, leaving one on the table for C. However, this is not a forced play...the other two cannot force Q to leave 7 candies on the table. Q will win if they can take either candy 38 or candy 39. If candy 39, then A loses (assumed order: A-B-Q). If candy 38, then B loses (since A takes candy 39 and also wins). Therefore Q must lose if they are forced to leave 3 candies on the table. This means that there must be at least 8 candies on the table to start. So 8 is a $bad \hspace{0.5ex} number^{TM}$; A and B can and should conspire to leave Q with 8 since this will maximize their chances of winning (at 100% each). We can see that the pattern for $bad \hspace{0.5ex} numbers^{TM}$ is $BN = 7n + 1$, $BN\in\mathbb{N}$. We can show this as follows. If Q has 9-13 candies remaining, then they ought to leave 8 candies left in order to force a loss on A. If Q has 14 candies remaining, then they must leave 9, so A must take 1 in order to force a loss on B. If Q has 15 candies remaining, then they must leave between 10 and 14 candies. The other two players can then force a Q loss by leaving Q with 8 on their next turn (A=1,B=1 if 10 left by Q up to A=1,B=5 if 14 left by Q). Continuing the pattern above, the $bad \hspace{0.5ex} numbers^{TM}$ are 8, 15, 22, 29, 36. This means that as long as Q can avoid being left with 36, the optimal strategy for the two non-losing players is to join up and screw the last guy. The only way to achieve this is Quetzalcoatlus chooses to go first (remember I'm Q instead of B ;P) and picks 4 candies off the pile. He has then screwed over A, who automatically loses, and B conspires with Q because doing so maximizes his chances of winning at 100% if he does.

Example game:

Q: picks $4$, leaves $36$.
A: knows he's screwed, picks $n$, $n\in\{1,2,3,4,5\}$ and leaves $36-n$.
B: knows that A is screwed, picks $6-n$ and leaves $30$.
Q: picks $1$, leaves $29$.
A: knows he's screwed, picks $n$, $n\in\{1,2,3,4,5\}$ and leaves $29-n$.
B: knows that A is screwed, picks $6-n$ and leaves $23$.
Q: picks $1$, leaves $22$.
A: knows he's screwed, picks $n$, $n\in\{1,2,3,4,5\}$ and leaves $22-n$.
B: knows that A is screwed, picks $6-n$ and leaves $16$.
Q: picks $1$, leaves $15$.
A: knows he's screwed, picks $n$, $n\in\{1,2,3,4,5\}$ and leaves $15-n$.
B: knows that A is screwed, picks $6-n$ and leaves $9$.
Q: picks $1$, leaves $8$.
A: knows he's screwed, picks $n$, $n\in\{1,2,3,4,5\}$ and leaves $8-n$.
B: knows that A is screwed, picks $6-n$ and leaves $2$.
Q: picks $1$, leaves $1$.

However, there is a major issue with this...

This strategy requires collusion throughout (which isn't against these rules, at the moment). If A is left with 8, he can pick 2, for example, leaving 6. Then B can take 5 and screw Q, because this doesn't affect his chances of winning. Hence this strategy works for Bob 100%, and works for A and Q 50% of the time. This looks like it is the best that it's going to be for a poor Quetzalcoatlus if he starts....

Let me look at this from a different angle.

if person 1 picks up the 4th candy, then person 3 has a 100% winning strategy. Therefore I doubt anybody would willingly pick up the 4th candy as their last candy; they would likely pick more than that.

Answer 3

Partial strategy up to 11 candies. A is the player whose turn is next, B is the next player, and C is last.

If there are 2 candies left, A can win by taking 1. (B loses.)

If there are 3-6 candies left, A can force a win by leaving 1 or 2 candies on the table. We have to be impartial with respect to which of the other players loses, so 50% of the time A leaves 1 (B loses) and 50% of the time 2 (C loses).

If there are 7 candies left, A wins by taking 5. (C loses.)

If there are 8 candies left, A cannot force a win. Taking 1 loses for A (because B has to take 5 to win), every other move leaves B with 6-3 candies and it's a 50% chance for A to win.

If there are 9 candies left, taking 2 loses (B has to take 5 to win). Taking 1 leaves a 50% chance to win for A (B has to leave 3-6 for C so C wins and it's 50-50 between A and B). Taking 3-5 also leaves a 50% chance to win for A (B has 4-6 left so C wins and it's 50-50 between A and B). A has to be impartial with respect to B vs C winning, so 50% of the time A takes 2 and 50% of the time 3-5 (doesn't matter which, since the result is identical).

If there are 10 left, A can
- leave 5-6 (B wins, 50-50 between A/C)
- leave 8 (C wins, 50-50 between A/B)
- leave 9 (50% A wins and 50-50 between B/C, 50% C wins and 50-50 between A/B).
Leaving 9 gives A a 75% chance to win, whereas the other options give 50%. So A should leave 9.

If there are 11 left, A can
- leave 10 (50% B wins and 50-50 A/C, 50% A wins and 50-50 B/C)
- leave 9 (50% A wins and 50-50 B/C, 50% C wins and 50-50 A/B)
As per 10, leaving 6-8 is worse than leaving 9. A is indifferent between leaving 9 and 10, so should 50% leave 9 and 50% leave 10 in order to be impartial between B/C.

Don't think I can do it for 40 without turning this into a novel. But I have to say that, based on the name alone, Quetzalcoatlus sounds like a mean logician.

(Much later:) Humm. The shortcut escapes me, even after solving the winning percentages for all players from all positions. Apparently

the starting player has a slightly better chance of winning (67.2%, while the others have 66.4% each).

The critical initial position seems to be

36 candies left, which is slightly losing for the player whose turn it is. So A should go first and play a mix of taking 4 (putting B in the losing position) and taking 3 (allowing B to put C in the losing position by taking 1).

For what is worth, here are the numbers. The numbers are the winning percentage for A, B and C respectively if A is the next player to take.

1 left: (0, 100, 100)
2 left: (100, 0, 100)
3 left: (100, 50, 50)
4 left: (100, 50, 50)
5 left: (100, 50, 50)
6 left: (100, 50, 50)
7 left: (100, 100, 0)
8 left: (50, 100, 50)
9 left: (50, 75, 75)
10 left: (75, 50, 75)
11 left: (75, 62.5, 62.5)
12 left: (75, 62.5, 62.5)
13 left: (75, 62.5, 62.5)
14 left: (75, 50, 75)
15 left: (75, 75, 50)
16 left: (75, 75, 50)
17 left: (75, 75, 50)
18 left: (75, 75, 50)
19 left: (75, 75, 50)
20 left: (50, 75, 75)
21 left: (75, 50, 75)
22 left: (75, 62.5, 62.5)
23 left: (75, 62.5, 62.5)
24 left: (75, 62.5, 62.5)
25 left: (75, 62.5, 62.5)
26 left: (75, 75, 50)
27 left: (62.5, 75, 62.5)
28 left: (62.5, 68.8, 68.8)
29 left: (68.8, 62.5, 68.8)
30 left: (68.8, 65.6, 65.6)
31 left: (68.8, 65.6, 65.6)
32 left: (68.8, 65.6, 65.6)
33 left: (68.8, 65.6, 65.6)
34 left: (68.8, 65.6, 65.6)
35 left: (65.6, 68.8, 65.6)
36 left: (65.6, 67.2, 67.2)
37 left: (67.2, 65.6, 67.2)
38 left: (67.2, 66.4, 66.4)
39 left: (67.2, 66.4, 66.4)
40 left: (67.2, 66.4, 66.4)

Answer 4

With this information:

To be perfectly rational and impartial, only wanting to maximise their own chance of winning.

and it is assumed that

Everyone is taking as many candles as possible where they would not lose the game (who doesnt like candies), because at some points taking 3 candles or 4 candles are indifferent for some players but it could change the outcomes for other players.

If there were 5 candles

1- Bob will go first or last to guarantee not to lose, because whoever go first will take 4 candles, and the second player would lose for sure. Whoever go first would not go for 3 candles even if first player would be still guaranteeing to win because of the assumption given at the very beginning. Because it will change the game so much for the further parts. If first player would be taking 3 candles, last player would be losing, second player would be winning etc.

If there were 6 candles,

2- Bob will go first or last, bob will take 5 candles, because he would not lose after taking 5 candles anyway and second player will lose. or being last player is a default win too.

If there were 7,8,9,10 candles,

3- Bob would go first take 1-5 candles, and make the game into game $2$ as the last player in that game, or being second player making himself first player in game $2$.

If there were 11 candles,

4- Bob can take 5 candles and make the game into game $2$ to guarantee to win as the last player or second player since the first player will apply the same thing to win and Bob will be first player in game $2$ and win.

If there were 12 candles,

5- if first player will make this game into game $3$ or $4$ by taking 5 candles or 1 candle, he/she will lose since he/she will be the last player in game $3$ or game $4$ and lose. So whatever first player does, he would lose, so Bob needs to be second or last player for this many candles!

if there were 13-15 candles,

6- Bob would prefer being first player or last player. Because the first player will force to game $5$ to guarantee to win. And the last player will win when the first player makes tha game into game $5$ anyway.

if there were 16 candles,

7- Bob would go first player by taking less than 5 candles and win the game. Since players are taking as many candles as possible (my assumption) when they guarantee to win, the first player is supposed to be taking 4 candles, and it makes the game into game $5$. and in game $5$, second player wins too. so being last player in this game is also win!

after this, I am just putting the game because the same logic goes on:

and at the end,

Bob could go first or second to win the game with the assumption given at the very beginning.

Answer 5

Using the same assumption as @Oray,

If a player is at 6, he will take 5 candies. Assume also that all players know this and factor it into their decisions

Now

Given this, we can now define "losing states".
1 is a losing state.
2 to 6 are not since they can bring the next player down to 1.
7 to 11 are not since they can take the second player to a winning position and force the third player to lose.
12 is a losing state.
From here, the game is just a cycle. Every 1 modulo 11 is a losing state, so 34 is a losing state. Bob needs to go second so that whatever the first player picks, he can make the third player go to 34.

Answer 6

Jafe posted something very close to my intended answer, and it may be that he is correct, and I've made a mistake somewhere. To compare notes, here's my intended solution: (the tick has gone to a completely different answer, because it was very good, and fit every requirement given, although in a much more clever way that I had intended.

Intended optimal strategy

Interpret the players' impartiality in such a way, that when they have to give an advantage to one of their opponents, they'll choose either opponent with a 50% probability.

Then, for every possible number of candies, plot the best strategy for the player whose turn it is:

1:     you lose
2:     next player loses
3:     you are the kingmaker (you win, and choose the other winner)
4:     (ditto)
5:     (ditto)  
6:     (ditto)
7:     never happens, automatic loss for the player who left it
8:     next player is kingmaker (this is bad for you.)
9:     kingmaker-maker (you choose the kingmaker, but it won't be you, so also bad)
10:    always leave 9 (50% chance of getting to be the kingmaker)
11:    leave 10 or 9 (you are the kingmaker-maker-maker, or km^3:
       you choose, which of the other players is the kingmaker-maker)
12:    (ditto)
13:    (ditto)
14:    (ditto)
15:    never happens: the person leaving it automatically becomes the kingmaker-maker,
16:    next player is the km^3. This is bad for you.
17:    you are km^4. (You choose the km^3, but it won't be you. This is bad.)
18:    always leave 17. (50% chance of getting to be km^3)
19:    leave 17 or 18 (You are the km^5. This is good.)
20:    (ditto)
21:    (ditto)
22:    (ditto)
23:    never happens: the person leaving it automatically becomes the km^4
24:    next player is km^5 (bad)
25:    km^6 (bad)
26:    leave 25 (50% for km^5)
27:    km^7 (good)
28:    (ditto)
29:    (ditto)
30:    (ditto)
31:    never happens (bad)
32:    next player is km^7 (bad)
33:    km^8 (bad)
34:    leave 33 (50% for km^7)
35:    km^9 (good)
36:    (ditto)
37:    (ditto)
38:    (ditto)
39:    never happens
40:    next player is km^9

So there is a repeating pattern all the way from the beginning:

• 1 "bad" number (lose outright, or forced to choose whom to give the advantage, "even-powered kingmaker")
• 1 "good, but forced" number (either you or the player before you gets an advantage)
• 4 "just plain good" numbers (choose a player who gets the disadvantage, "odd-powered kingmaker")
• 1 "impossible" number (automatically very bad for the previous player)
• 1 "unwanted" number (also bad for the previous player, so won't be chosen unless there are only equally bad (or worse) options)

Since each repetition of the pattern exponentially diminishes the advantage gained from being the odd-powered kingmaker, at 40 candies it's almost all the same what to do. But since it does give a tiny advantage, Barry should choose to go second in this game.

---

EDIT:

Should you want to out exactly how (in)significant this advantage is, we can list the winning probabilities for each player. To construct the next row in the list, choose among the five previous rows the one(s) that has the biggest number in the right hand column. Rotate the numbers one spot to the right to get the numbers for the new row. If there are more than one possible row to choose from, pick one row that favours one opponent, and one row that favours the other, rotate both, and average their values.

 N: best strategy | winning probabilities, in 1/512 parts
---------------------------------------------------------
 1: take 1        | (0,   512, 512)
 2: take 1        | (512,   0, 512) 
 3: take 1 or 2   | (512, 256, 256) = avg((512, 0, 512), (512, 512, 0))
 4: take 2 or 3   | ditto
 5: take 3 or 4   | ditto
 6: take 4 or 5   | ditto
 7: take 5        | (512, 512,   0)
 8: take 2-5      | (256, 512, 256)
 9: take 1 or 3-5 | (256, 384, 384) = avg((256, 512, 256), (256, 256, 512))
10: take 1        | (384, 256, 384)
11: take 1 or 2   | (384, 320, 320) = avg((384, 256, 384), (384, 384, 256))
12: take 2 or 3   | ditto
13: take 3 or 4   | ditto
14: take 4 or 5   | ditto
15: take 5        | (384, 384, 256)
16: take 2-5      | (320, 384, 320)
17: take 1 or 3-5 | (320, 352, 352) (avg) 
18: take 1        | (352, 320, 352) 
19: take 1 or 2   | (352, 336, 336) (avg)
20: take 2 or 3   | ditto
21: take 3 or 4   | ditto
22: take 4 or 5   | ditto
23: take 5        | (352, 352, 320)
24: take 2-5      | (336, 352, 336)
25: take 1 or 3-5 | (336, 344, 344) (avg)
26: take 1        | (344, 336, 344)
27: take 1 or 2   | (344, 340, 340) (avg)
28: take 2 or 3   | ditto 
29: take 3 or 4   | ditto 
30: take 4 or 5   | ditto 
31: take 5        | (344, 344, 340)
32: take 2-5      | (340, 344, 340)
33: take 1 or 3-5 | (340, 342, 342) (avg)
34: take 1        | (342, 340, 342)
35: take 1 or 2   | (342, 341, 341) (avg)
36: take 2 or 3   | ditto 
37: take 3 or 4   | ditto 
38: take 4 or 5   | ditto 
39: take 5        | (342, 342, 340)
40: take 2-5      | (341, 342, 341)
-------------------------------------------------

It's pretty easy to see that the winning probabilities all tend towards 2/3 for each player. At 40 candies, there's still a little bit of imbalance left, so that out of 512 games, the player that goes second is expected to gain one more win than the others. In terms of winning percentage, the second player wins with about 66.8% probability, while the others only win with 66.6%, or in other words, there's a gain of about one fifth of a percentage point.