# Recover the answers of a test with n yes/no questions

Given a test with 𝑛 yes/no questions, a candidate is able to submit multiple solutions. For a given solution, the candidate gets feedback on the number of correct answers. The goal is to recover the answers to all the questions.

What strategy could/should a candidate use to minimize:

1. The worst-case number of submissions?
2. The average number of submissions?
• For anyone interested, rot13(V guvax guvf vf rdhvinyrag gb gur ceboyrz sbezhyngrq va guvf cncre ol Reqöf naq Eralv). Couldn't find an exact duplicate on this site. Jan 25, 2021 at 21:34
• Nice find @LukasRotter! rot13(Ng svefg tynapr vg ybbxf vqragvpny (gb gur frpbaq ceboyrz) va gur cncre vapyhqvat nzovthvgl nf gb jurgure gur grfg dhrfgvbaf unir gb or fhozvggrq nyy ng bapr be vaperzragnyyl (tvivat gur punapr gb nqncg gb vasbezngvba tnvarq fb sne). Vg frrzf, ubjrire, gung gur cncre nqqerffrf gur svefg pnfr jurernf BC'f nfxvat sbe jbefg naq nirentr pnfrf fhttrfgf gur frpbaq pnfr.) Jan 26, 2021 at 2:55

## 2 Answers

Here's a solution that's likely not optimal, but worth a shot. It requires on average 3N/4 submissions, or N submissions in the worst case. To begin, submit random answers and get the number correct - we'll call this configuration of answers the baseline. Now, go down the list of questions in pairs, and changing your answer for exactly two questions and resubmitting.

On average, 25% of the time, both answers were right originally and your score will go down by 2, and 25% of the time, both were wrong and the score will go up by 2. In both cases, we now know the answers to both questions. The other 50% of the time, you'll have one question right and one wrong with no change in score, so you need to go back to the baseline configuration and change only one answer.

On average, it will take 2 submissions plus the baseline to get the right answer for half the pairs of questions, but only one submission plus the baseline to verify that the other half of pairs is correct already. This gives us an average of 3/4N submissions, since you don't need to worry about the last question (if you don't have a perfect score by then, change the answer). In the worst case, however, we need to change every single answer, resulting in N submissions.

There doesn't appear to be a definitive answer to this problem, but a paper of Cantor and Mills implies the following process provides a reasonably strong bound:

Begin with the matrices $$P_0 = [1], M_0 = [0], A_1 = \left[\matrix{1\\0}\right]$$.
Then, by simultaneous recursion, let $$P_{k+1} = \left[\matrix{P_k&M_k&I\\P_k&P_k&0}\right], M_{k+1} = \left[\matrix{M_k&P_k&0\\M_k&M_k&0}\right], A_{k+1} = \left[\matrix{A_k&P_k\\A_k&M_k}\right]$$, where $$I$$ (resp. $$0$$) is the identity (resp. zero) matrix of the appropriate size, as usual.
If $$m$$ is the least positive integer such that $$2^{m-1}m \geq n$$, then the nonzero rows of $$A_m$$ denote a sufficient set of solutions to identify the correct answers.
The reason this works is that $$P$$ (resp. $$M$$) denotes the positions of $$+1$$ (resp. $$-1$$) entries in the recurrence for $$B$$ in the linked paper (the interchange of $$P$$ and $$M$$ replaces the negation of $$B$$ and thus prevents negative entries from occurring) and is therefore a valid candidate for $$V$$ (resp. $$W$$) in the construction of $$A$$.
Since $$M$$'s bottom row cannot gain $$1$$'s and doesn't begin with any, it is always completely zero. Similarly, $$A$$'s bottom row doesn't begin with any $$1$$'s and could only obtain them from $$M$$, so it always remains completely zero and can be removed once a matrix of the desired length is obtained.

• Can you demonstrate an example? Say in the case of n=3 we have m=2, how do the questions work? Jan 26, 2021 at 17:36