1
$\begingroup$

I came up with this problem on my own, and I can't figure out how to solve it.

You are a hero fighting an evil overlord. At the beginning of these events, you have 0% chance of defeating the overlord in a fight. You take one day to train, and at the end, you have a 10% chance of defeating the overlord in a fight. However, the night of the first day, there is a one in ten chance that the overlord will take over the world, and then it will be too late to stop him. On the second day, you can either go to fight the overlord, or train some more. At the end of the second day, you now have a 20% chance of defeating the overlord in a fight. However, if you fight the overlord, and lose, then there will be no one left to oppose him, and the world is lost. The night of the second day, there is another one in ten chance of the overlord taking over the world. Every day that you train, your chances of defeating the overlord become 10% better. However, you also run the risk of him taking over the world every night. What is the best number of days to train before fighting the overlord?

I'm trying to solve this without using a decision tree. The only thing I came up with was using an equation, like this: Y = (9/10)x * (1/10) * x

But I don't think that it was right, because it said the 9th and 10th days were the best, as they were identical to the decimal extent of my graphing calculator, at approximately a 35% chance for each. I don't think the solution should go beyond the 10th day, as there is a 100% theoretical probability that asking for a single 1/10 chance to succeed in ten tries.

Thank you now for your time, and in advance for your words.

$\endgroup$
2
$\begingroup$

There's no useful information to be gained over time, so you can decide at the outset how long to train and when to go to fight.

If you train for $k$ days, you'll get a chance to fight with probability $\left(\frac9{10}\right)^k$, and you'll win with probability $\frac k{10}$, so your probability of saving the world is $\frac k{10}\left(\frac9{10}\right)^k$. The ratio of these probabilities for two successive numbers $k$ and $k+1$ of days of training is $\frac{k+1}k\frac9{10}$. This is greater than $1$ for all $k\lt9$, and equal to $1$ for $k=9$. Thus, your calculation was correct; you should train for $9$ or $10$ days, with the same $\left(\frac9{10}\right)^{10}\approx35\%$ chance of saving the world.

Perhaps you find this counterintuitive because you feel that you're giving the overlord all these chances to take over the world and there must be some earlier point at which you're already somewhat trained where you can prevent some of those chances. But the training is more valuable, since it increases your chances by a factor $\frac{k+1}k$, whereas the night only reduces them by a factor $\frac9{10}$.

Yoda, of course, knew this.

$\endgroup$
1
$\begingroup$

So the probability of being victorious if the hero plans to fight the overlord after training $N$ days is equal to the probability that the overlord does not take over the world during the training days times the probability for winning given $N$ days of training.   The overlord has a probability of $0.9$ for not taking over the world at the end of each day, and the hero accumulates a probability of $0.1N$ for winning on day $N$.   Because of this accumulation, we do not need to consider more than the tenth day.

$$\begin{align}\mathsf P(V\mid N{=}x) ~=&~ \mathsf P(T^\complement)^{x}\mathsf P(W\mid N{=}x)\\ y~=&~ (0.9)^{x}(0.1x)\end{align} $$

To find the day giving the maximum probability of victory, we take the derivative and set to zero, then solve for $x$ (to the nearest integer value).

$$0=\tfrac {9^{x}}{10^{x+1}}(1-x\ln\tfrac{10}{9})\\ x=\frac 1{\ln\tfrac {10}9}\\ x\approx 9.5$$

Now $\mathsf P(V\mid N=9) = 0.9^9(0.9)$ and $\mathsf P(V\mid N=10)=0.9^{10}$, so indeed the best day to plan to attack is either day $9$ or day $10$ with a probability of $0.3486784401$ for victory.

$\endgroup$
0
$\begingroup$

The probability that the world is safe if you wait $k$ days is $$ P(k)=\underbrace{\left(\frac9{10}\right)^k}_{\substack{\text{overlord does}\\\text{not take over}\\\text{the world}}}\underbrace{\ \ \min\left(\frac{k}{10},1\right)}_{\substack{\text{you defeat}\\\text{the overlord}}} $$ enter image description here

For $k\lt10$, the equation $$ \frac{P(k+1)}{P(k)}=\frac9{10}\frac{k+1}{k} $$ shows that $P(9)=P(10)$. For $k\gt10$, you can only have a $100\%$ chance of winning, so $P(k)=\left(\frac9{10}\right)^k$. That is, the probability that the world is safe is the same whether you attack the overlord after $9$ days or after $10$ days. After that, the probability dwindles.

$\endgroup$
  • $\begingroup$ What tool did you use to produce this graph? $\endgroup$ – Siris Jun 8 '16 at 17:01
  • $\begingroup$ The plot was generated with Mathematica 8. $\endgroup$ – robjohn Jun 8 '16 at 18:39

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.