Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge

Question

A test is consisted of $N$ multiple choice questions, each has $k$ possible answers.

A test solution is the sequence of answers $S\in[k]^N$.

Given is a black box which receives a solution as input and returns the number of correct answers. After failing a test, the student may take the test again, and the questions do not change.

In order to pass the test, a student must have at least $m\le N$ correct answers.

---

• What is the minimal number of attempts you need to make (as a function of $N,k$ and $m$) in order to be sure to pass the test, assuming you have no knowledge about the questions in hand?

• Assuming you are allowed to use randomization, how can we minimize the expected number of attempts needed?

---

A trivial algorithm is to "guess" an initial solution $S_0$, and then change one answer at a time until you have $m$ correct ones. This results in $1+(k-1)\cdot m$ attempts at the worst case.

For the probabilistic part, it seems some kind of an experts algorithm could work here: pick a few random tests and then construct additional tests such that answers appearing in high-scoring solutions will get higher probability.

Answer 1

You can produce an information-theoretic lower bound by viewing the problem as a decision tree. At each step, you try some solution and get a response (0..$N$) of how many answers were correct, which leads to your next guess.

Simple case: $m=N$

Your decision tree ends with a solution that is entirely correct, and every possible solution must be represented as a leaf of the tree. Since there are $k^N$ possible solutions, and each decision branches with $N+1$ possible results, we end up with a lower bound of $\log_{N+1} {k^N} \approx N \log_N(k)$ guesses.

General case: any $m \leq N$

In this case, it is not necessary for every leaf in the decision tree to be different, but any one solution may be used at most $k^{N-m}$ times; this is because one solution can only have $\geq m$ correct answers for ${N \choose M} k^{N-m}$ different arrangements of answers. In other words, there must be at least $\frac{k^m}{N \choose m}$ distinct leaves in the decision tree, yielding a lower bound of $\log_{N+1} \left({\frac{k^m}{N \choose m}}\right) = m \log_{N+1} {k} - \log_{N+1} {N \choose m}$ guesses (although there is a minimum of one guess).

Upshot

An overall (non-constructive) lower bound is $\max(1,m \log_{N+1} {k}- \log_{N+1} {N \choose m})$ guesses. If $N$ is very large compared to $m$, this bound is trivially 1. If $m$ is large, then this is roughly $m \log_m (k)$, which is a bit smaller than @babou ’s solution.

Answer 2

Here is an algorithm to identify the answers with successive attempts.

It has a worst case complexity of $O(m(1+\log_2 k))$

This corresponds roughly to collecting in each attempt one bit of information on the right answer, for each question in succession.

Of course we cannot do that, because we can only give one whole answer per question. So the trick in to transpose the problem, by identifying k correct answers and trying to find their questions.

Apologies for the rough presentation. I am running out of time.

The algorithm

We assume, to simplify the presentation, that $N\geq k$. But it does not really matter. We also assume that $k=2^p$ for some positive integer $p$, again to simplify the presentation.

We assume that the only result of an attempt $T\in [1,k]^N$ is a score $s(T)$ corresponding to the number of correct answers. The individual answers for each question are noted $T[j]\in [1,k]$ for the answer to question $j$, ($j\in [1,N]$), in attempt $T$.

We define $T_i=i^k1^{N-k}, \forall i\in[1,k]$

The $N-k$ last answers always contribute the same amount $r$ to the result $s(T_i)$ since they do not change.

Together, the first $k$ answers of all $k$ attempts will produce $k$ good answers, distributed in some way over all $k$ attempts, since for each question there is exactly one good answer among the $k$ being proposed.

If one attempt has 2 good answers, or more, for one of the first $k$ questions, then another must have 0. Thus, if the scores $s(T_i)$ are not all equal, the smallest is equal to $r$. Furthermore, if they are all equal, then they are all equal to $r+1$. So the value of $r$ is easily determined.

We first assume $\exists r\in[0,N-k],\; \forall i\in[1,k],\; s(T_i)=r+1$

This implies that each attempt has exactly 1 good answer among the first $k$ answers (to the first $k$ questions). But we do not know which.

We define a second set of $k-1$ attempts $T_i'=i^{k/2}1^{N-k/2}, \forall i\in[1,k]$

Note, that $T_1'=T_1$, so that k-1 new attempts only are needed, but the duplication makes things simpler to explain.

If the good answer $1$ in the first $k$ questions in $T_1$ was for one of the first $k/2$ questions, then $1$ is a bad answer for questions $Q_j,\; \forall j\in[k/2+1,k]$. Hence all the $T_i$ attempts that had a good answer for one of these $k/2$ questions will lose 1 point in score, thus falling to $r$. All other attempts, that had a good answer in the first $k/2$ questions will have an unchanged score $r+1$.

If the good answer $1$ in the first $k$ questions in $T_1$ was for one of the last $k/2$ questions, i.e. for questions $Q_j,\; \forall j\in[k/2+1,k]$, then all attempts $T_i'$ benefit from that good answer $1$. Those that had a good answer for the first $k/2$ questions will keep it and see their score increase from $r+1$ to $r+2$, while the others will lose their good answer as before, but have it replaced by the good answer $1$ for one question, thus keeping the score $r+1$.

Thus we can conclude that, if some score decrease, then the firat attempt $T1$ has a good answer $1$ in one of the first $k/2$ questions, and if some increase it is in one of the next $k/2$ questions. Forall other attempts $T_i'$, those with the higher score have a good answer for one of the first $k/2$ questions, and those with the lower score have a good answer in one of the next $k/2$ questions.

Recall that $k=2^p$, i.e. $p=\log_2 k$.

If we number the first $k$ questions in binary, starting from 0, we can see that this is a way to determine the $p^{th}$ bit of the index question that is correctly answered by some attempt $T_i$.

If for some $i>1$, the score decrease from $T_i$ to $T_i'$, then $T_1$ has a good answer for a question $Q$ such that the $p_{th}$ bit of its binary index is $0$, while it is $1$ for an increase. For the other attempts $T_i$, those with the higher score for $T_i'$ have a good answer for a questions with the index $p^{th}$ bit $0$, and the lower scores have a good answer for a questions with the index $p^{th}$ bit $1$

It is then quite simple to repeat the procedure identically for each of the other bits of the binary index of the first $k$ questions.

That makes $p=\log_2k$ series of $k-1$ attempts, in addition to the first $k$ attempts, that is a total of $k+(k-1)\log_2k$ attempts, to get the first k answers.

However we can improve a bit on that count. We do $\log_2 k$ attempts to identify the question associated with each answer, i.e. each index $i\in [1,k]$. Actually we need to identify only $k-1$ such question. The last one in necessarily the one that was not found yet.

Thus in the above algorithm, we do not need to compute $T_{k}'$, nor any of the other attempts of index $k$, except for the first $T_k$ in the first attempts of the algorithm. Since it is also unnecessary for $T_1'$ and similar, we only need, at most $\log_2k$ series of $k-2$ attempts, in addition to the initial $k$ attempts, that is a total of $k+(k-2)\log_2k$ attempts, to get the first k answers.

But this relied on the assumption that each of the first $k$ attempts has exactly one good answer for the first $k$ questions. What if that is not the case?

One of the first $k$ attempts had more than one good answer in the first $k$.

Then there is at least one attempt, say $T_h$ that failed on the first $K$ questions, which means that answer $h$ is wrong for the first $k$ questions.

Actually there may be several such attempts caracterized by the fact that they have the same smallest score $r$. They can all be discounted as containing no information for the first $k$ questions, other than the fact that their index is not the answer to these questions.

Futhermore, for any attempt $T_i$, we know that it has $s(T_i)-r$ correct answer $i$ in the first $k$ questions.

If there is only one answer, it can be identified with the previous binary technique using $\log_2k$ attempts, given that we can replace half the answers (as specfied by a bit in their binary index) by $h$ which is known to be wrong (which makes thing simpler than previously).

If there are two correct answers, the same technique is used with a small variation. The binary approach is used again for both answers together, until one of the attempts separates them by indicating a bit $0$ for one answer and a bit $1$ in the same position of the question binary index for the other answer. From then on, one answer can be hidden by using the answer $h$ in the questions corresponding to that index, while the binary search is resumed for the other answer. Once that answer has identified its question, it is replaced by the answer $h$ that is wrong so that the search can be resumed for the question of the second answer.

The same technique can be used independently of the number of answers, progressively splitting them until only one is searching for its question, then replaced by wrong answer $h$ when its question is found, so that another can be searched, and so on.

Since the splitting and searching is based on the bits of the binary indexes of questions, it is quite clear that this costs never more than $\log_2 k$ for each question to be associated with one of the $k$ answers.

So the cost in number of attempts for identifying the questions for the first $k$ answers (I am deliberately inverting the view) is not more than $k\log_2 k$, to be added to the first $k$ attempts. It might be a bit less with a finer analysis.

However we can again use the fact that each question has necessarily an answer, so as to skip the binary search on one line of answers (i.e., one answer number).

First recall that we simply ignore all answer numbers that correspond to no answer. Then we also set aside the answer number that corresponds to the largest number of questions for which it is the right answer. This corresponds by hypothesis to at least two good answers.

Then we determine the corresponding question for all other identified good answers, at most $k-2$ of them, with a cost that is at most $\log_2 k$ for each. The correct answer set aside can then be assigned to all questions that have not been identified as associated with another answer.

This makes for a total cost of at most $(k-2)\log_2k$ attempts, to be added to the initial $k$ attempts, thus again a total of $k+(k-2)\log_2k$ attempts, to get the first k answers, as in the first case.

Overall

The cost of this algorithm, mesured in number of attemps, is bounded by $k(1+\log_2 k)-2\log_2 k$ for identifying the $k$ answers to $k$ questions (as the above could have been done for any set of $k$ questions.

So for $m$ questions, assuming for simplicity that $m$ is a multiple of $k$, the total cost is bounded by $m/k$ times that cost, i.e. $m(1+\log_2 k)-(2m/k)\log_2 k$.

Apparently the total number $N$ of questions does not matter. But the last questions are not considered with this technique, except to identify their global effect to factor it out. We do not take advantage of the fact that some groups of question-answer pairs might be easier to identify (because their costs can be factored, for example). Possibly this could help for the worst case analysis with a different technique that would identify patterns of answers that are easier to analyze, but there might be a cost in finding them.

Regarding purely asymptotical complexity: this algorithm is $O(m\log_2k)$