Two gladiators are about to do battle in the coliseum. Before the battle, they enter separate rooms and pray to Ares, the god of war. Ares blesses them each with random amount of power, which you can think of as a real number between $0$ and $1$. If the gladiators are unsatisfied with their blessing, then they may pray at most one more time, receiving a new amount of power which replaces the old one. They then fight, and the gladiator with the greatest blessing wins.

How can a gladiator guarantee that they win with probability at least $1/2$?

The reason I like this puzzle is because there is one strategy which is "obviously correct:" namely, pray again if your first blessing is less than $0.5$. Surprisingly, there are strategies which beat this more than half the time. As a warning, this is a bit more computation-heavy than your average clever math puzzle.

  • $\begingroup$ Just for clarification, the random amount of power is uniformly distributed between 0 and 1, and each blessing is independent? $\endgroup$ – Glen O Apr 29 '15 at 4:02
  • $\begingroup$ @GlenO Good questions: the blessings are indeed uniform and independent. $\endgroup$ – Mike Earnest Apr 29 '15 at 4:05
  • 3
    $\begingroup$ Ares is Greek god of war. If they are battling in the coliseum, they would be praying to Mars. $\endgroup$ – Zikato Apr 29 '15 at 5:36
  • 1
    $\begingroup$ @Zikato, they are obviously Greek soldiers captured by the Roman army and forced to do battle against each other. $\endgroup$ – Ian MacDonald Apr 29 '15 at 14:00

The answer is that the gladiator should pray for another blessing if their blessing is below $1/\phi$ where $\phi$ is the golden ratio.

Suppose that the gladiator prays for a new blessing if the blessing they received were less than $x_n$, where $n$ is the identifier for the specific gladiator. We need to find the value of $x_1$ that ensures that the probability of having a higher blessing than gladiator 2 is always at least $\frac12$.

It is easy enough to find the distribution for each gladiator. The probability density for each gladiator is given by $$ p_n(x) = \begin{cases}x_n & x<x_n\\ 1+x_n \qquad& \text{otherwise}\end{cases} $$ Now, we seek $Pr(X_1\geq X_2)$ where $X_n$ is distributed according to $p_n(x)$. We can do this (because they are independent) by seeking $$ Pr(X_1\geq X_2)=\int_0^1 Pr(X_1\geq X_2=x) dx = \int_0^1 Pr(X_1\geq x)p_2(x)dx $$ Now, $$ Pr(X_1\geq x) = \int_x^1 p_1(y)dy = \begin{cases} 1-x_1x & x<x_1 \\ (1-x)(1+x_1)\qquad & \text{otherwise} \end{cases} $$ and so we have $$ Pr(X_1\geq X_2)=\begin{cases}\frac{(x_2-x_1)(x_1x_2+x_2-1)+1}2 & x_1<x_2 \\ \frac{(x_2-x_1)(x_1x_2+x_1-1)+1}2 & x_1\geq x_2\end{cases} \tag{1} $$ Evaluating the derivative with respect to $x_1$, we have $$ 0 = \frac{\partial}{\partial x}Pr(X_1\geq X_2)=\begin{cases}\frac{x_2^2-2x_1x_2-x_2+1}2 & x_1<x_2 \\ \frac{x_2^2-2x_1x_2+x_2-2x_1+1}2 & x_1\geq x_2\end{cases} $$ Solving these gives $$ x_1 = \begin{cases} \frac{x_2^2-x_2+1}{2x_2} & x_1<x_2 \\ \frac{x_2^2+x_2+1}{2x_2+2} \qquad & x_1\geq x_2\end{cases} $$ These intersect where $x_1=x_2=\frac12(\sqrt{5}-1)$. All that remains is to show that this guarantees at least $\frac12$ chance of winning. We substitute it into (1) to get $$ Pr(X_1\geq X_2)=\begin{cases}\frac{(\sqrt5+1)x_2^2-4x_2+\sqrt5+1}4 & x_2>\frac12(\sqrt{5}-1) \\ \frac{(\sqrt5-1)x_2^2+(2\sqrt5-6)x_2+2\sqrt5-2}4 & x_2\leq \frac12(\sqrt{5}-1)\end{cases} $$ And it can easily be seen that both cases remain above 0.5.

| improve this answer | |

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.