Iyfjky

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.

"Charlie couldn't make it, so he asked the Quetzalcoatlus to fill in for him." :)) — Aug 14 at 13:32
one thing is not given, players are aiming to finish the game and take as many candles as possible or they can randomly decide when they guarantee to win somehow? — Aug 14 at 14:16
It's stated that the players aim to maximize their own chance of winning. — Aug 14 at 14:18
@Oray they choose impartially. I actually just found a pretty recent (2013) paper that uses a fixed preference (each winning player wants to have played as late as possible) to solve this puzzle in a game theoretically significant way, but since I'm not a game theoretician, I didn't know about that when I made this puzzle, and so we're stuck with all this impartiality annoyance. — Aug 14 at 17:01
If there are 3 candies left the next player is guaranteed to win by taking either 1 or 2. The question doesn't specify how they play when two different options give identical chances of winning. — Aug 14 at 21:50

Mike Earnest 20.5k567211 · Accepted Answer · 2018-08-15 19:20:21Z

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 $nin 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 $nin [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

Also, here is some code which confirms the above result: repl.it/@mearnest/Three-player-takeaway-game — Aug 15 at 19:31
This answer seems correct, fits all the given clues, and isn't the one I intended. (The impartiality was supposed to mean impartiality between opponents when having to choose whom to give the advantage to). Therefore I'm afraid I have to say: Thank you, Good Sir, for finding a meaningful, unintended interpretation for my question, and even one that produces a very sensible answer! Here's your green tick! — Aug 17 at 11:47

score 6 · Answer 2 · 2018-08-14 13:51:30Z

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 hspace0.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 hspace0.5ex numbers^TM$ is $BN = 7n + 1$, $BNinmathbbN$. 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 hspace0.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$, $nin1,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$, $nin1,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$, $nin1,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$, $nin1,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$, $nin1,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.

If I'm Alice in this game, I might just take my candies and go home. — Aug 14 at 13:28
This is actually not quite true, since Bob still has the chance to screw over Quetzalcoatlus in the final stages of the game, having assured his victory.....but then gets prompted smote (smited?) because I wasn't Quetzalcoatlus at all! — Aug 14 at 13:31
Collusion isn't against the rules as they are written, but I hope the question is pretty clear on the point that the players aren't going to resort to that. — Aug 14 at 13:50
I can guarantee that the answer isn' exactly 2/3, but I'm afraid the "even by the tiniest amount" qualifier given in the question may become relevant.. — Aug 14 at 14:58

score 6 · Answer 3 · 2018-08-17 12:18:53Z

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)

This approach is definitely the way to solve this game. You may also notice, that the will never be 7 candies to choose from: C, whose turn was last, would never make such a bad choice. — Aug 14 at 12:21
From 14, you can reach either 9 or 10, both giving 75% for the previous player, so the percentages should be the same as for 11-13. (I posted my intended solution as a self-answer somewhere below, but that will spoil the shortcut thingy altogether.) — Aug 17 at 16:09
Yeah there's an error there. I have a feeling it'll come up as equivalent to your solution once fixed... — Aug 17 at 16:14
I think so too. I only calculated the values for the first < 20 candies when I was verifying my solution, but these numbers look very familiar. — Aug 17 at 16:15

sedrick 1,641514 · Answer 4 · 2018-08-14 15:34:29Z

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.

This is exactly the correct kind of reasoning, but I think you have overlooked something important: if Bob leaves the next player with 3 candies, that player can guarantee a win by taking either 1 or 2, and Bob will be among the winners only in the latter case. — Aug 14 at 16:04
I'd like to retract my previous comment about overlooking things, (leaving it up though): you very likely didn't overlook anything, but chose to solve the puzzle in a game theoretically interesting way. My bad for choosing a game theoretically less interesting formulation with impartial choices for every player. Glad I +1ed your answer the first time I saw it. — Aug 14 at 17:19

score 3 · Answer 5 · 2018-08-14 15:04:39Z

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.

This is a good answer, I like the pattern! The only issue I have is with the "indifference" notion, ie. with the idea that taking a maximal amount of candies is always preferential. If there are 6 candies left, for example, player 1 takes 5 and wins every time (p2 loses)...but player 1 can also take 4 and win every time (p3 loses). P1 should therefore (by my interpretation at least) be indifferent between taking 4 or 5 candies, meaning that P2 and P3 should both lose in this scenario 50% of the time. — Aug 14 at 14:45
@El-Guest that's why I added the assumption, otherwise those 50%s are getting bigger and bigger :) — Aug 14 at 14:47
It would be interesting to see if there's a strategy without the assumption...I feel there are too many possibilities to not brute-force it. That said, this solution is definitely at least 50% more elegant than mine, even with the assumption.....please, take my up-quetzalcoatlus! :) — Aug 14 at 14:49

score 1 · Answer 6 · 2018-08-18 11:14:28Z

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.

I think your interpretation of the rules is more natural and leads to a more interesting problem. I also get the km^n situation, though I do not think I would have arrived at that simplification even if I had correctly interpreted the rules. — Aug 17 at 15:27

Mike Earnest 20.5k567211 · Accepted Answer · 2018-08-15 19:20:21Z

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 $nin 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 $nin [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

Also, here is some code which confirms the above result: repl.it/@mearnest/Three-player-takeaway-game — Aug 15 at 19:31
This answer seems correct, fits all the given clues, and isn't the one I intended. (The impartiality was supposed to mean impartiality between opponents when having to choose whom to give the advantage to). Therefore I'm afraid I have to say: Thank you, Good Sir, for finding a meaningful, unintended interpretation for my question, and even one that produces a very sensible answer! Here's your green tick! — Aug 17 at 11:47

score 6 · Answer 8 · 2018-08-14 13:51:30Z

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 hspace0.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 hspace0.5ex numbers^TM$ is $BN = 7n + 1$, $BNinmathbbN$. 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 hspace0.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$, $nin1,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$, $nin1,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$, $nin1,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$, $nin1,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$, $nin1,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.

If I'm Alice in this game, I might just take my candies and go home. — Aug 14 at 13:28
This is actually not quite true, since Bob still has the chance to screw over Quetzalcoatlus in the final stages of the game, having assured his victory.....but then gets prompted smote (smited?) because I wasn't Quetzalcoatlus at all! — Aug 14 at 13:31
Collusion isn't against the rules as they are written, but I hope the question is pretty clear on the point that the players aren't going to resort to that. — Aug 14 at 13:50
I can guarantee that the answer isn' exactly 2/3, but I'm afraid the "even by the tiniest amount" qualifier given in the question may become relevant.. — Aug 14 at 14:58

score 6 · Answer 9 · 2018-08-17 12:18:53Z

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)

This approach is definitely the way to solve this game. You may also notice, that the will never be 7 candies to choose from: C, whose turn was last, would never make such a bad choice. — Aug 14 at 12:21
From 14, you can reach either 9 or 10, both giving 75% for the previous player, so the percentages should be the same as for 11-13. (I posted my intended solution as a self-answer somewhere below, but that will spoil the shortcut thingy altogether.) — Aug 17 at 16:09
Yeah there's an error there. I have a feeling it'll come up as equivalent to your solution once fixed... — Aug 17 at 16:14
I think so too. I only calculated the values for the first < 20 candies when I was verifying my solution, but these numbers look very familiar. — Aug 17 at 16:15

sedrick 1,641514 · Answer 10 · 2018-08-14 15:34:29Z

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.

This is exactly the correct kind of reasoning, but I think you have overlooked something important: if Bob leaves the next player with 3 candies, that player can guarantee a win by taking either 1 or 2, and Bob will be among the winners only in the latter case. — Aug 14 at 16:04
I'd like to retract my previous comment about overlooking things, (leaving it up though): you very likely didn't overlook anything, but chose to solve the puzzle in a game theoretically interesting way. My bad for choosing a game theoretically less interesting formulation with impartial choices for every player. Glad I +1ed your answer the first time I saw it. — Aug 14 at 17:19

score 3 · Answer 11 · 2018-08-14 15:04:39Z

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.

This is a good answer, I like the pattern! The only issue I have is with the "indifference" notion, ie. with the idea that taking a maximal amount of candies is always preferential. If there are 6 candies left, for example, player 1 takes 5 and wins every time (p2 loses)...but player 1 can also take 4 and win every time (p3 loses). P1 should therefore (by my interpretation at least) be indifferent between taking 4 or 5 candies, meaning that P2 and P3 should both lose in this scenario 50% of the time. — Aug 14 at 14:45
@El-Guest that's why I added the assumption, otherwise those 50%s are getting bigger and bigger :) — Aug 14 at 14:47
It would be interesting to see if there's a strategy without the assumption...I feel there are too many possibilities to not brute-force it. That said, this solution is definitely at least 50% more elegant than mine, even with the assumption.....please, take my up-quetzalcoatlus! :) — Aug 14 at 14:49

score 1 · Answer 12 · 2018-08-18 11:14:28Z

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.

I think your interpretation of the rules is more natural and leads to a more interesting problem. I also get the km^n situation, though I do not think I would have arrived at that simplification even if I had correctly interpreted the rules. — Aug 17 at 15:27

Search This Blog

Iyfjky

Single-pile Nim with Three Players

6 Answers
6

Intended optimal strategy

Your Answer

Post as a guest

6 Answers
6

6 Answers
6

Intended optimal strategy

Intended optimal strategy

Intended optimal strategy

Intended optimal strategy

Post as a guest

Comments

Post a Comment

Popular posts from this blog

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor

Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

Confectionery

Category

Random preview

Single-pile Nim with Three Players

6 Answers 6

Intended optimal strategy

Your Answer

Sign up or log in

Post as a guest

Post as a guest

6 Answers 6

6 Answers 6

Intended optimal strategy

Intended optimal strategy

Intended optimal strategy

Intended optimal strategy

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Comments

Post a Comment

Popular posts from this blog

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor

Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

Confectionery

6 Answers
6

6 Answers
6

6 Answers
6

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor