Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
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:
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.
