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.