Getting all answers correct by taking the same exam for fewest times

Question

Rain never studies, so she is completely clueless during the midterm even though it consists of Yes/No questions only. Fortunately, Rain's professor allows her to re-take the same midterm as many times as she wants, but he only reports the score, so Rain don't know which problems she got wrong. How can Rain get all answers correct by re-taking the exam a minimal number of times?

To put it more formally, the exam has a total of $n$ Yes/No questions, whose correct answer is $X_1, X_2, \dots, X_n \stackrel{iid}{\sim} \text{Bernoulli}(0.5)$. I want to find a strategy which minimizes the expected number of times Rain needs to re-take the exam.

I have been thinking about it for a while. When Rain takes the midterm for the first time, her score will always have a distribution of $\text{Binom}(n, 0.5)$, regardless of her answer, so each strategy decreases the same amount of entropy. I have no idea what this means, though. Does it mean that any random guess is as good as answering all "Yes" or all "No"?

While this is not a homework question, I'm planning to base my next research project around it, so

1. Please provide some hints instead of a full-blown answer;
2. If this question has already been answered, please give me a pointer.

Answer 1

This is similar to the game Mastermind.

There is a lot of literature on this topic. For that specific case (4 questions with each 6 options) several strategies have been devised that reduce the average number of takes to a bit above 4.3.

You could pick out one of those strategies or make a new one and apply it to the case of $n$ questions with $2$ options, which is your situation. The question is too broad to provide a detailed answer here.

Answer 2

This is an optimisation problem where you seek to find an unknown $n$-digit binary number from guesses, where the feedback from those guesses is that you receive the number of correct digits. This is essentially just binary Mastermind, which is also examined in a computational problem called "black-box optimisation" (see e.g., Doerr et al 2001).

Answer 3

As others have said, the problem is very similar to the game Mastermind. Suppose that the correct answers are binary variables $c_i$ for $i = 1, \ldots, n$ and that Rain takes the test $k$ times, at time $j$ answering $x_{i, j}$ to the $i$-th question ($i \le n, j \le k$). The total correct answer to the $j$-th time is $T_j$.

What follows are just some observation and notes, based on the OP explicit request to only provide some hints about the problem.

1. Note that an easy "information-theoretic" lower bound on $k$ for a generic configuration of correct answers is $k \ge O(n / \log n)$: each test provides Rain with a number $0 \le T_j \le n$, which amounts to $\le \log n$ bits of knowledge, while the required knowledge to know all the answers is ~$n$ (because of the $n$ binary questions).

2. In the general case you can define variables $z^Y_i$ and $z^N_i$ to be $0$ or $1$ respectively if the $i$-th correct answer is Yes or No. In such a way your problem is to determine the point of correct answers in a "discrete" linear space of dimension $2n$: to see why consider that by the above definition of variables you have the constraints $$ z^Y_i + z^N_i = 1 $$

   Moreover, at your $j$-th take of the exam, you are testing a linear combination of such variables and you know that their sum is $T_j$: $$ \sum_{i = 1}^n z^{Y/N}_i = T_j$$

   This highlights that it is trivial to solve such problem in $n$ queries because by taking the test $k$ times you have $n + k$ equations defining a point in a $2n$ dimensional space, so that if you are smart enough in not making redundant queries (just change your answers one at a time) you can take only $n$ times the quiz.

3. In particular cases (such as when the yes/no ratio is particularly unbalanced) it should be easy to come up with particularly suited heuristics: suppose by example you know that there is only one Yes answer in the entire quiz. You can then find it in just $\log n$ queries by standard bisection on the answer sets. Moreover you can check if you are in such a case by issuing an "all-yes" first query (in which case $T_1 = 1$).

4. By generalizing the idea in the previous bullet point, If the number of Yes answers is $C$ (suppose $C \le n/2$) (and this can become known by a single query), you are basically searching a set of size $C$ inside a set of size $n$ (thus there are $\binom{n}{C} \simeq n^C$ of them) and your query consists in knowing the cardinality of the intersection of one set $S$ of your choosing with said set of Yes questions, which I think is a much more studied problem and you can probably find many references on it.

   Call the set you are tring to find (Yes answers) $Y$. With a single query you can know its cardinality $|Y| = m$. Now a randomly selected set $S$ used as query allows you to know the cardinality of the two subsets $|Y \cap S| = t$ and $|Y \cap S^c| = m - t$, and your original problem has been reduced to two subproblems of roughly half the size (also the number of sought Yes answer will usually halve at each iteration). I won't write explicit details, but it is just a matter of simple probability calculations.

   Exploiting the above observation, you should came up with a probabilitic algorithm that solves the subproblem $P(m, n) \simeq\le 1 + 2 * P(m/2, n/2)$, which should get you a bound of $O(m \log n)$. Coming up with a deterministic algorithm for such problem may be done using the technique of maximized expectations, but I can't foresee if it would work or not.

Answer 4

Do you want to minimize the maximum number of retakes? or minimize the expected number of retakes?

You could come up with very different strategies depending on which you want to look at.

A first step naive approach would take up to $n+1$ times and would consist of taking the test the first time, then on the second time taking the test change only the first answer, If the score goes up then keep the new answer, if it goes down go back to the first answer for all future steps. On the 3rd time (2nd retake) change only the 2nd answer, etc.

Now you can start comparing other strategies to that one. If on the 2nd time taking the test 2 answers are changed, then if the score changes we know the correct answers for 2 questions and have saved a step, but if we changed one to be correct and the other to be wrong then the score does not change and we do not know which change was correct until we take the exam a 3rd time changing only one of them (but that will tell us about the other as well), so either 1 or 2 retakes to get 2 answers (50% chance of each) which will reduce the expected number of retakes, but probably keep the maximum the same.

Now you can look at other strategies and see how they compare (change the 1st 3 answers, change the first $\frac{n}{2}$, etc.).