Problem 12 Solution - "Energy Crisis"

Problem 12.1.

Let f(x) be the probability of success starting from x mana.

If x=0, we have already lost, so f(0)=0.
If x=y, we have already won, so f(y)=1.
If x is between 0 and y, then after this step there is a 1/2 chance that the player will be at x+1 mana and a 1/2 chance he will be at x-1 mana. Therefore, f(x) = (1/2)(f(x+1)) + (1/2)(f(x-1)).

Now suppose f(1) = A. Setting x=1 in the formula and solving for f(2) gives f(2)=2A (since f(0)=0). Similarly, setting x=2 in the formula and using the newly calculated values of f(1) and f(2) gives f(3)=3A, etc., so f(x)=xA. Since f(y)=1 we must have A=1/y, and thus f(x) = x/y. Therefore, the probability of success starting from X mana is X/Y.

Problem 12.2.

The solution is similar to the problem above, except that f(x) = (3/4)f(x+1)) + (1/4)(f(x-1)). If we set f(1)=A, we get f(2) = (1 + 1/3)A, f(3) = (1 + 1/3 + 1/9) A, f(4) = (1 + 1/3 + 1/9 + 1/27) A, and so on. As x approaches infinity, f(x) approaches 3A/2. Since we know f(1,000,000)=1, and by the preceding f(1,000,000) is approximately 3A/2, we have A=2/3. Thus the probability of success is approximately 2/3.