strategy - Single-pile Nim with Three Players

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

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