6 Tries to Guess a Number Between 1-100

Question

After every time you guess, you're told if you're right, too high, or too low. Is there a strategy you can use to guarantee you'll get it on your 6th attempt (or lower)?

I know a strategy to get it on your 7th attempt.

Answer 1

Ask about 50.

• If too high, then ask about 25.

• If too low, then ask about 75.

Continue, continually halving the search-space. This requires $\lceil \log_2 (n+1)\rceil$ maximum questions. For 100, that's 7. It is a binary search algorithm known to be $\mathrm O(\log(n))$ time. I'm fairly sure there isn't a faster way. Binary search is considered the best for this problem - unless you are allowed to ask other questions.

Answer 2

Yes.

Each guess eliminates one number as well as dividing the remaining numbers into 2. One guess can pick a number from 3 (is your number 2?). 2 guesses can do 7. N guesses can pick a number from $2^{N+1}-1$, so 6 guesses can do it for 1-127.

Edit: As noted in the comments, you're supposed to have guessed the number on or before the 6th attempt, while this only ensures you know the answer by then.

Answer 3

Totally ripping off Matt Malone's answer:

If you can ask any question about the number where "correct," "too high," or "too low" are valid answers, go with:

1. If you translate the number into trinary, is the last digit a "1"?
2. If you translate the number into trinary, is the second-to-last digit a "1"?
3. If you translate the number into trinary, is the third digit from the right a "1"?
4. If you translate the number into trinary, is the forth digit from the right a "1"?
5. If you translate the number into trinary, is the fifth digit from the right a "1"?
6. Is the number X?

For example, 100 in trinary would be 10201. The first five answers would be: "correct, too high, too low, too high, correct" which would tell me that the number is 100. That would be my final guess.

This works for any integer from 0 up to 242.

Answer 4

A strategy that solves this in under 7 questions is impossible.

For each question, you only get one bit of data (too low, or too high). It's impossible to do this in 6 questions because if you enumerated all the possible outcomes (let's say "too low" is 0, and "too high" is 1):

Q1 Q2 Q3 Q4 Q5 Q6
0  0  0  0  0  0
0  0  0  0  0  1
0  0  0  0  1  0
0  0  0  0  1  1
0  0  0  1  0  0
0  0  0  1  0  1
etc.

there would only be $2^6=64$ possible outcomes, while there are 100 possible numbers.

Answer 5

I think skywalker's answer is the one that the riddler seeks.

In his answer the notion of a 3rd outcome for a guess "that's the number" is being considered.

Consider the following sequences (Un) and (Vn)

Defined as

U(0) = 1

U(n+1) = 2*U(n) ("naive" answer without regard to the additionnal information)

and

V(0) = 1

V(n+1) = 2*V(n) + 1 (with regard to the additionnal information)

For the first items of the suite we have

• n - U(n) - V(n)

• 0 - 1 - 1

• 1 - 2 - 3

• 2 - 4 - 7

• 3 - 8 - 15

• 4 - 16 - 31

• 5 - 32 - 63

• 6 - 64 - 127

• 7 - 128 - 255

As you can see the (Vn) suite is one step ahead of (Un) thanks to the additionnal info. I think this single step ahead is the reason why this answer is the one the riddler is looking for.

EDIT: It is true that you can "only" be certain of the number to be guessed after 6 question instead of giving the right solution on the 6th guess.

But the more naive approach actually leads to the conclusion hat you should be allowed to speak an 8th time to say the number you were certain of after the 7th guess.

(Sorry I wanted to comment on skywalker's answer but I don't have enough points for that)

Answer 6

Six question are not sufficient Player 1 one guesses a number between 1 and 100. Player 2 says some numbers and Player 1 answers with "lower", "higher" or "equal" if his number is lower, higher or equal to your number. We write down the

answers of player 1, 0 if he answers "lower", 1 if he answers "higher" and = if he answers "equal".

An Example: Assume his secret number is 23.

1. We ask 60 and he answers "lower"
2. We ask 20 and he answers "higher"
3. We ask 25 and he answers "lower"
4. We ask 23 and he answers "equal"

The string we write down is 010=.

These are the possible answers

=
0=
1=
00=
01=
10=
11=
000=
001=
010=
011=
100=
101=
110=
111=
0000=
0001=
0010=
0011=
0100=
0101=
0110=
0111=
1000=
1001=
1010=
1011=
1100=
1101=
1110=
1111=
00000=
00001=
00010=
00011=
00100=
00101=
00110=
00111=
01000=
01001=
01010=
01011=
01100=
01101=
01110=
01111=
10000=
10001=
10010=
10011=
10100=
10101=
10110=
10111=
11000=
11001=
11010=
11011=
11100=
11101=
11110=
11111=

If you have a strategy it produces exactly one answer string for every secret number. There are only 63 possible answer strings so there cannot be 100 possible secret numbers.

But six questions are sufficient for the first player to know the right answer

If you can pose one question, you can find the solution if the there are $3$ possible numbers ${1,2,3}$ if you ask for $2$. If the answer is 'yes' the number is $2$, if the answer is 'lower' the answer is $1$ and if the answer is 'higher' the number is $3$. We model this with (a so called binary tree)

  2
 / \
1   3

which can be written in as $1-2-3$ using less space and ask for the number in the middle. If we have two question we can use the model $(1-2-3)-4-(5-6-7)$ or

     4 
   /   \
  2     6
 / \   / \
1   3 7   8

We ask for 7 and if it is not 7 the remaining model is $1-2-3$ or $5-6-7$. which can be solved after one question. So its immediately clear how to query and that there are 7 possible numbers. This can be continued, for 3 queries we have $((1-2-3)-4-(5-6-7))-8-((9-10-11)-12-(13-14-15))$. I will avoid the two dimensional graphic. So for k question we can differentiate between $N(k)=2 \cdot N(k-1)+1=2^{k+1}-1$ numbers. For $k=6$ we get $N(6)=127$ so we can differentiate between $127$ numbers. Therefore $6$ questions are sufficient for the numbers from $1$ to $100$. The first question always asks for the number $64$.

Answer 7

If I am allowed to ask about individual digits, I can do it in 6.

First question: Where X is the number from 1 to 100 inclusive, if X - 1 is left padded with zeros (00-99), is the left digit 5?

If the answer is "lower", I ask about 2. If higher I ask about 7 or 8.

Say I asked about 2, and the answer again comes back "lower". Then I ask about zero and the answer comes back "higher". I've found the first digit to be 1 in three guesses.

I repeat the process to get the second digit in 3 guesses, for 6 total, max. But of course that's 6 questions, not 6 guesses as to the actual number.

Edit: Taking it a step further, asking about the left digit means asking about a 10 number range. If I get to ask about ranges in general, I push the number of questions down to five. Basically, I just split the 1-100 range into ranges of 33, 33, and 34 numbers and ask about the middle one. "Is the number between 34 and 66 inclusive?" So your ranges go from size 100 to 34 (in the worst case) to 12 to 4 to 2 to 1.

Answer 8

If we assume that you can only ask the question, "Is the number XXX too high, or too low?", (for the purpose that "correct" will instantly let you know the answer), then there are three possibilities:

1. Correct
2. Too high
3. Too low

Thus, if you had one guess, you can know the number in one guess if the number was between 1,2,3. (i.e. The probability space of the number is a set of at most 3 numbers) It follows that you can guess the number in two guesses.

If you had two guesses, the first guess could go three ways:

1. Correct
2. Too high
3. Too low

If the first guess is too low or too high, there must be at most 3 numbers remaining for you to know the number in another guess. Thus, there can be at most 7 numbers.

Similarly, 15 numbers can be uniquely separated in 3 guesses, 31 in 4, 63 in 5, and 127 in 6. Thus it takes 6 guesses to know the number.

However, it will take 7 guesses to guess the number.

If you can ask questions such that when answered with "correct", there can still be possibilities (like in this answer), then 9 numbers can be uniquely separated in 3 guesses, and 5 guesses to know the number is sufficient as $3^5=243>100$.

If the question is to maximize the probability of guessing the number correct in 6 moves, the method is subject to change. (probably)

Answer 9

Nobody quite has the right answer to why this is impossible in less than seven questions (assuming you're restricted to asking about single numbers).

Here is why. Whatever number you pick first, there is some chance that the answer will be on the "big" side; the smallest you can make the big side is 50. (E.g. if you guess "51" then "52-100" is the small side (49 numbers) and "1-50" is the big side (50 numbers). Ask again and your best worst case is 25. Then 12. Then 6. Then 3. You've just used 5 guesses, but you still have 3 numbers left to pick between. Can you always state the correct one? Nope! It could be any of those 3.

If you get one more guess you can get the worst case down to 1 number, which means you've got it. So this proves (well, illustrates, as this isn't a formal proof) that it is impossible in 6 guesses but is possible in 7.

(Note that, if you allow guesses at ranges, the answer is different. You can, by carefully selecting your ranges, go from 100 to 34 at worst (by stating "the number is between 34 and 67") on your first go. Second gets you down to 12. Then 4, then 2, then 1. So you can always do it in 6.)

Answer 10

I think you can do it with 6.72 on average. Start with the above 50 question, then split again with the above 25 question. Now, if it less than 25, 'ask is it 16 or under?'. If it is then it takes 4 more guesses (2^4=16). If it is above you have 9 possibilities. 7 of these take 3 guesses (for example 'if it is less than or equal to 20?' and we know it is more than 16, then that's 2 more guesses, so 3 in total). And 2 of them take 4 guesses (for example, 'is it greater than 23', still leaves 23 and 24).

We then do the same for the branches between 26 and 50, 51 and 75 and 76 and 100.

So to sum up, we have 7 * 16 * 4+ 6 * 7 * 4+ 7 * 2 * 4 all divided by 100 gives 6.72 questions on average.

Answer 11

(Lateral thinking)

I have a strategy that guarantees guessing the number in 3 guesses:

First guess 11
    Higher -> second guess 100
    Lower  -> second guess 10
        Lower -> third guess 1

The question didn't mention the number base so I proclaim that we are using binary numbers.