Nib asked for
Why Twenty Guesses Is Enough
Each guess halves what remains, so each extra guess doubles what you can handle, and twenty doublings reach about a million.
5 steps, drawn by Nib. Read it here, or watch him draw it. Updated .
1one guess
Start at the other end. Suppose only one number could be hidden, say a single possibility left. You need no more guesses at all; you just name it. Now allow one guess: with one guess you can handle exactly one number, because that guess must be the answer itself.
With one guess, you can handle exactly one number.
With just one guess and no feedback to use, how many numbers can you be sure to find?
Show the answer
One. Your guess must simply be right.
2two guesses
Add a second guess. Now the first guess can land in the middle of a range of three numbers. If it is wrong, the answer says higher or lower, and exactly one number remains on that side, which your last guess covers. So two guesses handle three numbers: one in the middle, plus one on each side.
Two guesses handle three numbers.
a common mix-upPeople expect two guesses to handle only two numbers; the higher/lower feedback is what stretches it to three.
3seven numbers
Add a third guess. Pick the middle of a longer range. A wrong answer leaves one side, and each side can be at most what two guesses handle, which is three numbers. So the range is three plus three plus the middle one: seven. The pattern is that each new guess takes the old range, uses it twice (one copy per side), and adds the guess itself.
Three guesses handle seven numbers: two sides of three, plus the middle.
By the same pattern, how many numbers can four guesses handle?
Show the answer
Fifteen: seven on each side plus the middle.
4the pattern
Look at the sequence: 1, 3, 7, 15, 31. Each is a doubling of the one before, plus one. Equivalently, each is one less than a power of two: 2, 4, 8, 16, 32 minus one. So n guesses handle 2 to the n, minus 1, numbers. Doubling is the engine: one extra guess means twice the range.
n guesses handle 2^n minus 1 numbers.
a common mix-upCapacity is not exactly the power of two; it is one less, because one guess is spent on the middle itself.
5twenty guesses
Keep doubling. Ten guesses handle 1,023 numbers, about a thousand. Ten more doublings multiply that by about a thousand again. Twenty guesses handle 2 to the 20th power minus 1, which is 1,048,575 numbers. That is more than a million, so twenty guesses are enough, with a little room to spare.
Twenty guesses handle 1,048,575 numbers, enough for a million.
If the range doubled to two million, how many guesses would you need?
Show the answer
Twenty-one. One extra guess doubles the capacity to about 2.1 million.
Every guess you add doubles your reach, so a million numbers cost only twenty guesses, and a billion would cost just thirty.