A Truel
I heard this problem many years ago when I was working for Math Alive.
Three men are fighting in a truel. Andrew is the worst shot; he misses 2/3 of the time. Bob is better; he misses 1/3 of the time. Connor is the best shot; he always hits. Each of the three men have an infinite number of bullets. Each shot is either a kill or a miss. They have to shoot at each other in order until two of them are dead. To make it more fair they decide to start with Andrew, followed by Bob, and then Connor. We assume that they choose their strategies to maximize their probability of survival. At whom should Andrew aim for his first shot?
This is a beautiful probability puzzle, and I will not spoil it for you by writing a solution. Recently, I watched an episode of Numb3rs: The Fifth Season (“Frienemies”) which featured a version of this puzzle. Here is how Dr. Marshall Penfield, a frienemy of the protagonist Charlie Eppes, describes it:
Imagine a duel between three people. I’m the worst shot; I hit the target once every three trials. One of my opponents [Charlie] is better; hits it twice every three shots. The third guy [Colby] is a dead shot; he never misses. Each gets one shot. As the worst I go first, then Charlie, then Colby. Who do I aim for for my one shot?
This is a completely different problem; it’s no longer about the last man standing. Colby doesn’t need to shoot since the other two truelists have already expended their only shots. If Charlie believes that Colby prefers nonviolence, all else being equal, then Charlie doesn’t need to shoot. Finally, the same is true of Marshall. There is no point in shooting at all.
To make things more mathematically interesting, let’s assume that the truelists are bloodthirsty. That is, if shooting doesn’t decrease their survival rate, they will shoot. How do we solve this problem?
If he survives, Colby will kill someone. If Charlie is alive during his turn, he has to shoot Colby because Colby might kill him. What should Marshall do? If Marshall kills Colby, then Charlie misses Marshall (hence Marshall survives) with probability 1/3. If Marshall kills Charlie, then Marshall is guaranteed to be killed by Colby, so Marshall survives with probability 0. If he doesn’t kill anyone, things look much better: with probability 2/3, Colby is killed by Charlie and Marshall survives. Even if Colby is alive, he does not necessarily shoot Marshall, so Marshall survives with probability at least 2/3. Overall, Marshall’s chances of staying alive are much better if he misses. He should shoot in the air!
The sad part of the story is that Charlie Eppes completely missed. That is, he completely missed the solution. In the episode he suggested that Marshall should shoot Charlie. If Marshall shoots Charlie, he will be guaranteed to die.
It is disappointing that a show about math can’t get its math right.
Share:
Akshay:
Case 1 – Total chance Andrew wins is 2/27 + 1/6 = 0.24
Andrew shoots at Bob.
2/3 chance – Bob lives
Bob shoots at Andrew (but both end in him dying)
1/3 chance – Andrew lives
Con shoots Bob. Bob dies. Andrew shoots at Con.
2/3 chance – Con lives
Con shoots Andrew. Game Over.
1/3 chance – Con dies. Game Over.
2/3 chance – Andrew dies
Con shoots Bob. Game Over
Bob shoots at Con
1/3 chance – Con lives
Con shoots Bob. Bob dies. Andrew shoots at Con.
2/3 chance – Con lives
Con shoots Andrew. Game Over.
1/3 chance – Con dies. Game Over.
2/3 chance – Con dies. Andrew shoots at Bob and they play each other. (4/9)*(1/3) + (4/9)(1/3)(1/3)(1/3) + … = 1/6
1/3 chance – Bob dies
Con shoots Andrew. Game Over
Case 2 – Total chance Andrew wins is 2/9 + 1/24 = 0.26
Andrew shoots at Con.
2/3 chance – Con lives
Con shoots Bob. Bob dies. Andrew shoots at Con.
2/3 chance – Con lives
Con shoots Andrew. Game Over.
1/3 chance – Con dies. Game Over.
1/3 chance – Con dies.
Bob shoots Andrew.
1/3 chance – Andrew lives
Andrew shoots at Bob and they play each other. (1/9)*(1/3) + (1/9)(1/3)(1/3)(1/3) + … = 1/24
2/3 chance – Andrew dies. Game Over.
So Andrew should shoot Conner. Hopefully I didn’t make any mistake.
29 August 2010, 8:28 pmSteveS:
Akshay, I think your probability (or your game theory) is skewed somewhere – you break down the ‘Bob shoots at Andrew’ and ‘Bob shoots at Con’ cases, but don’t assign them probabilities, and it looks like you just straight-up add them together. Similarly, your analysis of the ‘Con dies and Andrew and Bob start aiming at each other’ seems to assign the wrong probability to the results (if I’m calculating correctly!).
The short version of the analysis goes something like this: C, if he’s alive and has a choice, will always shoot B, because doing so maximizes his chances of survival – his chance of surviving is 2/3rds if A gets a shot at him, and 1/3rd if B gets a shot at him (since C is guaranteed to kill the other survivor next turn if he’s still alive), so ‘eliminate the biggest threat’ is correct for C. Because of this, B (if he’s alive and has a choice) must shoot C to maximize *his* chances of survival. These are pure, optimum strategies for B and C; B will never shoot A unless C is already dead.
Now, the only potentially-infinite situation is the one in which only A and B are left alive, and continually shoot at each other. It’s easy to see that if A shoots first, his chance of survival P is 1/3 (A hits) + 2/3*1/3*P (A misses, B misses, and we’re back to square one); P = 1/3 + (2/9)*P, (7/9)*P = 1/3, P = 3/7. If B shoots first, then A’s chance of survival is 1/3*P (B misses, and we’re back to the A-shoots-first case) = 1/7. We’ll hang on to these for later.
Now, suppose A misses with his first shot (whoever he aims at). Then with probability 2/3, B will kill C, and we’ll be at our A vs. B case with A shooting first. With probability 1/3, B will miss C; C will then kill B, and A has a 1/3 chance of killing C and surviving. So if A misses, the chances of his surviving are (2/3)*(3/7) + (1/3)*(1/3) = 2/7 + 1/9 = 25/63.
So suppose A chooses to shoot B. Then with probability 1/3 he succeeds, and immediately dies (because C shoots A as the only other survivor). With probability 2/3 he misses; this puts us in the situation that we just described, and his odds of survival there are 25/63. So his overall odds of survival if he aims at B are 2/3*25/63 = 50/189.
If A aims at C instead, then with probability 1/3 he succeeds, and we’re in the ‘A vs. B’ case with B having first shot (so A has a 1/7 chance of survival); with probability 2/3 he misses and we go back to the ‘after A misses’ case. So A’s total chances of survival here are 1/3*1/7 + 2/3*25/63 = 9/189 + 50/189 = 59/189.
But if A aims into the air and deliberately misses, then we know he has a 25/63 = 75/189 chance of surviving. So A’s best bet here, similar to the other outlined case, is to not shoot anyone! This gives him roughly a 8.5% better chance of surviving than if he shoots C.
30 August 2010, 3:07 pmSteveS:
Also, Numbers is usually at least a little better than this about their math; I’m surprised that they would be so sloppy here, especially since the ‘paradox’ is the most interesting part of the puzzle.
30 August 2010, 3:09 pmmisha:
I “real life” there would be a considerable chance of Connor freaking out and quickly shooting both of his opponents. Of course he would shoot Bob first.
30 August 2010, 10:38 pmcolorblind:
Marshall: “You know, I just realized an error in how I set up my problem. I should have said what is my strategy if we keep laying uyntil someone “wins”. Also, I said Colby was a dead shot. Why would I even consider shooting at him if he’s dead??? And while we’re at it Charlie, how’s about I shoot you and if I miss – I shoot you again and again until I kill you! You know, we mathematicians get caught up in the details when the solution is just cutting the proverbial Gordian knot!”
Charlie: “Well, I think there’s a few problems with that, and thanks for the gesture of friendship by the way. First, obviously you were speaking colloquially when you said Colby was a dead shot. He’s really alive, and deadly to boot. And second of all, you’re breaking a rule on how the problem is supposed to be set up. We take turns – you don’t get to keep going again and again until you win – you get ONE shot and then it’s my turn if I should be so fortunate as to be alive. Finally, I DO think you’re OK in how you phrased your question. Anyone who speaks English as a first language would be able to figure out it was implied the ONE shot was the ONE shot of THIS turn. I understand we need to be precise, but my brother Don and all the non-mathematicians for whom we are expounding already get the rules of the game.”
Colby: “Yeah, I’m not an idiot. And besides, I have a better solution. While Marshall is trying to aim the gun, I wrestle him to the ground, take his gun away, and scare the bejesus out of Charlie, causing him to pause while I shoot my gun.. It a 100% chance of me winning.”
Marshall: “Uh…yeahhhhh……”
8 September 2010, 12:07 amAnimesh:
I have seen many mistakes on the show. Stopped watching it after they made a mess of Riemann Hypothesis in one episode. That was terrible.
17 September 2010, 5:14 am(Daughter gets kidnapped…whose dad was working on Riemann Hypothesis)