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.
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.
An answer based on this consideration
Show host has memory and can count
I think the smallest number of questions is
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.
Is the a_th bit of your number equal to '1'? where a_th is the number of questions answered before
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.
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.
The smallest number of questions is
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.