20
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ stackoverflow.com/questions/9605110/… AND math.stackexchange.com/questions/98344/… $\endgroup$
    – d'alar'cop
    Oct 20, 2014 at 22:02
  • 2
    $\begingroup$ @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?" $\endgroup$ Oct 21, 2014 at 19:21
  • 2
    $\begingroup$ 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. $\endgroup$
    – Gray
    Oct 22, 2014 at 18:56
  • 1
    $\begingroup$ @Gray I was thinking the same thing $\endgroup$
    – d'alar'cop
    Oct 23, 2014 at 12:32
  • 6
    $\begingroup$ @Gray This would do more than prove P=NP. It would violate the pigeonhole principle and thus prove large portions of math inconsistent. $\endgroup$
    – Taemyr
    Nov 5, 2014 at 14:19

11 Answers 11

32
+500
$\begingroup$

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.

$\endgroup$
23
  • $\begingroup$ That's my 7 strategy, I'm wondering if there's a faster way. $\endgroup$
    – warspyking
    Oct 20, 2014 at 21:13
  • $\begingroup$ 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. $\endgroup$
    – warspyking
    Oct 20, 2014 at 21:15
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Dennis
    Oct 21, 2014 at 4:46
  • 3
    $\begingroup$ @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. $\endgroup$
    – d'alar'cop
    Oct 21, 2014 at 9:41
  • 3
    $\begingroup$ @miracle173: Good points. But binary search is, in fact, provably optimal in the worst case (see stackoverflow.com/q/7578709) $\endgroup$
    – Nemo
    Dec 3, 2014 at 21:55
27
$\begingroup$

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.

$\endgroup$
11
  • 2
    $\begingroup$ good god you're right. $\endgroup$
    – d'alar'cop
    Oct 20, 2014 at 23:20
  • 8
    $\begingroup$ 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. $\endgroup$
    – cHao
    Oct 20, 2014 at 23:34
  • $\begingroup$ @cHao Exactly why this has not been marked accepted answer ;D $\endgroup$
    – warspyking
    Oct 20, 2014 at 23:49
  • $\begingroup$ haha... I must be on 1st gear today :p $\endgroup$
    – d'alar'cop
    Oct 21, 2014 at 0:08
  • 1
    $\begingroup$ @AdamDavis, what do you mean by "only affects the number of guesses ... far too late to remove a whole guess"? This method guarantees a correct guess 7 (and you're guaranteed to know the number after guess 6) vs binary search guaranteeing a correct guess 8 and letting you know after 7. $\endgroup$ Oct 22, 2014 at 18:28
17
$\begingroup$

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.

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

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.

$\endgroup$
2
  • 9
    $\begingroup$ 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.) $\endgroup$
    – cHao
    Oct 20, 2014 at 23:46
  • 6
    $\begingroup$ 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. $\endgroup$
    – Florian F
    Oct 20, 2014 at 23:49
4
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – kjbartel
    Oct 21, 2014 at 4:22
  • $\begingroup$ Heck, you're right. $\endgroup$ Oct 21, 2014 at 14:15
2
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ This appears to be the same method as proposed before in other answers, and the same overall conclusion ("not possible in 6 moves") $\endgroup$
    – bobble
    Aug 27 at 1:23
  • $\begingroup$ It is a similar method, but I couldn't find any of the above answers which had worked out the average guess or thought about the details to get that as low as possible. But maybe I missed something. $\endgroup$ Aug 28 at 6:09
-1
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ I need zero guesses. The number is 10. The base is the number they thought. $\endgroup$ Jun 10, 2020 at 12:21
  • 1
    $\begingroup$ This is clearly not in the spirit of the question $\endgroup$
    – bobble
    Aug 26 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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