Highlander was a series of fantasy movies and also a television series about certain people who have the luck to be immortal. An immortal can die only if his or her head is chopped off. Shots to the heart or brain or any other normally sensitive body part heal in seconds. As a result the immortals hone their sword-fighting skills with great care.

Each immortal acquires power by killing another immortal in a one-on-one duel. If immortal X with power P(X) fights immortal Y with power P(Y), then the winner will have, for purposes of this puzzle, power P(X) + P(Y). The loser, alas, dies.

As the series repeatedly reminded us, in the end “there can be only one” immortal left standing. In the series, some immortals provoke combat, others run from it, and the Scottish main character—the Highlander—accepts battle when it comes.

Suppose that you are an immortal. You want to find out your best prospects for survival. Should you pick fights or retreat from them? Do you prefer to fight stronger opponents or weaker ones? It all depends on winning probabilities.

We will consider two winning probability hypotheses. The "linear winning model" is the following:

If immortal X with power P(X) fights immortal Y with power P(Y), then X has probability P(X)/(P(X) + P(Y)) of winning and Y has P(Y)/(P(X) + P(Y)) probability of winning.

Warm-Up:

Suppose that there are three immortals X, Y and Z. X has power 2 and Y and Z each have power 1. If X duels and beats Y, then duels Z, what is the probability that X survives to the end? What would X's probability of surviving be if Y and Z first duel one another and then X duels the winner?

Solution to warm-up:

If X duels against Y, then X wins with probability 2/3 and acquires power 3. If X then duels against Z, then X wins that duel with probability 3/4. The probability that X survives both contests is the product of those two: (2/3) * (3/4) = 1/2.

If Y and Z duel first, then the winner has power 2. X has power 2 as well, so by symmetry, X wins with probability 1/2.

End of Warm-Up

In the warm-up, the order of dueling didn't affect X's chances of dueling. This result leads to our first question:

1. Assuming the linear winning model and up to 8 immortals, can you find a situation in which the order of duels does affect any given immortal's chances of surviving till the end?

So far we have assumed a linear winning model, but life for the immortals need not be so simple. Suppose the probability of winning is instead (P(X)2)/[(P(X)2) + (P(Y)2)]. We call this the quadratic winning model.

Warm-Up:

Let's reconsider our first warm-up problem but under the quadratic winning model.

Again, suppose that immortal X has power 2 and immortals Y and Z each have power 1. If X duels Y and, if he wins, then duels Z, what is the probability that X survives to the end? What would X's probability of surviving be if Y and Z first duel one another and then X duels the winner?

Solution to warm-up:

If X duels against Y, then X wins with probability 4/(4+1) and acquires power 3. If X then duels against Z, then X wins that duel with probability 9/10. The probability that X survives is the product of these two: (4/5) * (9/10) = 18/25.

If Y and Z duel first, then the winner has power 2. X has power 2 as well, so by symmetry, X wins with probability 1/2. Therefore, it's better for X to be more aggressive.

End of Warm-Up

All the remaining problems have to do with this quadratic model.

2. Four immortals all have equal power 1 initially, but three won't initiate a fight until they have fought and won once. Thereafter, they will initiate. One is willing to initiate a fight from the beginning. What chance does each immortal have of winning?

3. Again, there are four immortals, and three won't initiate a fight. The initiator has power 1 and the non-initiators have power 1, 2 and 4. In which order should the initiator fight the others to maximize his chances of surviving?

4. There are four immortals again but two will initiate a fight and two won't. If they all have the same initial power, then should the two initiators, in their own self-interest, start by fighting one another or start by fighting the non-initiators? (Try to answer this one before going on to Problem 5.)

5. We have seen that in the quadratic model it is better to initiate, better to fight other initiators first, and better to fight weaker opponents first. Which strategies take precedence assuming nobody fights more frequently than once per day?

People of course aren't immortal, but street gangs and countries transcend the lives of individual members. Is there a model here for police work or diplomacy?