applets.

Guess My Number

← All apps

About Guess My Number

The higher-or-lower game, both ways round. In YOU GUESS the stall has picked a number from 1 to 100, 1,000 or a million; type a guess and it says higher or lower. The measuring board shows what's still possible, with shutters over everything you've ruled out, and a close-up underneath once the gap gets small. A guess outside what you already know isn't counted, it just reminds you. Tick Only 7 guesses (or 10, or 20) to play with no more guesses than halving needs. At the end it shows how halving would have played the same number. Your best scores stay in this browser.

In IT GUESSES you think of a number and it finds it, answering with the buttons or the keys H, L and Y. Tick You may fib once and it asks "Is it higher than…?" instead (keys Y and N) and still finds your number even if one of your answers was a lie, and says which.

THE STORY

This app grew from two Python scripts, Guess.py and Number Guessing Game.py: a number from 1 to 100, "Higher" or "Lower", a count of guesses and a timer, and a to-do list in the first one (difficulty, a score from guesses and time, saved best scores, play again) that this page ticks off.

Guessing the middle each time is binary search, one of the first ideas in computing: John Mauchly described it for sorted tables in his 1946 Moore School lectures. Each guess at least halves what's left, so k guesses can tell apart 2k − 1 numbers. That's 7 for 100, 10 for 1,000, and 20 for a million, because 220 = 1,048,576. It's the same sum as the parlour game Twenty Questions: twenty yes-or-no answers are enough to pick one thing out of about a million.

In his autobiography Adventures of a Mathematician (1976), Stanisław Ulam asked how many yes-or-no questions you need to find a number up to a million if the person answering may lie once or twice. For one lie, Andrzej Pelc showed in 1987 that the answer is 25. Elwyn Berlekamp's counting argument from error-correcting codes shows why no one can do better: with q questions to go, a number nobody has lied about yet could still turn out true in q + 1 ways (no lie, or the lie on any one of the q answers), and q answers only have 2q outcomes, so q questions can only cope with n numbers if n × (q + 1) ≤ 2q. For a million, 1,000,000 × 26 fits under 225 = 33,554,432, but 1,000,000 × 25 doesn't fit under 224.

HOW IT WORKS

Halving guesses the middle of what's left, rounding down. For a fair score it compares your count with halving's worst case (the most it could ever need) and with the path it would have taken for your number; halving averages 5.8 guesses for 1 to 100.

In the fib-once game every number still in play is worth q + 1 if it agrees with all your answers and 1 if it disagrees with one (two disagreements and it's out), Berlekamp's weights. Each question goes where the worth on the "yes" side and the "no" side comes out most even. Pelc's 25 allows any yes-or-no question; this page only asks "Is it higher than…?", which can cost one more: it never needs more than 11 questions for 100, 15 for 1,000 and 26 for a million (checked by playing out every possible run of answers). Once one number is left, the answer that number disagrees with is the fib. If you fib twice there may be no number left that fits, and it says so; or a different number may fit with just one fib, and it names that one instead (it can only promise to survive one).

Your guesses never leave this page; your best scores are kept in this browser only.

FURTHER WATCHING AND READING

FROM 1 TO

I'M THINKING OF A NUMBER

from 1 to 100. Have a guess.

GUESSES0
TIME0.0 s
STILL POSSIBLE100
YOUR BEST–
THE WHOLE BOARD1 – 100
CLOSE UP1 – 100