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.

  • 1
    @warspyking: can I ask "it's between 33 and 66"? Answers: right, too low, too high... "It's between 11 and 22?" "It's between 4 and 8?" – woliveirajr Oct 21 '14 at 19:21
  • 2
    It would have been amazing if somebody came up with a way to do this is < 7 attempts. It'd be like someone unknowingly proving that P=NP in an attempt to solve some silly riddle. The funny thing is that any CompSci PhD would immediately say "no, it's impossible" but an amatuer puzzle solver might try to come up with an answer... and maybe they would find one! Not knowing what is "impossible" can be really powerful. – Gray Oct 22 '14 at 18:56
  • 1
    @Gray I was thinking the same thing – d'alar'cop Oct 23 '14 at 12:32
  • 5
    @Gray This would do more than prove P=NP. It would violate the pigeonhole principle and thus prove large portions of math inconsistent. – Taemyr Nov 5 '14 at 14:19

11 Answers 11

up vote 31 down vote accepted
+500

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.

  • That's my 7 strategy, I'm wondering if there's a faster way. – warspyking Oct 20 '14 at 21:13
  • Oh and the number is never a decimal so after it's too low for 25, then it'll be 12, or if it's too high it's be 38, the point is to make it even. – warspyking Oct 20 '14 at 21:15
  • 2
    That's the same bound. If $n=2^m$, $\lceil\log_2(n+1)\rceil=m+1=\log_2n+1$. If $n$ is not a power of $2$, $log_2n$ is not entire and $\lceil\log_2(n+1)\rceil=\lceil\log_2n\rceil=\lfloor\log_2n\rfloor+1$. – Dennis Oct 21 '14 at 4:46
  • 3
    @Twinkles That's "Big-O" or "Landau" notation. It is used in Computer Science to express the "complexity" or computational cost of an algorithm. The reason it's used here is because it expresses that the algorithm is efficient and highlights that a search algorithm with better than that "efficiency"/"computational cost" is not known for this problem - that supports the argument of optimality of the solution. – d'alar'cop Oct 21 '14 at 9:41
  • 3
    @miracle173: Good points. But binary search is, in fact, provably optimal in the worst case (see stackoverflow.com/q/7578709) – Nemo Dec 3 '14 at 21:55

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.

  • 2
    good god you're right. – d'alar'cop Oct 20 '14 at 23:20
  • 8
    Six guesses may be enough to tell you what the number is, but knowing the number isn't enough. You still have to say it, which potentially counts as your 7th attempt. – cHao Oct 20 '14 at 23:34
  • @cHao Exactly why this has not been marked accepted answer ;D – warspyking Oct 20 '14 at 23:49
  • haha... I must be on 1st gear today :p – d'alar'cop Oct 21 '14 at 0:08
  • @warspyking atleast frodoskywalker told you "Yes" :) so +1 from me though in essence its almost the same answer – skv Oct 21 '14 at 5:25

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.

  • I have totally same answer, because correct, to high, to low are 3 different info, so trinary should be use. – jwall Oct 22 '14 at 1:28
  • 1
    I think the OP means 'guess a number', not 'is the following hypothesis correct, too high or too low' – Seb Oct 22 '14 at 17:03

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.

  • 9
    Nitpick: you do get a little more than one bit of data. Besides "too low" and "too high", there's also "correct!". (That still doesn't reduce the search space enough in this case...but if the question were between 1 and 70, it could make all the difference.) – cHao Oct 20 '14 at 23:46
  • 5
    70 would be too much. 63 is the actual maximum. 1 question: 1 value. 2 questions: 3 values. 3 questions: 7 values, etc. You get 6 questions: 63 values. – Florian F Oct 20 '14 at 23:49

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)

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.

  • 2
    Technically asking about the digits would still be 7 questions because even though you know the digits you have to still confirm the number is correct. Otherwise the binary search method would also give you the answer in 6 guesses. – kjbartel Oct 21 '14 at 4:22
  • Heck, you're right. – Matt Malone Oct 21 '14 at 14:15

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$.

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.)

(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.

This is what I did to guess the number between 1and 100. Guess 1: 50 Less than Guess 2: 25 Greater than Guess 3: 38 Greater than Guess 4: 44 Greater than Guess 5: 47 Less than The time is than of I write 45 it is going to be higher. If I write 46 it is going to be lower. Guess 6 45 Greater than That means the answer has to be 46 Guess 7: 46 Right Yes I finally guessed your number I won.

One thing I don't like to do anymore is to start with the number of 50. For a while, I was favoring starting with 48. But right at the moment that I'm wrote this text, my preferred first number would be... 32.

Yeah, that runs me into trouble a bit over a third of the time, but I'm currently thinking that is better (more rewarding) than any other approach I've tried so far.

Now, I happen to have studied this a bit, and, as I said, I wish to share my analysis with no further delay:

][CyberPillar][ Legend of the Red Dragon sub-section: guessing a number in six tries

(It's a sub-section of the LoRD page, which shows some output from the mini-game I described momentarily.)

I've actually tried this puzzle numerous times before, because this is essentially a mini-game within a larger game called "Legend of the Red Dragon". For those who don't know about "Legend of the Red Dragon", it was a multiplayer computer game that was installed on many BBSs. A BBS was a computer system that acted like a server for people using "dial-up" modems to connect directly to servers via phone lines, which was a common approach before widespread Internet access had people connecting to centralized sources that relayed information through multiple servers.

So, there's every reason to believe/suspect that the original poster may have been seeking to gain some advantages in a game.

To all those who used information theory, binary logic, tree splitting, and describing functions like “ $\lceil \log_2 (n+1)\rceil$ ”, I thank you for your input. And, I mean that sincerely: you provided details to answer the question that was asked, and so your answer was entirely on-topic and an appropriate answer to the question that was asked. So your answers were not wrong; they just aren't as useful for every possible usage scenario, including the scenario that I just brought up. But their answers were completely suitable for the question that was originally asked, and would be more useful in other scenarios.

Such answers not only answered the question that was asked, but help to provide additional information. For instance, such approaches lets us know, "what is a minimum number of guesses that would be required to guarantee a successful guess?" And, strategies of simply splitting the numbers may result in getting really, really close after six guesses. The final permitted guesses may be so close, in fact, that the next guess would be an absolutely guaranteed right answer. These seem like things that could be useful in some scenarios, so I don't wish to dismiss the good of the approaches that were taken.

That's all nice and interesting information. However, I wished to share my analysis, because it provides some more details that would be helpful to answer another question: "What is the strategy that will provide the right answer most of the time?" Because, you see, in the embedded mini-game I'm referring to, we really don't care about getting close to the right answer. That might be great for some usage scenarios, where guessing a number that is close to being accurate is way, way better than a number that is way, way far away from being accurate. However, in the usage scenario I'm describing, all we care about is getting 100% accurate as often as possible. Because, getting the accurate answer leads to the embedded mini-game providing a reward, and being even slightly inaccurate results in no reward whatsoever. A series of six missed guesses results in a failure, and there is no rewarded benefit for being close. Complete perfection, achieved within the stated limits, is absolutely the only thing that is cared about at all.

Granted, getting close might seem just a bit emotionally satisfying, but it doesn't provide any additional advantage over wildly wrong answers. So, in the cases where perfection doesn't get achieved, then there is no reason to try to avoid being wildly wrong.

One reason I think my results are nice to be able to see is because I ended up making a bit of a chart. This chart helps to be able to visualize how big the clumps of un-guessed numbers are. I think that this visual presentation can be pleasant, and might even be useful for someone who wishes to contemplate this in hopes of coming up with a better strategy.

Many people probably have the initial inclination to use each available guess to try to split the task into half. I found that approach (Method #1) does not seem to be the approach that maximizes winning. Using Method #1, the sixth guess will often provide the guesser with odds of one in two, or even one in three. However, when using Method #3, the guesser seems to be getting better overall odds of winning. A person could say that the guesser ends up being way more off-track from getting the final answer, because the guesser is left in a situation of being nowhere close to having the final answer in the next guess. However, if the goal is simply to maximize the number of times that correct guesses are made, then Method #3 seems to be the superior approach than starting the first guess at 50. So, as can often be the case in real life, which method seems best may depend on what goals are being pursued.

  • 2
    But exactly what's the method... – warspyking Jan 6 '15 at 2:18
  • @TOOGAM Binary search, starting at 50 or 51, has a 63% chance of hitting the correct number. This is optimal, no method can give better odds. – Taemyr Jan 7 '15 at 11:52
  • @TOOGAM The goal at each step is to divide the sets into equal sizes. 50, unless correct, divides into either 1-49(49 choices) or 51-100(50 choices) - meaning that you are left with 50 choices in the worst case. 48 is bad because it divides into 1-47(47 choices) and 48-100(52 choices) - meaning that you are left with 52 choices in the worst case. Because we are quite far away from 127 this will not actually matter in terms of probability for hitting the correct answer. – Taemyr Jan 7 '15 at 12:02
  • The flaw in your logic is this line "method #1 does allow for an additional 5 numbers to be guessed before getting to the point of having a 50/50 chance, which ups the chances of method #1 to 55%." Those 5 numbers contribute more than 5% chance of overall sucess, because they are made incorporating the information from earlier guesses. (Look at your table for the method, there are 31 instances of guess1 through guess5 so you have 31% chance to be correct in one of the first 5 guesses.) – Taemyr Jan 7 '15 at 12:16
  • @warspyking Binary search but shift your guess so that if the guess is too high you are guaranteed to suceed with the number of guesses you have left. Eg. if you have 1 guess left choose the minimal value, if 2 guesses choose minimal value+1, if 3 guesses choose minimal value+3, if 4 guesses then minimal value+7 etc. This does happens to be the farthest you can shift your guess without hurting your probability of finding the correct number in the available number of guesses, so I would describe it as the worst optimal strategy. – Taemyr Jan 7 '15 at 12:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.