11
$\begingroup$

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.
$\endgroup$
3
  • $\begingroup$ The distribution is not binomial n 0.5, unless there are other parameters you aren't mentioning. It depends on her initial bet strategy (let's face it, this is a game theory problem) and also the distribution of correct answer. One approach might be to answer "No" for every question on a first pass. The actual correct answer may be "No" to every question. $\endgroup$
    – AdamO
    Oct 9 '19 at 14:26
  • $\begingroup$ @bounty / Martijn / a bit meta: I don't understand -- why is that a question with too little attention? First it is a well known problem from "game theory", with several specific solutions. Second, why is the best answer is from the same person as the bounty (I really don't mind much handing points out). But anyhow I'm not sure if the real questions from the OT are answered. There still seem to be open ones about the conditions and implications of the game itself. $\endgroup$
    – cherub
    Oct 17 '19 at 15:26
  • $\begingroup$ @cherub I am trying to get rid of my reputation score. I actually wanted to bounty tens of questions but I got stuck with only three. $\endgroup$ Oct 18 '19 at 15:09
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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).

$\endgroup$
4
+100
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.).

$\endgroup$
1
  • $\begingroup$ Thanks for the hint! My money is on changing the first $\frac{n}{2}$, because doing so minimizes the correlation between the first and second retakes. I'm going to do some math to verify it, though. $\endgroup$
    – nalzok
    Oct 2 '19 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.