# Find the Prize With a Limited Number of Questions

This question is the final step to a much more complicated question that I have spent many hours thinking about but was never able to solve so I am hoping someone here might be able to help.

The question is, there are 5 cups A,B,C,D,E , one of which has a prize underneath,

|---A---|---B---|---C---|---D---|---E---|

using only two yes/no questions is it possible to deduce where the prize is? For the sake of the game it is safe to assume that the operator of the game(the one who is answering your questions) knows where the prize is and is a highly skilled logician, so you can ask as complicated of a question as you want provided it can be answered yes or no. Are there two questions that will allow you to win everytime?

Does the problem change at all if it is 3 cups with 1 question?

Does the problem change at all if you can ask a question where the operator's answer is "I don't know" ?

• You could see this puzzling.SE question for one question and 3 cups, and this one for one question and 5 cups. Your last line is the key to both of those solutions. – Ross Millikan Jul 30 '14 at 13:01
• Note that (even if your second question should depend on the answer to the first), there are only four possible outcomes yes/yes, yes/no, no/yes, no/no from whicho you want to distinguish betwen five cups. – Hagen von Eitzen Jul 30 '14 at 13:01
• @Ross Millikan could oyu expand on you comment about the lat line being the key to the solution? – KBusc Jul 30 '14 at 13:19
• You need more than two answers, even though it started off a yes/no question. That way you get more than one bit of information from one question. That is the trick exploited in the two links. – Ross Millikan Jul 30 '14 at 13:22
• After reading the links posted by Ross it seems to me that this problem is solveable when I dont know is an answer and unsolvebable otherwise. Can someone please confirm this? – KBusc Jul 30 '14 at 13:23

## 1 Answer

I believe the answer is "no".

Think about the four possible answers you can get: Y/N, YY, NY, or YY. Each of these leads to a conclusion about where the prize might be. There are therefore at most four possible conclusions, but 5 spaces for the prize. Hence, you cannot find the prize with two yes/no questions.

(By the way, the two questions you ask needn't be predetermined for this reasoning to work; for instance, the second question could be predicated on the answer to the first...)

Added after comments: Here's a complete solution to the problem when "maybe" or "I don't know" is also allowed as an answer. The main idea is stolen directly from one of hte links Ross pointed out. Anyhow, it, together with the comments above, shows that

• if only "yes/no" questions are allowed, you cannot solve the 5 cups problem
• if "yes/no/maybe" questions are allowed, you can solve it.

Question 1: "Label the cups 0, 1, 2, 3, 4. Let's say the ball is in cup $n$, where $n$ is one of these numbers. Imagine that you flip $n$ coins. Will there be a pair of coins that are both heads or both tails?"

If the answer is "yes", then the ball must be in cup 3 or 4; if the answer is "no", then the ball must be in cup 0 or 1; if it's "maybe", then the ball's in cup 2.

[quick explanation: if the answerer flips 0 or 1 coins, then there cannot be a pair, so if $n = 0, 1$, the answer is "no". If the answerer flips 3 or four coins, even if the first two are opposites (one head, one tail), the third one will have to match at least one of them, so there's certain to be a pair, and the answer is "yes". If the answerer flips 2 coins, there might be a pair (HH, TT) or there might not (HT, TH), so the answer is "maybe."]

So:

If the answer to Q1 is "no", ask "is it in cup 0?" A "yes" means it's in cup 0; a "no" means it's in cup 1.

If the answer to Q1 is "maybe", you don't need to ask another question: it's in cup 2.

Finally, if the answer to Q1 is "yes", you know it's in cup 3 or 4. So say "Is it in cup 3?" If the answer's "yes", then it's in cup 3; if it's "no", then it's in cup 4.

(Simpler than my erroneous earlier answer, which was almost a correct way to handle a six-cup problem!)

• What about the case where I Don't know is an answer , then there are 8 possible answers and only 5 cups. Does this help you solve the problem? – KBusc Jul 30 '14 at 13:18
• Certainly it might. I was only trying to answer the first part of the question ("Can you do it with two yes/no questions?"). – John Hughes Jul 30 '14 at 13:20
• I've added a solution when "yes/no/maybe" is allowed. – John Hughes Jul 30 '14 at 17:56
• I have accepted the answer since this is well explained but it really gets fuzzy at the end when you say "If the answer to Q2 is "no", then the ball's in cup 4. If it's "maybe", the ball's in cup 5. If it's "yes", the ball's in cup 6. " Since there was no cup 5 and 6 to begin with... – KBusc Jul 30 '14 at 18:55
• I'll edit to fix -- I was off by two in my head when I wrote that part. :( – John Hughes Jul 30 '14 at 23:27