Detailed mathematical approach

Problem Summary

For positive real costs \(a\) and \(b\), let \(C(n,a,b)\) denote the smallest budget \(c\) that guarantees success in an ordered guessing game with at least \(n\) candidates: after each guess, one non-equal answer consumes cost \(a\) and the other consumes cost \(b\). In Problem 406 we must evaluate

$\sum_{k=1}^{30} C\!\left(10^{12},\sqrt{k},\sqrt{F_k}\right),\qquad F_1=F_2=1,\quad F_k=F_{k-1}+F_{k-2}.$

A direct search over strategies is hopeless, so the solution converts the game into a lattice dynamic program that counts how many ordered candidates a fixed budget can handle.

Mathematical Approach

Define \(K(c,a,b)\) as the largest number of ordered candidates that can always be distinguished with total cost at most \(c\). Once \(K\) is known, the desired threshold value is

$C(n,a,b)=\inf\{c\ge 0: K(c,a,b)\ge n\}.$

The implementation therefore solves two subproblems: compute \(K(c,a,b)\) for a fixed budget, then binary-search the smallest \(c\) for which \(K(c,a,b)\) reaches the target \(n\).

Step 1: State Space Under a Fixed Budget

Suppose that along the current path of the decision tree we have already seen \(i\) answers of the first type and \(j\) answers of the second type. The spent cost is then

$ia+jb.$

Such a state is still usable exactly when

$ia+jb\le c.$

This gives the finite feasible lattice region

$\mathcal{R}_c=\{(i,j)\in \mathbb{Z}_{\ge 0}^2: ia+jb\le c\}.$

Now let \(D_c(i,j)\) be the maximum number of ordered candidates that can still be resolved from state \((i,j)\). Outside the feasible region there is no remaining budget, so

$D_c(i,j)=0,\qquad (i,j)\notin \mathcal{R}_c.$

Step 2: Exact Counting Recurrence

At a feasible state \((i,j)\), the next guess picks one pivot candidate. That pivot itself contributes one distinguishable value. If the hidden value falls on the \(a\)-cost branch, the next state becomes \((i+1,j)\); if it falls on the \(b\)-cost branch, the next state becomes \((i,j+1)\).

Therefore every strategy rooted at \((i,j)\) can distinguish at most

$1+D_c(i+1,j)+D_c(i,j+1)$

candidates.

Conversely, if the left continuation can handle \(L=D_c(i+1,j)\) candidates and the right continuation can handle \(R=D_c(i,j+1)\) candidates, then an ordered block of length \(L+1+R\) can be handled exactly: guess the \((L+1)\)-st candidate, use the left strategy on the lower block, and the right strategy on the upper block.

Hence the upper bound is attainable, so the recurrence is exact:

$D_c(i,j)= \begin{cases} 1+D_c(i+1,j)+D_c(i,j+1), & ia+jb\le c,\\ 0, & ia+jb>c. \end{cases}$

The quantity needed by the outer search is simply

$K(c,a,b)=D_c(0,0).$

Step 3: Worked Example

The checkpoint \(C(5,2,3)=5\) illustrates the mechanism well.

For \(c=4\), the feasible states are \((0,0),(1,0),(2,0),(0,1)\). Working backward gives

$D_4(2,0)=1,\qquad D_4(1,0)=2,\qquad D_4(0,1)=1,\qquad D_4(0,0)=4.$

So a budget of \(4\) can guarantee only \(K(4,2,3)=4\) candidates.

For \(c=5\), the extra feasible state \((1,1)\) appears, and now

$D_5(2,0)=1,\qquad D_5(1,1)=1,\qquad D_5(1,0)=3,\qquad D_5(0,1)=2,\qquad D_5(0,0)=6.$

Thus \(K(5,2,3)=6\ge 5\). Since \(4\) is insufficient and \(5\) is sufficient, we obtain

$C(5,2,3)=5.$

Step 4: Monotonicity and Binary Search

If \(c_1\le c_2\), then \(\mathcal{R}_{c_1}\subseteq \mathcal{R}_{c_2}\). Every state available with budget \(c_1\) is also available with budget \(c_2\), so

$K(c_1,a,b)\le K(c_2,a,b).$

That monotonicity makes \(C(n,a,b)\) a standard “binary search on the answer” problem. The implementation first doubles an upper bound \(1,2,4,8,\dots\) until the capacity reaches \(n\), and then performs 90 bisection steps to isolate the minimal sufficient budget to high precision.

Step 5: Final Aggregation Over Fibonacci Pairs

After computing the Fibonacci numbers \(F_1,\dots,F_{30}\), the algorithm forms the 30 parameter pairs

$\left(\sqrt{k},\sqrt{F_k}\right)\qquad (1\le k\le 30).$

For each pair it computes the threshold budget \(C\!\left(10^{12},\sqrt{k},\sqrt{F_k}\right)\), then sums all 30 values. The mathematical burden is therefore concentrated entirely in evaluating the capacity function \(K(c,a,b)\) efficiently.

How the Code Works

For one fixed budget \(c\), the implementation sets

$i_{\max}=\left\lfloor \frac{c}{a}\right\rfloor,\qquad j_{\max}=\left\lfloor \frac{c}{b}\right\rfloor,$

allocates a rectangular DP table of size \((i_{\max}+2)\times(j_{\max}+2)\), and fills it from bottom-right toward top-left so that the two successor states are already known when a cell is updated.

A tiny tolerance \(\varepsilon=10^{-16}(1+c)\) is added in the feasibility test \(ia+jb\le c+\varepsilon\) to protect against floating-point roundoff when \(a\) and \(b\) are irrational square roots.

Each DP value is also clamped at the target \(n\). This does not change the answer, because the outer search only asks whether the capacity is at least \(n\); once a cell reaches \(n\), larger values are irrelevant. Saturation prevents overflow and keeps the arithmetic numerically stable.

The C++, Python, and Java implementations all follow this same plan: build Fibonacci numbers, solve 30 independent threshold searches, and print the final sum to eight decimal places.

Complexity Analysis

For one evaluation of \(K(c,a,b)\), the table dimensions are

$I=\left\lfloor \frac{c}{a}\right\rfloor+1,\qquad J=\left\lfloor \frac{c}{b}\right\rfloor+1,$

so the dynamic program uses \(O(IJ)\) time and \(O(IJ)\) memory.

To obtain \(C(n,a,b)\), exponential bracketing uses \(O(\log C(n,a,b))\) capacity evaluations, followed by exactly 90 bisection evaluations. Since the Project Euler instance has only 30 parameter pairs, the total runtime is the sum of these fixed-cost searches over \(k=1,\dots,30\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=406
2. Dynamic programming: Wikipedia — Dynamic programming
3. Binary search on the answer: cp-algorithms — Binary search
4. Fibonacci numbers: Wikipedia — Fibonacci number
5. Recurrence relations: Wikipedia — Recurrence relation