Guess my number

How halving finds any number in 7 questions

Each question splits the numbers still possible into two groups, and the answer throws one away. Asking "is it greater than the middle?" makes the two groups as equal as they can be, so whichever answer comes, at most half (rounded up) are left. From 100 that goes 100, 50, 25, 13, 7, 4, 2, 1: 7 questions.

Seven is not a coincidence of 100. Six answers can only tell apart 2⁶ = 64 cases, fewer than 100, so no list of six yes/no questions can work for every number. Seven can tell apart 2⁷ = 128, enough with room to spare. In general n numbers need ⌈log₂ n⌉ questions, the number of bits it takes to write n − 1 in binary.

Some numbers take one question fewer: the halves of an odd count are not equal, and a number in the smaller half can finish early. None takes more. Replay this game.

The answers are the binary digits

With 0 to 127 the halving lines up exactly with binary. The first question, greater than 63, asks whether the 64s bit is 1. Whichever half is left, the next question asks about the 32s bit, then the 16s, down to the 1s. Write yes as 1 and no as 0 and the seven answers are the number in binary. That is why a yes/no answer is said to carry one bit of information: exactly one when yes and no are equally likely, as here, and less when the split is uneven.

The binary converter shows the same place values for any number. Ranges that are not a power of two, like 1 to 100, still need whole bits: 100 numbers carry log₂ 100 ≈ 6.64 bits of information, and a question cannot ask for part of one.

Liar mode: catching one lie with a Hamming code

Stanisław Ulam posed this game in his autobiography, Adventures of a Mathematician (1976): how many yes/no questions find a number if the answerer may lie? Plain halving is hopeless, because one wrong answer sends the search into the wrong half and it never comes back. Asking every bit question three times and taking the majority works, but costs 21 questions for 0 to 127.

Liar mode needs only 11, by borrowing an error-correcting code. The questions are numbered 1 to 11. Questions 3, 5, 6, 7, 9, 10, 11 ask for the seven bits of your number, 64s to 1s. Questions 1, 2, 4, 8 are checks: check c asks whether an odd number of the bit questions whose own number contains c in binary would be answered yes, so that across its whole group the honest yes answers always come to an even count.

A lie on question p flips one answer, so it makes the yes count odd in exactly the groups that contain p, and those are the checks whose numbers add up to p in binary. Add up the broken checks and you have the number of the lie. If nothing is broken, nobody lied. This sum is called the syndrome.

This is a shortened Hamming(15, 11) code: the full code has 11 data bits and checks 1, 2, 4 and 8 over 15 positions; keeping positions 1 to 11 leaves 7 data bits, exactly 0 to 127. Any two numbers differ in at least three of the eleven answers, so one lie leaves the honest number closer than any other. Two lies can be mistaken for one lie somewhere else, and then the answer comes out wrong; if the syndrome is 12 to 15, a position that does not exist, the page can at least tell you so. Lies on questions 4 and 8 do that: they break checks 4 and 8, which add up to 12.

11 is the least possible. Each number has 12 answer patterns that must lead to it (the honest one, and one with each answer flipped), and no two numbers can share a pattern, so 128 × (q + 1) ≤ 2^q. That fails at q = 10 (1,408 against 1,024) and holds at 11 (1,536 against 2,048), even if each question could depend on the answers before it.

The evil version: an opponent that never commits

In "you guess mine" the evil page does not pick a number. It keeps the range of numbers that fit every hint so far, and on each guess says whichever of higher or lower leaves more of them. It never lies, since every reply is true for every number still in play, but it makes each guess as useless as it can be.

Against that, the best a player can do is halve, and halving still rules out only about half each time, and never gets lucky. From n numbers that takes ⌊log₂ n⌋ + 1 guesses. When n is a power of two that is one more than the yes/no game, because the last number has to be said out loud: 7 questions but 8 guesses for 0 to 127. Otherwise the two counts are equal, both 7 for 1 to 100, because a guess has three outcomes and can carry more than one bit. Here is a halving player against it on 1 to 100:

This is an adversary argument, the standard way to prove a lower bound: if a clever opponent can always keep two numbers alive for this long, no strategy can be sure to finish sooner.

Questions needed for each range

Yes/no questions: ⌈log₂ n⌉. Higher/lower guesses, counting the winning one: ⌊log₂ n⌋ + 1. With one lie: the smallest q with n × (q + 1) ≤ 2^q, a lower bound that Hamming codes reach for 0 to 127.

Common mistakes

• Greater than, or greater than or equal? Mixing the two halfway through moves the boundary by one and can lose the number. Pick one wording and keep it; this page always asks "greater than".
• Guessing the middle of the original range. The middle must be of what is still possible. After "higher than 50" from 1 to 100, what is left is 51 to 100, so the next guess is 75, not 25 or 51.
• Counting 100 as needing 6.64 questions. log₂ 100 ≈ 6.64, but questions come in whole numbers, so it is 7.
• Expecting the same count for questions and guesses. For 0 to 127 it is 7 yes/no questions but 8 higher/lower guesses, as explained above.
• Asking each question twice to beat a liar. Two answers that disagree show a lie happened, but not which one was true. It takes three copies, or a code like the one in liar mode, to correct it.