A game show picks a number from 1 to 100. You can send the host a list of "yes" or "no" questions. As an example, one of the questions can be "Is the number odd?". The host of the show answers the questions honestly in a random order, but does not tell the player in what order he answered the questions. Find, with proof, the smallest number of questions that you need to ask to determine with absolute certainty the chosen number.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ Because it's come up in an answer: what about if a question's answer is unknowable, thus the host can't answer "yes" or "no"? I can imagine you can come up with clever questions for which there is a "I don't know" answer. For example "If I at random add either 1 or 3 to your number, will the result be a prime number?". if the number is 9 it would result in no, 10 would result in yes, 12 in "I don't know" - @Ivo $\endgroup$– bobbleCommented Nov 18, 2022 at 16:20
-
1$\begingroup$ I suppose those types of questions would not be allowed. $\endgroup$– NielIGuessCommented Nov 18, 2022 at 16:46
-
$\begingroup$ So this game show. It is popular? $\endgroup$– Boba FitCommented Nov 18, 2022 at 21:33
-
$\begingroup$ @Boba Fit, presumably yes $\endgroup$– NielIGuessCommented Nov 18, 2022 at 22:09
-
1$\begingroup$ I suppose it's disallowed to ask self-referential questions. Otherwise, if you could ask something like "Is exactly one of the following true: (a) The number is 37 (b) The answer to this question is no?" then the only way for the host to give a consistent answer is to change their choice to 37, and then answer either "yes" or "no". $\endgroup$– Daniel ScheplerCommented Nov 19, 2022 at 21:00
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
The information we get from the host is simply:
The number of "yes" (or the number of "no", doesn't matter since the number of questions is fixed). This is because we get back a collection of unordered "yes" or "no". So the only information we get is just the number of "yes".
To be able to distinguish 100 numbers, we need at least 100 different responses. Therefore:
We need at least 99 questions (number of "yes" can be 0-99, 100 possibilities).
Which can be easily achieved by asking a series of questions in the form of:
"Is the number strictly larger than N?" with N ranges from 1 to 99.
Then to guess the host's number, we can simply respond with:
The number of "yes", plus 1. So 0 "yes" means the hidden number is 1. 31 "yes" means the hidden number is 32. And 99 "yes" means the hidden number is 100.
$\begingroup$
$\endgroup$
5
An answer based on this consideration
Show host has memory and can count
I think the smallest number of questions is
7
This is due to the fact that:
One can use binary search exploiting the memory of the show host
The questions are:
It is the same question submitted 7 times.
If this is the first question you are answering, is the number between 50-100? If this is the second question you are answering, is the number between 25-49 or between 75-100? If this is the third question you are answering, is the number between 12-25 or between 37-49 or between 63-75 or between 87-100? ... if this is the seventh question you are answering, is the number between (a list of ranges) ? Basically unroll the binary tree.
Or simplify:
Is the a_th bit of your number equal to '1'? where a_th is the number of questions answered before
-
7$\begingroup$ This does require that you receive the answers in the same order that the host answered them, but for the question as it is currently written that does seem to be the case. Nice loophole! $\endgroup$ Commented Nov 18, 2022 at 20:34
-
1$\begingroup$ While this was not the intended solution at all, it does seem to work. I'll allow it. Great loophole. $\endgroup$ Commented Nov 18, 2022 at 22:07
-
2$\begingroup$ Basically forces the host to answer in a single specific order, nice. Haha. $\endgroup$– justhalfCommented Nov 19, 2022 at 9:07
-
2$\begingroup$ I love this answer. I do feel bad for that game show host, if you use the first formulation. $\endgroup$– anonCommented Nov 20, 2022 at 21:26
-
$\begingroup$ @Nic, I think the first formulation is better for the host, since he can compare directly to the list given. In the second one he needs to do some calculation, haha $\endgroup$– justhalfCommented Nov 21, 2022 at 14:18
$\begingroup$
$\endgroup$
Here's a simple and concise interrogation that can't be beat:
Ask this question 7 times: "In the binary representation of the number, is the least significant digit that you have not told me anything about yet one?"
This uses the same underlying mechanism as some of the other answers, but (a) it is much easier to ask, and (b) I thought of it before reading those other answers anyway!
You can bail out early if...
...by the sixth question, the answer is already over 36.
$\begingroup$
$\endgroup$
2
I don't know what questions that might be and this might be a bit cheaty but...
The total number of questions
would be 15.
The questions would have to be worded in such a way that the host has to either answer Yes, No, or N/A. for example:
Is the number such that 1/N-2 is equaled to 1?
for 3 the answer is Yes, for 1 the answer is No and for 2 the answer would be N/A since dividing by zero is impossible.
Having 15 questions will give us a result of 105 unique number of responses. for example all 15 yes, or 12 yes, 2 no and 1 N/A.
-
10$\begingroup$ The answer to "is 1/0 = 1" is "No". 1/0 is not defined, and thus not equal to anything. $\endgroup$– SneftelCommented Nov 18, 2022 at 11:30
-
9$\begingroup$ While your example is maybe not good, I can imagine you can come up with clever questions for which there is a "I don't know" answer. For example "If I at random add either 1 or 3 to your number, will the result be a prime number?". if the number is 9 it would result in no, 10 would result in yes, 12 in "I don't know". $\endgroup$– IvoCommented Nov 18, 2022 at 12:16
$\begingroup$
$\endgroup$
1
The smallest number of questions is
7
Why can't it be smaller than this?
Each response from the host gives you 1 bit of information: a yes or a no. If the smallest number of questions was fewer than 7, say 6, then it would mean that the answer would be determinable from only 6 bits of information. But 2^6 is 64, which means there are only 64 possible responses the host could give to your set of 6 questions, which is a contradiction.
What are the questions?
Any question to which the answer "yes" or the answer "no" excludes as close as possible to half of the remaining possible solutions. A simple example: "Is the number in the range 1-50?" Yes. "Is the number in the range 1-25"? No. "Is the number in the range 25-37"? No. "Is the number in the range 38-43"? No. "Is the number in the range 44-46"? No. "Is the number 47"? No. "Is the number 48"? No. Then the number must be 49.
-
15$\begingroup$ I think you missed that part: "The host of the show answers the questions honestly in a random order, but does not tell the player in what order he answered the questions." You will get all your answers at the same time, so your strategy of question 1 - Answer 1 - Question 2 - Answer 2 , etc, is not available. $\endgroup$– EvargaloCommented Nov 18, 2022 at 13:41