9
$\begingroup$

Suppose there are n archers in a standoff and want to kill each other until there is just one archer remaining.

However everyone's chance of hitting (and thus killing) another archer is not fair. They are 1/n, 2/n, 3/n, ... n/n. Thus they decide to take turns and one may only shoot, if is determined, whether his arrow has killed someone or not.

The order is determine by the following: First they look, which archers are alive, then they look which of them has shot the least amount of arrows so far and if there are several of them, then they go after their chance of hitting another archer and always let a weaker archer shoot first. An archer (not the one with the highest chance of hitting one!) may be allowed to shoot into the air, not hitting and thus not killing anything.
It can be assumed, that every archer is sane and of course wants to survive.

Which archer has the highest chance of surviving? Which strategy should he use in order to maximize his success? (No hiding behind another archers and also no other loopholes) For starters one might go with n = 3;

$\endgroup$
  • $\begingroup$ The part "An archer may be allowed to shoot into the air" is the greatest hint here. =) Usually this kind of puzzle doesn't include that information. $\endgroup$ – justhalf Feb 3 '15 at 11:52
  • $\begingroup$ Why is the best archer not allowed to deliberately miss his shot? $\endgroup$ – ghosts_in_the_code Feb 3 '15 at 12:01
  • $\begingroup$ Also, try posting this on Stack Overflow. $\endgroup$ – ghosts_in_the_code Feb 3 '15 at 12:04
  • $\begingroup$ @ghosts_in_the_code: I want this game to terminate and I don't want all archers just keep shooting in the air. So it seemed reasonable to me to force the strongest archer to try taking out another archer. $\endgroup$ – Imago Feb 3 '15 at 13:06
  • $\begingroup$ @Imago 1) For a large n, it is not only the strongest archer who is so powerful, but the archers below him as well. For example, for n = 100, the difference in power of the top two archers is negligible. Such a rule may put the second best archer in a more powerful position than the 'best' one. 2) Once the top few archers are out, you could always have a game that takes thousands of shots to terminate. Your extra rule is not a problem, it only complicates matters. $\endgroup$ – ghosts_in_the_code Feb 3 '15 at 13:21
7
$\begingroup$

Solution for n = 3

The weakest archer (1/3 chance of killing) starts. If he aims at the medium archer (2/3), and happens to kill him, it is the strongest archer's turn next, and will kill him. Therefore, he will aim at the strongest archer. If he kills, he has about 1/9 chance of survival. If not, it is the medium archer's turn.

If the medium archer aims, and kills the weak one, the strongest will fire next and win. So he will aim at the strongest one. If he kills, he has about 1/2 chance of survival as. If not, it is the strongest one's turn.

The strongest archer will obviously increase his chance of survival by taking out the medium one. He has 2/3 chance of survival and the weakest 1/3.

Wasting shots

Coming back to the medium archer's option to waste his shot, the strongest archer will anyway kill him, so that option's out.

If the weakest one chooses to waste his shot, he will at least reach the top 2 (the other 2 will still aim at each other), and it will be his turn to fire, giving him a minimum survival chance of 1/3.

The strongest one gains nothing by wasting his shot.

Conclusion

Optimal strategy for first shot, if you are:
a) Weakest archer - Waste the shot.
b) Medium archer - Aim for the strongest one
c) Strongest archer - Kill the medium one

After up to 3 arrows shot, someone will end up dead, so you need to aim every shot at the remaining opponent.

Approach to solve n = 4

This is the basic outline for how it should be solved, some higher level maths will be necessary.

Let a to d be the archers, weakest to strongest.

Fact 1: One who misses a shot is as good as wasting it.

Fact 2: Top 2 archers always duel against each other (as best archer will always take out the next best).

  • Case 1: a kills b. c and d duel. a duels with winner of c and d.

  • Case 2: a kills c. b and d duel. a duels with winner of b and d.

  • Case 3: a kills d. b and c duel. a wastes shots till b or c is killed, a duels with winner.

  • Case 4: a wastes his shot, or chooses to waste it. Write 4 cases for b's decisions, like a. 4th case for b (waste/miss) will be as follows. c will necessarily kill d, else get killed by d. If a, b and c are left, a wastes shots till b and c's duel is over, then duels with the winner. Similarly for if a, b and d are left.

Then you need to calculate the probability of each of the archers surviving each of these cases, and each archer should take the case with greatest chance of survival.

$\endgroup$
  • $\begingroup$ What's the strategy for n = 4? $\endgroup$ – warspyking Feb 3 '15 at 20:27
  • $\begingroup$ @warspyking It gets very complicated when done on paper, also it requires you to calculate some probabilities, which I don't know how to. The basic strategy is that there are about 10-15 different ways a person dies on the first round of shooting, and survival probabilities have to be calculated for each person, for each of the cases. Also, as Imago pointed out, I suppose there is no generalization for $n$ and writing a program would be the best approach. $\endgroup$ – ghosts_in_the_code Feb 5 '15 at 14:58
  • $\begingroup$ @ghosts_in_the_code I wrote a program, but I need to write the strategy. Since adopting a strategy for one player affects the others, it is difficult to optimize. In the 4 person game, there are 4 strategies for each player - shoot one of the 3 or waste your shot. You'd need to see which strategy is the best for each player and then make your own strategy based on that. For example, if player 1's best strategy is to shoot player 2, maybe player 2's strategy should be to shoot player 1. But this may affect player 1's strategy, which then affects player 2.... $\endgroup$ – Trenin Feb 5 '15 at 15:10
  • $\begingroup$ @Trenin I've given the basic approach. You are right in saying that player 2's strategy in turn affects strategy for player 1, but this will happen only in the next round of firing, by when at least one archer will be dead, and strategies will completely change. You have to calculate probabilities for each player, for each case, and add them to see what the best move is in the previous round of firing. Doing this for all the players lets you calculate the round before that, and so on. $\endgroup$ – ghosts_in_the_code Feb 5 '15 at 15:40
  • $\begingroup$ @ghosts_in_the_code Lets say that my best strategy is to target $A$. Given that I am going to target $A$, your best strategy might be to target me. But if you are targeting me, then my best strategy is to target you. If I am targeting you, then perhaps your best strategy is target something else, leaving me back with my original strategy. So, it is not always dependent on the previous round, but rather what I expect the others will be doing this round. $\endgroup$ – Trenin Feb 5 '15 at 16:03
5
$\begingroup$

Let the archers be numbered $a_1, a_2, ... a_n$.

Let $p_i$ be the probability of archer $i$ making a shot.

Let $P_n(j, S)$ be the probability of archer $a_j$ winning out of the ordered set $S=\{i, ..., j, ... k\}$ with an initial size of $n$ where $a_j$ goes first.

General solution for $n=2$

For the following, we will compute a formula for 2 archers.

Lets say that we have two archers remaining, $a_i$ and $a_j$ and $a_i$ is to shoot first. To win, he can either kill $a_j$ on the first shot (happens with probability $p_i$), or if he misses (probability $1-p_i$) and survives the attempt by $a_j$ (probability $1-p_j$), then he can try again. This gives the following recursive formula:

$$P_n(i, \{i,j\}) = p_i + (1-p_i)(1-p_j)P(i,\{i,j\})$$ $$P_n(i, \{i,j\}) = \frac{p_i}{1-(1-p_i)(1-p_j)}$$

Since $p_k=\frac{k}{n}$, we can reduce this further.

$$P_n(i, \{i,j\}) = \frac{\frac{i}{n}}{1-(1-\frac{i}{n})(1-\frac{j}{n})} = \frac{i}{n \left( 1-\left( \frac{n-i}{n}\right) \left( \frac{n-j}{n} \right) \right)} = \frac{i}{\frac{n^2-(n(i+j)+ij)}{n}} = \frac{in}{ni+nj-ij}$$

Solution for $n=3$

As posted by @ghosts_in_the_code, there is a strategy for this scenario. When implemented, the following are the chances for survival.

Archer $a_3$

The first archer $a_1$ wastes his shot, and $a_2$ will aim at $a_3$. If he hits, then $a_3$ loses, but if he misses, then $a_3$ kills $a_2$ and must survive an attempt by $a_1$ to win. So, $a_3$ wins if both $a_2$ and $a_1$ miss.

$$P_3(3, \{1,2,3\})=(1-p_2)(1-p_1)=\frac{2}{9}$$

Archer $a_2$

The second archer will lose if he misses on his first shot at $a_3$ since $a_3$ will surely target him and kill him on his turn. Thus, $a_2$ must first kill $a_3$, and then survive $a_1$'s attempt. Then his chances are given in the formula above.

$$P_3(2, \{1,2,3\}) = p_2 \times (1-p_1) \times P_3(2, \{1, 2\}) = \frac{2}{3}\times \frac{2}{3}\times \frac{2 \times 3}{3 \times 2 + 3 \times 1 - 2 \times 1} = \frac{8 \times 3}{3 \times 3 \times (6+3-2)} = \frac{8}{21}$$

Archer $a_1$

The first archer can win in two ways:

  1. If $a_2$ kills $a_3$ ($p_2$) and then $a_1$ outlasts $a_2$ (formula above).
  2. If $a_3$ kills $a_2$ ($1- p_2$) and then $a_1$ hits $a_3$ on the first attempt ($p_1$). There will be only one attempt!

Using the formula we worked out before, we get the following:

$$P(1, \{1,2,3\}) = p_2 \times P_3(1, \{1, 2\}) + (1-p_2) \times p_1 = \frac{2}{3} \times \frac{3\times 1}{3 \times 1+ 3 \times 2 - 2 \times 1} + \left( 1-\frac{2}{3} \right) \times \frac{1}{3} = \frac{2}{7} + \frac{1}{9} = \frac{25}{63}$$

Summary

All these should add up to $1$, and they do.

$$\frac{25}{63} + \frac{8}{21} + \frac{2}{9} = \frac{25 + (3 \times 8) + (7 \times 2)}{63} = \frac{25 + 24 + 14}{63} = \frac{63}{63} = 1$$

Thus, somewhat counter-intuitively, the best archer has the worst chance of survival, and the worst archer has the best chance.

General Solution for $n=3$

We've done the specific solution for $a_1, a_2, a_3$, but what about for $a_i, a_j, a_k$? It is no longer obvious that the lowest archer shoot intentionally miss. For example, say $a_i$ and $a_j$ are equally dismal shots and $a_k$ is perfect. If $a_i$ wastes the shot and $a_j$ misses $a_k$, then $a_k$ will take out $a_j$. That leaves $a_i$ one shot to kill $a_k$. Thus, $a_i$'s chance of winning is $1-p_i$. If $a_j$ hits $a_k$ instead, then it is a duel between roughly equal players and $a_i$ has about a 50% chance.

Instead if $a_i$ aims for $a_k$ and hits, then although $a_j$ goes first in the duel, the chances are still pretty equal - much better than duelling $a_k$.

Thus, in this case, it is obvious that $a_i$ should shoot for $a_k$.

Thus we need to explore 2 strategies - one where the weakest wastes the shot, and the other where the weakest targets the strongest.

Weakest Targets Strongest

For the strongest to win, he needs to survive the first two shots. Then he will target $a_j$. If he is successful, then it is a two person game (and we have the general solution for that). If he fails, then it is the same probability as before.

$$P_n(k, \{i,j,k\}) = (1-p_i)(1-p_j)\Big( p_k \times P_n(k, \{i,k\}) + (1-p_k) \times P(k, \{i,j,k\}) \Big) = \left(1-\frac{i}{n} \right) \left( 1-\frac{j}{n} \right) \left( \frac{k}{n} \times \frac{nk}{nk+ni-ik} + \left( 1-\frac{k}{n} \right) \times P(k, \{i,j,k\}) \right) $$

Solving this is rather tricky, and doesn't have a nice closed form that I can see.

So, for now, I am giving up on this. Perhaps we can come back to it later, but I think I am taking the wrong approach.

$\endgroup$
1
$\begingroup$

The optimum strategy is for the top 2 archers to duel, the next one to shoot down, then the rest to shoot for the strongest.

If you have 3 archers, the weakest wants to miss and let the top 2 kill each other, then try to snipe the survivor.

If you have 4 archers, the 2nd weakest will try to kill the weakest, since the top 2 archers are focused on each other, and if you kill either of them, the survivor will try to kill you. And the weakest will actually try to kill the strongest, since that puts him back into the 3 archer scenario. He could just try to kill the 2nd weakest, but that would ultimately leave a stronger archer to 1-on-1.

If you have 5 archers, the two weakest would go for the top, the middle would go for 2nd weakest, then the top 2 would duel, as usual.

Edit:

So, I've been thinking about how to deal with this issue when you have many archers (say, 100). It's actually not in the top archer's best interest to kill each other first, since there are so many people gunning for them. Which got me thinking about how the categories of archers really played out.

  • The top archers, who everyone is gunning for.
  • The good archers, who have a good chance against the top, but eventually could become the top that everyone else is gunning for.
  • The mediocre archers, who won't get to the top any time soon, so can gun for whoever.
  • The bad archers, who through weight of numbers can bring down a good archer.

Now, the good archers and the top archers have an interesting predicament. The good archers could probably take out at least half of the top archers, but then the remaining top archers would take out a lot of the good ones, less how many top archers were killed by the lower archers.

If instead the good archers shot into the mediocre ones, the top ones could shoot into the good ones, but then they'd be eliminated the next wave (likely). But if they also shot into the mediocre ones, that group would be fairly weakened, leaving bad archers to hit good/top and good/top to hit mediocre/bad.

This scenario would end up with the good archers in the best position, since they really haven't been targeted as much as the top/bottom.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.