In a multiple choice quiz, how many submissions do you need to answer all questions right if you know how many answers were right? In a multiple choice test where


*

*one has to pick one answer for each question

*all answers are submitted at once

*one is told the number of questions answered right (but not which answers were correct) after each submission and

*it is the goal to answer the questions right with as little attempts as possible
How many submissions are required in order to succeed without knowing any answer (worst case) and what strategy can be applied to achieve this?

For example, in a quiz with ten questions and four answers for each question I would guess that, using an optimum approach:


*

*each submission gives me about three bits of information

*each question requires 2 bits to be answered
and therefore, seven submissions should be enough to answer all questions. Is that right?
 A: I like the problem, so I'll give it a shot.
If you have a test with $N$ questions with $a$ answers each, then the probability of guessing correctly is $p_a=\frac{1}{a}$. Since you don't have information on the answers $A$, the first round of guessing will give you $\mathbb{E}[A] = p_a\cdot N$ correct answers.
Assuming they only tell you how many are correct, you submit $N$ times to check which answers were correct. In the process you can expect to gather an extra $p_{(a-1)}\cdot (1 - p_a)\cdot N$ correct answers. Now you have
$$
\mathbb{E}[A] = p_a\cdot N + p_{(a-1)}\cdot (1 - p_a)\cdot N = N \cdot \left[ p_a\ + p_{(a-1)}\cdot (1 - p_a) \right]
$$
Now you change the wrong answers randomizing with $p_{(a-2)} = \frac{1}{a-2}$. (You've already discarded $2$ possibilities for each answer.) From this run you expect to have a new total of correct answers:
$$
\frac{\mathbb{E}[A]}{N} = \left[ p_a\ + p_{(a-1)}\cdot (1 - p_a) \right]\ +\ p_{(a-2)}\cdot \left[1 - \left( p_a\ + p_{(a-1)}\cdot (1 - p_a) \right) \right]\\
= p_{a} + p_{a-1} - p_{a}\cdot p_{(a-1)}\ +\ 
p_{(a-2)} - p_{a}\cdot p_{(a-2)} - p_{(a-1)}\cdot p_{(a-2)} + p_{a}\cdot p_{(a-1)} \cdot p_{(a-2)}
$$

If $a = 4$, then the expected value of correct answers is $.75N$ after these $2$ steps. Those steps include $\mathbb{E}[\mathrm{S_1}] = 1 + N$.
And for the second iteration, you fill in the remaining option for the wrong questions, giving a total of $\mathbb{E}[\mathrm{S_2}] = \left(1 + N\right) + \left(1 + \frac{N}{2}\right)$.
Since $a = 4$, $.25N$ is expected to remain, which has a $p_{(a-3)}$ of being correct, so finally $\mathbb{E}[\mathrm{S_3}] = \left(1 + N\right) + \left(1 + \frac{N}{2}\right) + 1$ can solve the test with $100\%$ on average.
