16
$\begingroup$

Is there a way to find a number between 1-15 in 4 attempts? In each attempt you can guess a range / combination of numbers and you will get an answer if the number is in that range / combination or not. You are not allowed to ask directly which number it is. Only whole numbers are involved.

$\endgroup$
  • $\begingroup$ You might want to define your objective for your question such as "Is there a way to ensure you will get the correct number" $\endgroup$ – Alex Nov 25 '19 at 16:18
  • 1
    $\begingroup$ What do you mean by combination of numbers? $\endgroup$ – Duck Nov 25 '19 at 16:45
  • 5
    $\begingroup$ Yes, binary search. $\endgroup$ – smci Nov 26 '19 at 8:03
  • 2
    $\begingroup$ Just for fun: It can be done in only 3 guesses if you allow asking "yes or no" questions (hint: the third answer to a "yes or no question" would be "I do not know" when answering either "yes" or "no" is impossible due to unknown information or a paradox). $\endgroup$ – Vepir Nov 27 '19 at 10:34
  • 2
    $\begingroup$ It is presumed you mean integers or natural numbers, so you might want to state that. $\endgroup$ – Patrick Szalapski Nov 27 '19 at 16:50
71
$\begingroup$

Yes.
Guess 1st set (1,3,5,7,9,11,13,15) -> If the number is in the set, write down 1
Guess 2nd set (2,3,6,7,10,11,14,15) -> If the number is in the set, write down 2
Guess 3rd set (4,5,6,7,12,13,14,15) -> If the number is in the set, write down 4
Guess 4th set (8,9,10,11,12,13,14,15) -> If the number is in the set, write down 8

After all 4 guesses, add the numbers you wrote down. This will be the chosen number. 1 Appears in Set 1 only, so you will have written down 1 12 appears in Sets 3 and 4 only, so you will have written down 4 + 8 = 12. 15 appears in all Sets, so you will have written down 1 + 2 + 4 + 8 = 15.

This works based on the binary representation of numbers, that is, every number can be written as a sum of powers of 2 - {1,2,4,8,16,32,... 2n)

Table comparing the Binary values of 1 (0001) through 15 (1111) against the Binary values of 1, 2, 4 and 8 (0001, 0010, 0100, and 1000)

Homework: Can you do a number between 1 and 31 in 5 questions?

See Mystery Calculator Trick

$\endgroup$
  • 5
    $\begingroup$ This is basically a binary search. Each "level" of items (1, 2, 4, and 8) is a list of numbers that have that bit set in a binary representation of that number. $\endgroup$ – Dewi Morgan Nov 26 '19 at 0:34
  • 4
    $\begingroup$ @JongeRoge is this a homework question? $\endgroup$ – Kat Nov 26 '19 at 14:30
  • 3
    $\begingroup$ Re "Can you do a number between 1 and 31 in 5 questions?", I can do 0..31 in 5 questions :) $\endgroup$ – ikegami Nov 26 '19 at 16:16
  • 3
    $\begingroup$ @ikegami: I can do 1...32 in 5 questions ;) $\endgroup$ – Adriano Nov 26 '19 at 16:29
  • 2
    $\begingroup$ There is a variant to this puzzle that's known as "Poison" which asks you to identify a single vial of poison out of 1,000 with 10 test strips. The way that the puzzle is worded leads the solver towards Binary search; however it's important to realize that this method is not binary search because this test can be performed independent of the data set (read: can be done in parallel). The number of tests required is the strict log_2(y) = x where y is the number of "things" in your testable set and x is the number of tests required. $\endgroup$ – karnesJ.R Nov 26 '19 at 16:59
55
$\begingroup$

A simple way is to pick the number $X$ which is half-way through the range and ask

Is it less than $X$?

From the answer you can discard either the lower half or the upper half of the range.

Repeat until you have 1 number left.

This method is known as a binary search or binary chop.


In general, If you are allowed $q$ queries, you can get an answer from $2^q$ items. Here you have $4$ guesses, so you can succeed when there are $16$ or fewer items.

From the other way round, if you have $n$ items, you need $log_2 n$ guesses (rounded up).

The numbers do not need to be consecutive: just split the group into two equal size parts (or off by 1 if an odd number) and eliminate one half.

$\endgroup$
  • 1
    $\begingroup$ To generalize your answer you could add that any number X with 0 <= X < 2^n can be guessed in n attempts. It would also answer all the similar questions $\endgroup$ – Fabich Nov 25 '19 at 20:53
  • 1
    $\begingroup$ @Fabich it doesn't have to be a power of two to work, but that is the limit. $\endgroup$ – Weather Vane Nov 25 '19 at 20:54
  • 2
    $\begingroup$ In practice, this is the simplest and most straightforward way to achieve it. Hands down. +1 $\endgroup$ – Stiv Nov 25 '19 at 22:18
24
$\begingroup$

To build off @ChrisCudmore’s correct answer (go upvote it!), here is the same answer but with a simpler less technical explanation – hopefully this will be easier to understand…

All the whole numbers 1-15 can be calculated by adding some or all of the numbers 1, 2, 4 and 8, like so:

1 = 1
2 = 2
3 = 1 + 2
4 = 4
5 = 1 + 4
6 = 2 + 4
7 = 1 + 2 + 4
8 = 8
9 = 1 + 8
10 = 2 + 8
11 = 1 + 2 + 8
12 = 4 + 8
13 = 1 + 4 + 8
14 = 2 + 4 + 8
15 = 1 + 2 + 4 + 8

If you are allowed to ask four questions before then saying which number it is, you should use the following 4 questions:

1. Is it one of {1,3,5,7,9,11,13,15} – or more simply, “Is it an odd number?”
2. Is it one of {2,3,6,7,10,11,14,15}?
3. Is it one of {4,5,6,7,12,13,14,15}?
4. Is it one of {8,9,10,11,12,13,14,15} – or more simply, “Is it higher than 7?”

(The trick here is that all of the numbers mentioned in Question 1 need a '1' in their sum, all of those in Question 2 need a '2' in their sum, all of those in Question 3 need a '4' in their sum, and all of those in Question 4 need an '8' in their sum - compare them to the list above, and see for yourself.)

Now to find the number, start with 0.

If the answer to Question 1 was ‘Yes’, add 1; if ‘No’, do nothing.

If the answer to Question 2 was ‘Yes’, add 2; if ‘No’, do nothing.

If the answer to Question 3 was ‘Yes’, add 4; if ‘No’, do nothing.

If the answer to Question 4 was ‘Yes’, add 8; if ‘No’, do nothing.

The result of adding these up will be the number the other person was thinking of!

You will always get the correct answer here – try it and see :)

$\endgroup$
  • 2
    $\begingroup$ Nice. Rewrote mine in similar way to make it age appropriate. $\endgroup$ – Chris Cudmore Nov 25 '19 at 17:18
  • $\begingroup$ @ChrisCudmore Brill - love your 'Homework' line! :) $\endgroup$ – Stiv Nov 25 '19 at 17:19
  • 1
    $\begingroup$ Its good pedagogy... Give a solution and ask them to extend it. $\endgroup$ – Chris Cudmore Nov 25 '19 at 17:20
  • $\begingroup$ Thank you very much! But why did you choose these combinations? What is the explanation behind it? $\endgroup$ – user64031 Nov 25 '19 at 17:24
  • $\begingroup$ @JongeRoge Just added a line to the second block above - take a look now :) $\endgroup$ – Stiv Nov 25 '19 at 17:25
12
$\begingroup$

You can do this by splitting the range in half. If the numbers to guess from (1-16) is less than 2^X where x is the number of guesses you get. Look at the picture below, and each color is 1 guess:

Step down through the guesses

Hypothetically, the answer is 16 (I rounded up to split the numbers easier). 1. you guess 1-8, and that isn't it 2. you guess 9-12 and that isn't it 3. you guess 13-14 and that isn't it 4. you guess 15 and that isn't it.

In 4 guesses you were able to halve the numbers till you are down to 1.

This game also works if you can select only 1 number, and you are told whether it is higher or lower. In that case, you half the range with each guess.

$\endgroup$
  • $\begingroup$ This is actually a simpler answer. Upvote it. $\endgroup$ – Chris Cudmore Nov 26 '19 at 17:02
  • $\begingroup$ My picture got deleted :( it illustrates the point pretty well. $\endgroup$ – Issel Nov 26 '19 at 19:59
  • 2
    $\begingroup$ Isn't this the same as @WeatherVane 's answer? $\endgroup$ – CSM Nov 26 '19 at 21:44
  • $\begingroup$ I'm confused about the correct steps when the range does contain the correct number. Assume the correct answer, or number, is 5. Then, following your steps: 1.) *Guess range [1-8]; 2.) Answer is Yes; 3.) Split range [1-8] into [1-4] and [5-8] to check halves; 4.) Question: Ask if correct number is in [1-4] or [5-8]? Not sure... 5.) **Worst case scenario would be, * guess [1-4]; 6.) Since 5 is not in [1-4], you get a no; 7.) Split the rest of the correct range [5-8]: [5-6] and [7-8]; 8.) Now * Guess [5-6]; 9.) This leaves one guess. If we can, we can ask if it's the 6, which points at the 5 $\endgroup$ – Jamie Watts Dec 3 '19 at 10:42
2
$\begingroup$

So I can’t comment since I don’t have enough reputation yet. I just want to say that this is the coolest thing I have ever seen. I had no idea that binary could be used in such a way that you could guess a number in a certain amount of guesses 100% of the time as long as the amount of guesses was equal to the amount of digits in binary of the highest number in the range!

How Our Number System Works Binary is another way to represent a number. Our number system is in base 10, since each digit/place is in base 10. Example: the number 295 has a 5 in the 1s place (the ones place is represented by base 10 as $10^0$), a 9 in the 10’s place (the tens place is represented as $10^1$) and a 2 in the hundreds place (hundreds place is $10^2$). Notice that our normal number system is in base 10 which means the first digit “place” is 10 with exponent 0 which make it 1 (the ones place), following places are just powers of 10.

How Binary Works Binary on the other hand, uses a base 2 number system. In other words, the bases are 2, and the digit place is a power of 2. Binary uses only 0’s and 1’s since the digit places are only a power of 2. If it is base 10, you need 10 digits, binary is base 2 so 2 digits are used. Binary has a ones,($2^0$) twos($2^1$), fours($2^2$), eights($2^3$) instead of ones, tens, hundreds places from our number system. If you had 21 in base 10 (our system), and you wanted to convert it to binary, you would take the highest power of 2 you can out of 21, then represent the rest as binary until you are left with nothing (I will show you that). The highest power of 2 that you can take out of 21 is $2^4$ which is 16. So the binary for 21 would have a highest place of $2^4$(sixteens place). Once you take 16 out of 21, you are left with 5. Once again, take out the highest power of 2 you can out of what you have left (5). The highest power of 2 you can take out of 5 is $2^2$ which is 4. Once you take 4 out of 5, you are left with 1. Again, subtract the highest power of 2 you can out of 1. The highest power of 2 you can take out of 1 is $2^0$ which is 1. Once you have done that, you are left with nothing so you are done figuring out how you will structure 21 in binary. Since you subtracted out $2^4$, the number in the $2^4$ is 1, since you had to subtract $2^4$ out of 21 1 time. The next place in binary is $2^3$ which is 8. You never subtracted 8 from 21, so a 0 will go there. Next place in binary is $2^2$ which is 4. You did take 4 out of 21 after you took 16 out of 21, so a 1 will go in the $2^2$s place. Next place is $2^1$s place(equals 2), and you never took 2 out of 21, so a 0 will go there. Last place in binary is the $2^0$s place which is the ones place. You did take 1 out of 21 so a 1 goes in that place. Your final result will be 10101 representing one 1, 0 twos, 1 four, 0 eights, and 1 sixteens. Notice that 1+4+16 equals 21.

Incase you were wondering, this is where the 1’s and 0’s came from in @Chris Cudmore’s original answer.

$\endgroup$
  • $\begingroup$ This is one of the first algorithms you learn when you get a math degree. I use it about once a month to search through MILLIONS of records by hand. Takes about 20 minutes. $\endgroup$ – nomen Nov 27 '19 at 18:41
  • $\begingroup$ Very interesting, how do you use it for searching through records efficiently? $\endgroup$ – Cotton Headed Ninnymuggins Nov 27 '19 at 19:57
  • $\begingroup$ Suppose we have a list of a million records, and we want to find the last one before a change happened (like, the last record to use a kind of form, for example). To do that, start in the middle. If it changed, eliminate the upper half. If it didn't, eliminate the lower half. Continue in this way until there is only one left. $\endgroup$ – nomen Nov 27 '19 at 21:11
2
$\begingroup$

No, it is not possible.

At least not unless you put up more restrictions. E.g. that the numbers have to be integers.

None of the solutions shown so far give a way to find $\sqrt \pi$ , which is between 1-15.

If you restrict yourself to integers you can use this method:

sum = 0
s = 1
while s <= max value:
  Ask: "Is the number odd?"
  Yes: Add s to sum
       Subtract 1 from number
  Tell the person to divide number by 2
  Double s
sum is now the correct number

Or as a program:

sum = 0
s = 1
while s <= maxvalue:
  if number % 2 == 1:
    sum = sum + s
    number = number - 1
  number = number / 2
  s = s + s
print sum

Try using that to guess a number between 1 and 1023. How many guesses did that take?

$\endgroup$
  • $\begingroup$ It's a bit pedantic, but you haven't shown that your program always terminates after 4 guesses. $\endgroup$ – boboquack Nov 27 '19 at 23:29
  • $\begingroup$ Number is divided by 2 in each round which means it terminates after log2(number) rounds. log2(16) = 4, so log2(15) < 4. QED. $\endgroup$ – Ole Tange Nov 27 '19 at 23:44
  • $\begingroup$ In the question, it's stated, unless I'm mistaken, that only whole numbers are allowed. Since whole numbers are positive integers, whole numbers are an even greater restriction than just "integers" would be. $\endgroup$ – Jamie Watts Nov 28 '19 at 4:18
  • 1
    $\begingroup$ @JamieWatts That restriction was added by Cotton Headed Ninnymuggins in an edit after my first answer. Whether that is what OP meant is unknown. $\endgroup$ – Ole Tange Nov 28 '19 at 8:14
  • $\begingroup$ @OleTange Sorry about my comment, then. I thought maybe you didn't see the restriction. $\endgroup$ – Jamie Watts Dec 3 '19 at 8:48
1
$\begingroup$

There are 2 problems with trying to eliminate half of the numbers between 1-15

1st problem: you eventually narrow it down to 2 numbers at which point you have to ask about 1 specific number which isn’t allowed.

2nd problem: if the questions aren’t answered when they’re asked, but rather all 4 questions are answered after they’re all asked, then eliminating half wouldn’t work. Using binary (@Chris Cudmore) to use ranges of numbers works the best since each question isn’t dependent on the previous.

As @Ole Tange said, there needs to be more restrictions like only whole numbers, and the 4 questions are answered only after they’re all asked, eliminating the possibility of depending on each answer to formulate another question. In other words, should the 4 questions asked all be determined before asking them, or can they be formulated on the fly?

$\endgroup$
  • $\begingroup$ The first problem is a non-problem. Suppose I've narrowed it down to either 3 or 4. Then I can ask, "Is the number strictly less than 4?" or "Is it in the set {2, 3}?". This is a trivial transformation from asking whether it's a particular number. Mind you, the constraint about asking directly if it's a specific number adds no value to the problem anyway. $\endgroup$ – Toby Speight Nov 29 '19 at 9:51

Your Answer

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