This question was asked before but I have a lot of trouble understanding the answers given.
Why is it that a number selected at random between 1 and 100 can be determined in 7 or less guesses by always guessing the number in the middle of the remaining values, given that you're told whether your previous guess was too high or low?
Here's a link to the earlier thread: Guessing number between 1-100 always can always be guessed in 7 guess. Why?
I wonder if someone could explain this in greater detail?
$\endgroup$4 Answers
$\begingroup$The answer is that $2^7=128>100$.
To be more precise:
Say that you start by guessing $50$. Either you're right, in which case you're done, or you're wrong; if you're wrong, then you know that the number is either in $[1,49]$ or $[51,100]$, so that there are only $49$ or $50$ possibilities left.
Now, assuming that you aren't already done, you have a collection of $49$ or $50$ possibilities left; guess the middle one. That is, if you are on $[1,49]$, guess (say) $25$; if you're on $[51,100]$, then guess (say) $75$. If you got it right: great. If not, then you find out whether it should be higher or lower; in particular, if you previously knew it was in $[1,49]$, then you either now know it is in $[1,24]$ or you now know it is in $[26, 49]$. If you previously knew it was in $[51,100]$, then either you know that it is in $[51,74]$ or that it is in $[76,100]$.
In any case, you have either already guess right, or you have narrowed down the possibilities to one of $[1,24]$, $[26,49]$, $[51,74]$, or $[76,100]$. In any one of these cases, there are at most $25$ possibilities left, and it must be one of them.
Continue in this way: cut your current interval of possibilities in half by a guess, so that you are either right or you can discard roughly half of the possibilities based on the announcement of "higher" or "lower".
By continuing this process, in the third step you narrow it down to at most $12$ possibilities; in the fourth, to at most $6$; in the fifth, to at most $3$; in the sixth, to at most $1$; and voila! In your seventh guess, assuming that you're unlucky enough to have not guessed it yet, there's only one number that could possibly be it.
$\endgroup$ 4 $\begingroup$Note that all positive integers between $1$ and $100$, when represented in binary has at most $7$ digits. This is due to the fact that $2^7 = 128 > 100$.
$100$ in binary is $1100100$. Hence, to get any number between $1$ and $100$, all you need to know are its $7$ digits in binary.
So you ask the question if the first digit is $0$. Irrespective of the answer being yes or no, you know the digit once the question has been answered. If the answer is yes, then the first digit is $0$, if the answer is no, then the first digit is $1$.
Repeat this for the remaining $6$ digits and conclude what the number is.
$\endgroup$ $\begingroup$Let's start with a smaller number: 15. Why 15? Because it is $2^4-1$, and we can do it in 4 guesses. Your first guess is 8, as it is halfway from 1 to 15. In general, for problems like this, you want to make your guesses so it doesn't matter which answer you get-that gets you the most information. Whether you are high or low, you will have a range of 7 left. Let's say you were low, so the range is now 9 to 15. Guess 12 and you will have 3 left either way. Now guess 10 or 14 for your third guess and you will get it on the fourth try.
This scales up because $(2^n-1) + 1 + (2^n-1)=2^{n+1}-1$, so if you start with $2^{n+1}-1$ possibilities and guess the middle, you will have $2^n-1$ left no matter what the answer (unless you get it right)
If you know about binary numbers, your first guess gets the leading bit, your second gets the second bit, and so on.
$\endgroup$ $\begingroup$I had the same problem for a program I was writing and I wasn't satisfied with these solutions because the set of possible questions was still very large and depended on the previous answer. I wanted a solution that asked the SAME three questions for a set of numbers from 1 to 8, or the SAME 7 questions for a number from 1 to 100 and did NOT depend on the previous answers. So here's an example solution for guessing a letter from the first eight letters of the alphabet. The questions are always the same.
- Is the letter in the set {D,E,F,G}?
- Is the letter in the set {B,C,F,G}?
- Is the letter in the set {A,C,E,G}?
If you test these three questions you will see that they always suffice in guessing the right answer for guessing a letter from A to H. If you can't figure out why it works, here's a clue. Write the binary number for each letter of the alphabet under each letter. A is 001, B is 010, etc. (H is 000 in this case.) Then compare those numbers to the three sets above.
$\endgroup$ 2
