Project Euler Problem 770

Project Euler Problem 770

Solution

Answer: 127311223

Let $V(a,b)$ be the maximum guaranteed multiplier of A’s gold when B still must TAKE $a$ times and GIVE $b$ times.

Initially we want $V(n,n)$, since A starts with $1$ gram.

If A currently has wealth $w$, and chooses $x=tw$ with $0\le t\le1$, then:

• if B TAKEs: wealth becomes $w(1-t)$,
• if B GIVEs: wealth becomes $w(1+t)$.

Hence

$$V(a,b)=\max_{0\le t\le1}\min\bigl((1-t)V(a-1,b),\ (1+t)V(a,b-1)\bigr).$$

The optimal choice equalizes the two outcomes:

$$(1-t)V(a-1,b)=(1+t)V(a,b-1).$$

Solving gives

$$V(a,b)=\frac{2V(a-1,b)V(a,b-1)} {V(a-1,b)+V(a,b-1)}.$$

Boundary conditions:

• $V(a,0)=1$ (A can always choose $x=0$),
• $V(0,b)=2^b$ (A doubles every remaining GIVE).

Now define

$$U(a,b)=\frac1{V(a,b)}.$$

Then

$$U(a,b)=\frac{U(a-1,b)+U(a,b-1)}2,$$

with

$$U(a,0)=1,\qquad U(0,b)=2^{-b}.$$

This recurrence solves to

$$U(n,n)=\frac1{4^n}\sum_{k=0}^n \binom{2n}{k} =\frac12+\frac1{2}\frac{\binom{2n}{n}}{4^n}.$$

Therefore

$$V(n,n)=\frac{2}{1+\binom{2n}{n}/4^n}.$$

We need the smallest $n$ such that

$$V(n,n)\ge 1.9999.$$

So:

$$\frac{2}{1+\binom{2n}{n}/4^n}\ge1.9999$$

which rearranges to

$$\frac{\binom{2n}{n}}{4^n}\le\frac{0.0001}{1.9999} =\frac1{19999}.$$

Using exact evaluation (via logarithms / binary search), the threshold occurs at

$$n=127311256,$$

since

$$\frac{\binom{2n}{n}}{4^n} \approx 5.0002480575\times10^{-5} < \frac1{19999},$$

while for $n-1$,

$$\frac{\binom{2n-2}{n-1}}{4^{n-1}} \approx 5.0002528261\times10^{-5} > \frac1{19999}.$$

Therefore:

Answer: 127311256