At a quiz show there are three doors. Behind exactly one of the doors, a prize is hidden. You may ask the quizmaster whether the prize is behind the left-hand door. You may also ask whether the prize is behind the right-hand door. You may ask each of these two questions multiple times, in any order that you like. Each time, the quizmaster will answer ‘yes’ or ‘no’. The quizmaster is allowed to lie at most $10$ times. You have to announce in advance how many questions you will be asking (but which questions you will ask may depend on the answers of the quizmaster). What is the smallest number you can announce, such that you can still determine with absolute certainty the door behind which the prize is hidden?
Problem
Source: Dutch NMO 2018 p5
Tags: combinatorics, minimum, game
07.09.2019 13:27
The smallest number of questions that suffices is 32. First we will show a strategy to locate the prize in only 32 questions. Start by asking the quizmaster if the prize is behind the left-hand door. Repeat this until you are sure whether the prize is there or not. You can only be 100% sure when you have received the same answer 11 times, because the quizmaster can lie a maximum of 10 times. After doing this, suppose that the quizmaster has lied n times. This means that you have thus far asked 11 + n questions and the quizmaster is entitled to 10 − n more lies. Now ask the quizmaster whether the prize is behind the right-hand door, and keep asking this until you are 100% sure of the true answer. Since the quizmaster can lie only 10−n more times, you need at most 2(10−n)+1 = 20 − 2n + 1 questions for this. In total you have now asked 32 − n questions. We conclude that with this strategy, 32 questions always suffice. Having only 31 questions, it is not always possible to locate the prize. We will show how the quizmaster can make sure of that. At the beginning, as long as you have asked about both doors at most 10 times, he always answers ‘no’. To keep it simple, we assume that the left-hand door is the first door that you query for the eleventh time (the other case is completely analogous). We consider the situation that the prize is not behind the left- hand door (which may happen). In this case, we show that the quizmaster can make sure that after 31 questions, you cannot tell whether the prize is behind the middle door or behind the right-hand door. So far, the quizmaster has been speaking the truth about the left-hand door, and he will continue to do so: when asked about the left-hand door, he will always answer ‘no’. For the right-hand door, the quizmaster will keep saying ‘no’ up to and including the tenth time he is asked about this door. The next ten times he is asked about this door, he will answer ‘yes’. Since you ask at most 20 questions about the right-hand door (since you already queried the left-hand door at least 11 times), the quizmaster needs to lie at most 10 times. Whether the prize is behind the middle door or behind the right-hand door, in both cases the quizmaster gives the same 31 answers. Therefore, you cannot determine the door behind which the prize is located.