Project Euler Problem 887

Solution

Answer: 39896187138661622

Let $M(q,d)$ denote the maximum $N$ such that there exists a strategy using at most $q$ questions and satisfying

$$\text{questions needed for }x \le x+d.$$

Then

$$Q(N,d)=\min{q : M(q,d)\ge N}.$$

We derive the recurrence for $M(q,d)$.

Suppose the first question is “Is the secret number greater than $y$?”

If the answer is no, the secret lies in ${1,\dots,y}$.

One question has already been used, so the remaining allowance becomes

$$(x+d)-1=x+(d-1),$$

hence the left subtree can contain at most

$$M(q-1,d-1)$$

numbers.

If the answer is yes, write the secret as $x=y+z$ where $z\ge1$.

The remaining allowance is

$$(y+z+d)-1=z+(d+y-1),$$

so the right subtree can contain at most

$$M(q-1,d+y-1)$$

numbers.

The optimal choice is $y=M(q-1,d-1)$, giving

$$M(q,d)=M(q-1,d-1)+M!\left(q-1,d+M(q-1,d-1)-1\right),$$

with base cases

$$M(q,-1)=1,\qquad M(0,d)=1.$$

This recurrence reproduces the examples:

$M(3,1)=7$, hence $Q(7,1)=3$.
$M(10,2)=777$, hence $Q(777,2)=10$.

For each $d=0,\dots,7$, we compute the increasing sequence $M(q,d)$ until it exceeds

$$7^{10}=282475249,$$

and then sum

$$\sum_{N=1}^{7^{10}} Q(N,d) = \sum_q q\cdot\bigl(M(q,d)-M(q-1,d)\bigr).$$

The resulting values are:

$$\begin{aligned} d=0 &: 39896133007568376\ d=1 &: 7937386123\ d=2 &: 7789128659\ d=3 &: 7722019822\ d=4 &: 7688465416\ d=5 &: 7671688225\ d=6 &: 7663299641\ d=7 &: 7659105360. \end{aligned}$$

Adding them all gives

$$39896187138661622.$$

Answer: 39896187138661622