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.
$\begingroup$
$\endgroup$
9
-
$\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$– AlexCommented Nov 25, 2019 at 16:18
-
1$\begingroup$ What do you mean by combination of numbers? $\endgroup$– DuckCommented Nov 25, 2019 at 16:45
-
5$\begingroup$ Yes, binary search. $\endgroup$– smciCommented Nov 26, 2019 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$– VepirCommented Nov 27, 2019 at 10:34
-
2$\begingroup$ It is presumed you mean integers or natural numbers, so you might want to state that. $\endgroup$– Patrick SzalapskiCommented Nov 27, 2019 at 16:50
|
Show 4 more comments
7 Answers
$\begingroup$
$\endgroup$
16
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)
Homework: Can you do a number between 1 and 31 in 5 questions?
answered Nov 25, 2019 at 16:48
-
6$\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$ Commented Nov 26, 2019 at 0:34
-
4$\begingroup$ @JongeRoge is this a homework question? $\endgroup$– KatCommented Nov 26, 2019 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$– ikegamiCommented Nov 26, 2019 at 16:16
-
3$\begingroup$ @ikegami: I can do 1...32 in 5 questions ;) $\endgroup$– AdrianoCommented Nov 26, 2019 at 16:29
-
3$\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$ Commented Nov 26, 2019 at 16:59
$\begingroup$
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.
$\endgroup$
3
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.
answered Nov 25, 2019 at 19:38
-
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$– FabichCommented Nov 25, 2019 at 20:53
-
1$\begingroup$ @Fabich it doesn't have to be a power of two to work, but that is the limit. $\endgroup$ Commented Nov 25, 2019 at 20:54
-
3$\begingroup$ In practice, this is the simplest and most straightforward way to achieve it. Hands down. +1 $\endgroup$– StivCommented Nov 25, 2019 at 22:18
$\begingroup$
$\endgroup$
16
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 :)
-
2$\begingroup$ Nice. Rewrote mine in similar way to make it age appropriate. $\endgroup$ Commented Nov 25, 2019 at 17:18
-
$\begingroup$ @ChrisCudmore Brill - love your 'Homework' line! :) $\endgroup$– StivCommented Nov 25, 2019 at 17:19
-
1$\begingroup$ Its good pedagogy... Give a solution and ask them to extend it. $\endgroup$ Commented Nov 25, 2019 at 17:20
-
$\begingroup$ Thank you very much! But why did you choose these combinations? What is the explanation behind it? $\endgroup$– user64031Commented Nov 25, 2019 at 17:24
-
$\begingroup$ @JongeRoge Just added a line to the second block above - take a look now :) $\endgroup$– StivCommented Nov 25, 2019 at 17:25
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ This is actually a simpler answer. Upvote it. $\endgroup$ Commented Nov 26, 2019 at 17:02
-
$\begingroup$ My picture got deleted :( it illustrates the point pretty well. $\endgroup$– IsselCommented Nov 26, 2019 at 19:59
-
2$\begingroup$ Isn't this the same as @WeatherVane 's answer? $\endgroup$– CSMCommented Nov 26, 2019 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$ Commented Dec 3, 2019 at 10:42
$\begingroup$
$\endgroup$
3
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.
answered Nov 25, 2019 at 17:29
-
$\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$– nomenCommented Nov 27, 2019 at 18:41
-
$\begingroup$ Very interesting, how do you use it for searching through records efficiently? $\endgroup$ Commented Nov 27, 2019 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$– nomenCommented Nov 27, 2019 at 21:11
$\begingroup$
$\endgroup$
5
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?
-
$\begingroup$ It's a bit pedantic, but you haven't shown that your program always terminates after 4 guesses. $\endgroup$ Commented Nov 27, 2019 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$ Commented Nov 27, 2019 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$ Commented Nov 28, 2019 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$ Commented Nov 28, 2019 at 8:14
-
$\begingroup$ @OleTange Sorry about my comment, then. I thought maybe you didn't see the restriction. $\endgroup$ Commented Dec 3, 2019 at 8:48
$\begingroup$
$\endgroup$
1
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?
-
$\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$ Commented Nov 29, 2019 at 9:51