Find my number
I'm "thinking" of a number and may lie. Build a question by tapping numbers (or use a preset), then ask "is it one of these?". Start with 1 to 64 and one lie: honest, six questions would do, and with one lie the best possible is 10. The meter shows, after every answer, whether that's still in reach. Then try a million numbers, more lies, or the picture board.
Volume counts, for every number still possible, the answer sequences I could still give if that were my number. With one lie allowed, a number that needs no lie so far can still survive any one lie in the q questions left (q + 1 ways), and a number that needs one lie can't survive another (1 way). With more lies the counts are binomial: k lies to spare among q answers is C(q, 0) + … + C(q, k) ways. Each answer splits the volume in two and I always pick the bigger part, so the best a question can do is halve it. The questions left can separate at most 2q sequences, so once the volume is over the line no strategy can win in time.
On the million-number board each pixel of the strip is a bin of about a thousand numbers, colored by the share of them in each class. The bars below it count each class on a log scale, and the blue part of each bar is the share of that class in your question.
Your turn to lie
Think of a number from 1 to 64 (or one of the 20 pictures) and keep it to yourself. I'll ask whether it's one of the highlighted ones. Answer Yes or No, and lie whenever you like, up to the limit you set. I'll still name it, and I'll tell you which answers were lies.
The page picks each question to split the volume as evenly as it can, the same count as the meter above, and near the end it searches every possible continuation. It never asks more than the number shown: that's the guaranteed worst case for this many lies, checked against every way you could answer. Lie more often than you said and I won't notice: I'll name the wrong one just as confidently. Every question goes into narrowing down and none into double-checking, so both answers always leave someone standing and there's no slack to catch the extra lie. An error-correcting code past its limit fails the same way: it "corrects" to the wrong message without complaint. Catching more lies than you can fix costs extra questions.
Questions are bits, lies are bit errors
Write the answers down as you go: yes = 1, no = 0. After q questions you have a q-bit word. If I never lie, each number produces exactly one word, and you need enough bits to give a million numbers their own word: 220 = 1,048,576, so 20 questions.
A lie flips one bit. Now each number owns not one word but a little cloud of them: its honest word plus every word one flip away, q + 1 words in all. Two numbers' clouds can't overlap, or one word would fit both and you couldn't tell them apart. So a million clouds of size q + 1 have to fit among the 2q words: 106 × (q + 1) ≤ 2q. At q = 24 the clouds need 25 million words and there are only 16.8 million. At 25 they need 26 million and there are 33.5 million. With k lies the cloud is everything within k flips, C(q, 0) + … + C(q, k) words, which is why the million-number board says 25, 29 and 33 for one, two and three lies.
That inequality is the sphere-packing bound (or Hamming bound) from coding theory, and the game's volume is the same count made mid-game: the words still available to each number, given the answers so far. The meter is a sphere-packing bound you can watch.
If you had to write all 25 questions down before hearing any answers, you'd be choosing a million 25-bit codewords that stay at least three flips apart: an error-correcting code. One exists. A Hamming code shortened to 20 data bits and 5 check bits has 220 codewords, enough for a million, and corrects any single flip. So with one lie and a million numbers, hearing the answers as you go buys nothing. With more lies, or a liar allowed a fixed fraction of lies, feedback does help. Over many questions, fixed questions only cope if fewer than a quarter of the answers are lies, while adaptive questions can handle any fraction below a third (Spencer and Winkler).
The same packing explains why the reverse game can't catch an extra lie. In the best strategies the clouds use up nearly every word. Sixteen numbers with one lie fit exactly into 7 questions (16 × 8 = 27, the [7,4] Hamming code), so every possible answer word decodes to some number and none is left to signal "you cheated". Codes work the same way. A code can correct t errors, or detect some extra ones, but every word kept in reserve for detection is one that can't be used for a message.
Try this
- On 1–64 with one lie, press suggest a question every time. It finishes in exactly 10, and the history points out the question I lied on. Play again: the lie moves.
- Ask the six binary digits first (1, 2, 4, …, 32). Each one cuts every class exactly in half, so the meter runs parallel to the line. Honest binary search isn't wrong here, it just isn't finished: four more suggested questions find the number, 10 in all.
- Start with "≥ 60" instead. The meter jumps over the line and turns red, and it can never come back: the best question halves the volume, and the capacity halves too.
- Set lies to 0 and the board is plain binary search, 6 questions. Then try 1, 2, 3 lies: 10, 13, 16. On the million board it's 20, 25, 29, 33. A lie costs about log₂ q extra questions, because that's how many bits it takes to say where the lie was.
- In Your turn to lie, lie on the very first answer. I still get your number and name the question. Then set the limit to 1 and lie twice: I name the wrong number without blinking.
- Give the picture board to a kid with one fib allowed: 20 pictures, never more than 8 questions.
Build plan
- Core math, no UI. A state is a vector of counts: how many candidates have used 0, 1, …, k lies.
- Berlekamp volume: Vq(state) = Σi ai · Σj≤k−i C(q, j).
- The adversary answers to leave the most work: the most questions still needed (exact search near the end), then the most volume, then the most candidates.
- Test: a state is winnable in q questions only if Vq ≤ 2q. Check against the known 1-lie result (10⁶ needs 25).
- Small board, 1 lie. Numbers 1–64, one allowed lie, question = "is it in this set?" built by tapping cells or using presets (≥ n, bit k is 1, even).
- Cells colored by lies used, a question history, and the volume meter against 2q.
- Reverse mode. The page asks using a volume-halving strategy. You answer with Yes/No and may lie up to k times, and it announces your number.
- Scale and settings. 1–1,000,000 with 0–3 lies (the board becomes a histogram of the lie-count classes), and a "kid mode" with 1–20 and picture questions.
- Write-up. The link to codes: each question is a bit, lies are bit errors, and the questioner is designing an error-correcting code one bit at a time. Add the "try this" list and the deep cut.
The deep cut
Stanisław Ulam posed the question in his 1976 autobiography, Adventures of a Mathematician, and Alfréd Rényi had described a version in 1961. Elwyn Berlekamp had already found the key tool in 1964, in his thesis on codes with feedback: the volume, and the fact that each answer splits it exactly in two. Andrzej Pelc settled the one-lie case in 1987: for n numbers you need the least q with n(q + 1) ≤ 2q when n is even, and n(q + 1) + (q − 1) ≤ 2q when n is odd. For a million that's 25. Two lies (Guzicki, 1990) and three (Deppe, 2000) took long casework.
The odd case is the volume bound failing. With 3 numbers and one lie the volume is 3 × 5 = 15, which fits in 4 questions (24 = 16). But a useful first question splits the numbers 2 and 1, and if I answer for the 2 the volume left is 2 × 4 + 1 = 9, more than the 8 that three questions can handle. You need 5. This page's questioner halves the volume while there are many candidates and switches to exhaustive search once 24 or fewer remain, because those endgame traps are real. Its test file checks it against every possible answer sequence: a million numbers in exactly 20, 25, 29 and 33 questions for 0 to 3 lies, and Pelc's formula for every size up to 200 with one lie.
The liar here never commits to a number. It's an adversary that answers whichever way leaves you more work, which is the same as a real liar who picked the worst number for you in advance. Any strategy that beats the adversary beats every real player too, so "the page cheats" makes the guarantee stronger, not weaker.
Reading
- S. M. Ulam, Adventures of a Mathematician, Scribner, 1976.
- E. R. Berlekamp, “Block coding for the binary symmetric channel with noiseless, delayless feedback,” in Error Correcting Codes, Wiley, 1968.
- A. Pelc, “Solution of Ulam's problem on searching with a lie,” Journal of Combinatorial Theory A 44, 1987.
- W. Guzicki, “Ulam's searching game with two lies,” Journal of Combinatorial Theory A 54, 1990.
- C. Deppe, “Solution of Ulam's searching game with three lies or an optimal adaptive strategy for binary three-error-correcting codes,” Discrete Mathematics 224, 2000.
- A. Pelc, “Searching games with errors—fifty years of coping with liars,” Theoretical Computer Science 270, 2002.
- J. Spencer & P. Winkler, “Three thresholds for a liar,” Combinatorics, Probability and Computing 1, 1992.
- R. W. Hamming, “Error detecting and error correcting codes,” Bell System Technical Journal 29, 1950.