Detailed mathematical approach

Problem Summary

There are three plates containing \(a\), \(b\), and \(c\) beans, and exactly one bean is magical. A question may inspect only a subset taken from a single plate, and the answer is just yes or no. Let \(h(a,b,c)\) be the minimum number of such questions that always identifies the magical bean. The task is to evaluate

$H(N)=\sum_{\substack{a,b,c\in\mathbb{Z}_{\ge 0}\\1\le a+b+c\le N}} h(a,b,c) \pmod{10^9+7}.$

A brute-force search over triples or over decision trees is hopeless for the true input size, so the solution turns the problem into a counting argument over dyadic ranges.

Mathematical Approach

Write \(s=a+b+c\) for the total number of candidate beans. The whole strategy revolves around the threshold

$D=2^{k-1}\qquad\text{whenever}\qquad 2^{k-1}\lt s\le 2^k.$

At that scale, \(k\) is the information-theoretic lower bound, and the only question is whether a given triple attains that bound or needs one extra step.

Step 1: Baseline Lower Bound from Binary Questions

With \(s\) possible locations for the magical bean, any yes/no decision tree of depth \(t\) has at most \(2^t\) leaves. Therefore every strategy satisfies

$h(a,b,c)\ge \left\lceil \log_2 s \right\rceil.$

For fixed \(s\), the number of nonnegative triples \((a,b,c)\) with total \(s\) is the stars-and-bars count

$\binom{s+2}{2}.$

So the universal baseline contribution is

$B(N)=\sum_{s=1}^{N}\left\lceil \log_2 s \right\rceil \binom{s+2}{2}.$

Since \(\lceil\log_2 1\rceil=0\), the \(s=1\) term vanishes automatically. The implementations group this sum by dyadic blocks \((2^{k-1},2^k]\) and expand

$\binom{s+2}{2}=\frac{s^2+3s+2}{2},$

so each block can be evaluated from closed forms for \(\sum s\) and \(\sum s^2\).

Step 2: When Can the Lower Bound Be Achieved?

Fix a triple with \(2^{k-1}\lt s\le 2^k\), and set \(D=2^{k-1}\). If we hope to finish in exactly \(k\) questions, then after the first question both branches must leave at most \(D\) candidates, because only \(k-1\) further yes/no answers remain.

Suppose the first question selects a subset of size \(q\) from one plate. Then the two branch sizes are \(q\) and \(s-q\), so we must have

$s-D\le q\le D.$

Inside the cube \(0\le a,b,c\le D\), the chosen subset can only come from a plate that contains at least \(s-D\) beans. Thus a triple is easy at level \(k\) if at least one coordinate is at least \(s-D\). It is hard if no coordinate reaches that threshold.

Because \(s=a+b+c\), the condition \(a\lt s-D\) is equivalent to \(b+c\gt D\), and similarly for the other coordinates. Therefore, inside the cube, hardness is exactly the system

$a+b\gt D,\qquad a+c\gt D,\qquad b+c\gt D.$

Every hard triple needs \(k+1\) questions; every non-hard triple attains the lower bound \(k\).

Step 3: Count the Hard Region Inside \([0,D]^3\)

Define

$W_D(X)=\#\left\{(a,b,c)\in\mathbb{Z}_{\ge 0}^3:0\le a,b,c\le D,\ a+b+c\le X,\ a+b\gt D,\ a+c\gt D,\ b+c\gt D\right\}.$

This is the hard region at level \(k\) restricted to triples with total at most \(X\). To count it, use inclusion-exclusion on the three “easy” events

$E_{ab}:\ a+b\le D,\qquad E_{ac}:\ a+c\le D,\qquad E_{bc}:\ b+c\le D.$

By symmetry,

$W_D(X)=U_D(X)-3A_D(X)+3B_D(X)-C_D(X),$

where \(U_D(X)\) counts all triples in the box with total at most \(X\), \(A_D(X)\) counts one easy event such as \(E_{ab}\), \(B_D(X)\) counts an intersection of two easy events, and \(C_D(X)\) counts the intersection of all three.

The simplest term is the universe count:

$U_D(X)= \begin{cases} \binom{X+3}{3}, & X\le D,\\ \binom{X+3}{3}-3\binom{X-D+2}{3}, & D\lt X\le 2D. \end{cases}$

The remaining terms reduce to one-dimensional polynomial sums after fixing either a pair sum or one coordinate. That is why the implementation only needs closed forms for arithmetic and quadratic progressions rather than any explicit enumeration of triples.

Step 4: Recursive Reduction When One Plate Exceeds \(D\)

Now consider a triple with total \(s\le 2D\) but with one coordinate larger than \(D\). Because \(s\le 2D\), at most one coordinate can exceed \(D\).

Assume \(a\gt D\). To keep both branches within size \(D\), the first question must isolate exactly \(D\) beans from that oversized plate. The “yes” branch then has exactly \(D\) candidates, while the “no” branch leaves the reduced triple

$\left(a-D,\ b,\ c\right),$

whose total is \(s-D\).

So the original triple is hard at level \(k\) precisely when the reduced triple is hard at level \(k-1\). If we let \(E_k(X)\) denote the number of hard triples with total at most \(X\) on level \(k\), then

$E_k(X)= \begin{cases} W_{2^{k-1}}(X), & X\le 2^{k-1},\\ W_{2^{k-1}}(X)+3E_{k-1}(X-2^{k-1}), & 2^{k-1}\lt X\le 2^k. \end{cases}$

The factor \(3\) comes from the choice of which plate is the oversized one.

Step 5: Final Summation Formula

Let \(K\) be the largest integer with \(2^{K-1}\lt N\le 2^K\). Every triple in the dyadic block \(2^{k-1}\lt s\le 2^k\) contributes the baseline \(k\), and every hard triple contributes one extra question. Hence

$H(N)=\sum_{k=1}^{K} k\sum_{s=2^{k-1}+1}^{\min(N,2^k)}\binom{s+2}{2}+\sum_{k=1}^{K}E_k\!\left(\min(N,2^k)\right)\pmod{10^9+7}.$

This is the exact formula used by the implementation.

Worked Example

Take \(s=8\). Then \(k=3\) and \(D=4\).

For the triple \((3,3,2)\), all pair sums exceed \(4\):

$3+3\gt 4,\qquad 3+2\gt 4,\qquad 3+2\gt 4.$

So it lies in the hard region. Any three-question strategy would need its first question to split the eight candidates into two branches of size at most four, which forces a queried subset of size exactly \(4\). But no plate contains \(4\) beans, so such a first move is impossible. Therefore

$h(3,3,2)=4.$

By contrast, \((5,2,1)\) is easy at the same level: ask about a four-bean subset of the plate containing five beans. The “yes” branch leaves \(4\) candidates, and the “no” branch leaves \((1,2,1)\), whose total is \(4\), so two more questions suffice. Thus \(h(5,2,1)=3\).

The recursive idea appears one level higher with \((11,3,2)\), where \(s=16\) and \(D=8\). Asking about an eight-bean subset of the large plate leaves either a block of size \(8\) or the reduced triple \((3,3,2)\), already known to be hard. Hence \((11,3,2)\) is hard at level \(4\) and needs \(5\) questions.

How the Code Works

The C++, Python, and Java implementations work entirely modulo \(10^9+7\). They first accumulate the baseline term by grouping totals \(s\) into dyadic intervals and evaluating

$\sum \binom{s+2}{2}=\sum \frac{s^2+3s+2}{2}$

with closed forms for \(\sum s\) and \(\sum s^2\). Next they evaluate the hard-region counts \(W_D(X)\) by inclusion-exclusion. Each component of that inclusion-exclusion is reduced to a short list of polynomial range sums, so no loop over triples is ever required.

Finally, the implementation memoizes the recursive states \(E_k(X)\). Each state performs one within-cube count and, when \(X\gt 2^{k-1}\), one recursive call to the previous level. The answer is the baseline term plus the total number of hard triples across all relevant levels.

Complexity Analysis

Let \(K=\lceil\log_2 N\rceil\). The number of dyadic levels is \(O(K)\), and each recursive state is evaluated once. Every state uses only constant-time modular arithmetic together with closed-form sums, so the total running time is \(O(\log N)\). The memoized state table also has size \(O(\log N)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=847
2. Decision tree: Wikipedia — Decision tree
3. Inclusion-exclusion principle: Wikipedia — Inclusion-exclusion principle
4. Stars and bars: Wikipedia — Stars and bars
5. Binomial coefficient: Wikipedia — Binomial coefficient