A Cantor–Mills demo
You take a test of 30 true/false questions. After each attempt you learn only your total score — never which answers were right or wrong. You may retake the identical test as often as you like. What is the smallest number of attempts that guarantees a perfect score, no matter what the answer key is?
Answer: 17 — 16 fixed probes whose scores pin down every answer, plus one perfect submission. Click the key row below to rig the test, then run it and watch the deduction.
Run it
Sixteen fixed probes, then one guaranteed-perfect submission. Step through it or let it play.
Why it works
Submit all-True and the score is exactly t, the number of True answers. Flip your answer to False on a chosen set S and the score becomes t + |S| − 2·(#True inside S). So each attempt secretly reports how many True answers sit inside any subset you pick — this is the classic coin-weighing problem with a spring scale, in disguise.
The obvious strategy — flip one question per attempt — therefore needs 31 attempts. But a probe's score is a number from 0–30, worth up to ~5 bits. Asking about one question at a time wastes almost all of that.
The 15 flip-sets on the board are rows of a Cantor–Mills detecting matrix (1966): no two of the 2³⁰ ≈ 1.07 billion possible answer keys produce the same 15 counts — verified here exhaustively, every case checked. Add the all-True baseline to learn t, and 16 scores identify the key uniquely. Attempt 17 submits it: guaranteed 30/30.
The probes are fixed in advance — you could submit all 16 without reading a single score until the end.
Why do these particular sets work? They come in pairs that share the same pattern on the first block of questions. Subtract a pair's scores and that block cancels, leaving a clean measurement of the rest. Add a pair's scores and you get 2×(block) + z — even plus a single fresh answer, so the sum's parity reads one answer for free. Recurse: 30 questions become a 12-question test, then 4, then 1. That parity bonus is exactly why 15 probes cover 30 questions instead of one-probe-one-question.
Each attempt returns one of 31 possible scores, so k attempts distinguish at most 31k transcripts. Since 31⁶ < 2³⁰, no strategy — adaptive or not — can guarantee success in fewer than 8 attempts. In practice a mid-range score carries only ~2.5 bits (counts concentrate around the middle), which pushes the true optimum to roughly 13–15; its exact value is an open question. Adapting each probe to earlier scores provably can't improve the leading behavior — the only attempt that must be adaptive is the last one.
Every test size
The riddle works for any number of questions n, and the best known guarantee is β(Qn) + 1 attempts: β(Qn) — the metric dimension of the n-dimensional hypercube — is the fewest fixed "landmark" answer sheets whose scores pin down every possible key, and the final attempt submits the deduced key. Each tile shows that guarantee. Exact values of β are only known up to n = 13; everything beyond is an upper bound (a cleverer strategy may yet do better). While building this page we searched past the published bounds — and improved three of them.
All three records come from a search over ±1 sign matrices: a matrix resolves the test if and only if no nonzero vector z ∈ {−1,0,1}n satisfies Wz = 0. We ran simulated annealing on the matrix entries, scoring each candidate by exactly counting its ternary kernel with a meet-in-the-middle enumeration over 3n/2 half-vectors (~4.8 million per side at n=29) — millions of candidate matrices evaluated over roughly ten CPU-days. The 15×29 fell to annealing directly; the 14×26 turned up inside a random row-and-column slice of an already-solved 15×29, a "slice audit" that costs almost nothing; the 13×24 came from industrializing that trick — slicing random 13×23 children out of the solved 15×29s and immediately scanning each for a one-column extension (two independent slices found the same winning column). Every claimed record was then re-verified by two independently written counters (C and JavaScript). SAT-based provers are grinding on the matching lower bounds.
Sources: exact values n ≤ 13 — OEIS A303735 (brute force + MaxSAT verification); bounds — Mladenović et al. 2012 (variable neighborhood search), Nikolić et al. 2017 (dynamic programming), Hertz 2020 (IP-based swapping), Lu & Ye 2022 (coin-weighing bridge, incl. the easy-to-miss β(Q₂₈) ≤ 15). The three new records were found by simulated-annealing search over ±1 matrices with exhaustively verified empty ternary kernels. Certificates + two independent verifiers, one command each: github.com/shmulc8/crack-the-test.
A 15×29 sign matrix with no nonzero vector z ∈ {−1,0,1}²⁹ satisfying Wz = 0 — checked exhaustively (meet-in-the-middle over 3¹⁵ half-vectors) by two independent implementations. Its rows encode 15 landmark answer sheets that resolve a 29-question test: 16 attempts, one fewer than the published 17.
+++++++++-+++++++++++++++++++ --+--+-+-+-+-+-+-+-++-+-+-++- +--+--+++++---+++++-+++--++++ -+-+-+--+-++-+--+-+++-++-++++ ++++--+--+++--+--++++++++++++ --+-+-+-+-++-+-+-+-+-+-+-+-++ +--++++--+++--+++++---+++++-+ -+-++-++-+++-+--+-++-+--+-+++ ++++++++++++--+--+++--+--++++ --+--+-+-+-++-+-+-++-+-+-+-++ +--+--+++++-+++--+-+--+++++-+ -+-+-+--+-+++-++-+++-+--+-+++ ++++--+--+++++++++++--+--++++ --+-+-+-+-+++-+-+-+++-+-+-+++ +--++++--++++++--++++++--++++
A 13×24 sign matrix with the same verified property, found by extension-scanning random 13×23 slices of the solved 15×29s. It resolves a 24-question test in 14 attempts instead of the published 15.
-+--+-++-+-++-+-+-+-++-- +-+--++++---+++++++--++- --+-+---++-+-+-++-++-++- +++--+-+++----++++++++++ -+-+-+--++-++-+--+-+-++- +-++++-+++--++++--+++-+- --++-+++++-+-+-+-+--+++- ++++++++++----++--+--++- -+--+-++-++--+-+-+-+-++- +-+--++++-++--+---+++-+- --+-+---+++-+-++-+--+++- +++--+-+++++++++--+--+++ +-++++-+++++--+++++--++-
A 14×26 sign matrix with the same verified property, found inside a random row/column slice of a solved 15×29. It resolves a 26-question test in 15 attempts instead of the published 16.
++++++++-+++++++++++++++++ --+--+-+-+-+-+-++-++-++-++ -+-+--+-++-+-++-+-+-++++++ ++++---+++--+--++++++++++- --+-+-+-++-+-+-+-+--+-++++ +--++--+++--++++--++++-+++ -+-+++-+++-+--+--+-+-+++++ ++++++++++--+--+--+-++++++ --+--+-+-++-+-+--+--+-++++ +--+-++++-+++--+--++++-+++ -+-+--+-+++-++-+-+-+-+++++ ++++---+++++++++--+-++++++ --+-+-+-+++-+-+-+-++-+++++ +--++--++++++--++++-++++++
Lineage: the riddle is the coin-weighing problem of P. Erdős & A. Rényi, On two problems of information theory (1963) — how many weighings on a spring scale identify the counterfeit coins. The 17-attempt construction is D. G. Cantor & W. H. Mills, Determination of a subset from certain combinatorial properties, Canad. J. Math. 18 (1966); F. Harary & R. A. Melter recast it as the metric dimension of graphs (1976). The deduction log shows the genuine arithmetic — the page never peeks at the key, only at the scores.