14
$\begingroup$

There are $n$ archers competing in an archery contest. The rules:

  • Each archer will shoot exactly one arrow at the target.
  • The archers will shoot one at a time, with the order of turns chosen at random.
  • On an archer's turn, he or she may choose how far from the target to stand while shooting. Of course, standing farther away makes it harder to hit the target.
  • After all the shots are taken, the archer who hit the target from the farthest away is declared the winner. Ties are broken in favor of the archer who shot later.

This contest is not fair, as shooting later is a significant advantage.

The archers are all equally skilled, and an archer shooting from $d$ meters away will hit the target with probability $\frac{10}{d}$. The minimum allowed distance is 10 meters.
(The specific expression for probability as a function of distance is not so important. Essentially each archer in turn chooses a probability, and among the archers who hit the target, the one who chose the lowest probability is the winner.)

Suppose you are the $k$-th archer to shoot. How far from the target should you stand to maximize your likelihood of winning? Assume every other archer will act optimally to maximize their chance of winning.

Bonus: As $n\to\infty$, what is the probability that the winner took their shot during the first half of the contest?

$\endgroup$
  • $\begingroup$ So if d = 1, then there is a probability of 10? Therefore, d>10 at all times? $\endgroup$ – the4seasons Jun 14 '15 at 4:41
  • $\begingroup$ Yeah, this only makes sense if $d\geq 10$ so I should require this. $\endgroup$ – Julian Rosen Jun 14 '15 at 15:00
13
$\begingroup$

Main Puzzle

I'll assume that every archer expects the others to play optimally (this was implied in the bonus question, but I'll use it here too).

There are only two pieces of information that could influence what shot an archer decides to take:

  • the probability $b$ (for "best") that was chosen by the archer currently winning or $1$ if no one has hit yet (relevant because one cannot win taking a shot with probability above $b$) and
  • the number of competitors $r$ (for "remaining") to shoot after the archer (relevant because later contestants may snatch one's victory away).

So we can write the optimal probability to choose for one's shot as a function $p$ of just $b$ and $r$.

First, suppose $r=0$. Obviously, the archer should take the easiest shot available, so we have $p(b,0)=b$. For the moment, I will note that this is equivalent to $p(b,0)=\min(b,1)$.

Now take $r=1$. We need to maximize the current archer's chances of winning, $p(b,1)$, for their shot being made, times $1-p(p(b,1),0)$ for the last archer not stealing the win. The maximum of $x(1-x)$ over the interval $[0,b]$ is achieved at $x=\min(b,1/2)$, so $p(b,1)=\min(b,1/2)$.

A similar argument for $r=2$ has us maximizing $x(1-\min(x,1/2))(1-x)$ over the interval $[0,b]$. Having the $\min$ in the $1-\min(x,1/2)$ factor choose $x$ is obviously better and occurs at lower $x$ anyway, so we can equivalently maximize $x(1-x)^2$. This gives $p(b,2)=\min(b,1/3)$.

By now you can probably see the pattern: We maximize the product of one success and $r$ subsequent failures over $[0,b]$, which is equivalent—because we want all the negative mins to be small—to maximizing $x(1-x)^r$. So, in general, $p(b,r)=\min(b,1/(r+1))$.

This gives us an answer to the main question, which depends, via $b$, on how prior archers have fared:

$$d=\frac{10}{p(b,r)}=\frac{10}{\min(b,\frac{1}{n-k+1})}.$$

Or, in plain language: An archer should shoot either from a distance where they expect exactly one of the as-yet-unfired shots (hopefully their own) to hit or from the distance of the currently winning shot, whichever is further.

That makes this puzzle pretty nifty in my opinion: the result is what my intuition would like it to be, but the justification is nontrivial.


Bonus

The probability of everyone in the latter half missing is $(1-b)^{n/2}$, where $b$ is established by the first archer to hit: $1/(n-i+1)$ when the $i^{\mathrm{th}}$ archer is first. Because of the problem wording, we only care about cases where some archer in the first half scored a hit, and these cases are disjoint, so we can sum over them.

Thus, we must determine the probability of the $i^{\mathrm{th}}$ archer scoring the first hit. It is the product of the probabilities of prior archers missing, which telescopes to $(n-i+1)/n$, times the probability that the archer themself hits, $1/(n-i+1)$. In other words, just $1/n$.

(As an aside, that too is a pretty cool result: As long as these archers play optimally, we can dupe them into a fair contest by claiming the rules above but then actually awarding the victory to the first hit.)

We substitute into the sum and take the limit:

\begin{align*}\lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^{n/2}\left(1-\frac{1}{n-i+1}\right)^{n/2}&= \lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^{n/2} \left(\left(1-\frac{1}{n-i+1}\right)^{n-i+1}\right)^{\frac{1}{2\left(1-\frac{i-1}{n}\right)}}\\& = \lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^{n/2} e^{\frac{-1}{2\left(1-\frac{i-1}{n}\right)}}\\& = \int_0^{1/2} e^{\frac{-1}{2(1-t)}}\,dt = \frac{1}{2}\int_{1}^2 e^{-1/t}\,dt\\ &\approx 0.252396. \end{align*}

There's slightly better than a quarter chance of the winner having taken their shot during the first half of the contest.

$\endgroup$
  • 1
    $\begingroup$ Regarding assumption 2: if the first $n-1$ archers have missed the target, the $n$-th archer can stand 10 meters from the target to ensure hitting it. So in practice it should never happen that nobody hits the target. $\endgroup$ – Julian Rosen Jun 14 '15 at 17:18
  • $\begingroup$ @JulianRosen Ah. Of course. That was silly of me. I will drop the assumption. $\endgroup$ – Edward Jun 14 '15 at 17:21
1
$\begingroup$

Every archer must use the first applicable rule:

  1. Shoot from the greatest distance of a successful shot, if there was at least one succesful shot.

  2. Shoot from distance less than or equal to $10$, if shooting last.

  3. Shoot from distance greater than $10$.

Note that to win it is required not only to hit the target from farthest distance, but all subsequent shots to fail. There is no way, by choosing the shooting distance, for archer to ensure that own shot is less likely to miss than any of subsequent shots to hit - thus it is impossible to detrmine best shooting distance: if $P$ is a probability to hit the target from a given distance, than a chance to win for a $k_{\text{th}}$ archer would be $P \times \big((1-P)^{5-k}\big)$, but for $(k+i)_{\text{th}}$ archer it would be $P \times \big((1-P)^{5-(k+i)}\big)$, which is greater.

On bonus:
The problem, in general, is to determine the probability $P_n^k$ that one of the first $n$ archers wins - that is, any (or all) of first $n$ archers hit the target (which is inverse to probability that all first $n$ archers miss) while last $k-n$ archers miss. Again, given $P$ as probability of an archer to hit target from a given distance, $P_n^k$ would be: $$P_n^k=\big(1-(1-P)^n\big)\times (1-P)^{k-n}$$ or $$P_n^k=(1-P)^{k-n}-(1-P)^k$$ or $$P_n^k=\frac{1}{(1-P)^n}-1$$ or, finally $$P_n^k=\frac{1}{(1-10/x)^n}-1$$

$\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.