Contents

Number Guessing Game

This is a famous children's game: it looks astonishing at first that the number between 1 and 1000 could be guessed with only 10 questions.

Rules are simple: first player secretly chooses a number from the range 1 ... 1000 and second tries to guess it.
Second player could ask no more than 10 questions to which the first could answer only Yes or No.

The trick is to ask such questions which divide the set of possible values in two almost equal sets. For example, the first question could be Is your number less then 501? - more info on this algorithm could be found in the article about the Binary Search

Below you can try the live example of this game in our virtual terminal - just follow the instructions:

Let us follow the example of calculations "step-by-step" if you still could not get the idea. Let the "Anna" be the player who chooses the secret value and "Bob" is the one who guesses:

Anna: I'm ready! (she thinks of 561)

Bob: 500 is greater than your number?
Anna: No (so it falls into range 500...1000)

Bob: 750 is greater than yours?
Anna Yes (so it falls into range 500...749)

Bob: 625 is greater than yours?
Anna: Yes (so it falls into range 500...624)

Bob: 563 is greater than yours?
Anna: Yes (so it falls into range 500...562)

Bob: 531 is greater than yours?
Anna: No (so it falls into range 531...562)

...

Please, try to continue the sequence of questions and answers yourself to see that 10 questions are really sufficient.

You can also try to write such a guessing program.