4 Attempts to Guess a Number Between 1-15

Question

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.

Answer 1

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,... 2ⁿ)

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

See Mystery Calculator Trick

Answer 2

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.

Answer 3

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

Answer 4

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:

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.

Answer 5

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.

Answer 6

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?

Answer 7

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?