# Is this a problem that has already been solved?

I have a question paper with $n$ True/False questions and I don't know the answer to any of those questions. My objective is to find the answer key of the question paper. All I have is a machine which will tell my total score out of $n$, when I submit my answer sheet(I must mark either T/F for all the questions). What strategy should I follow to ensure that I find the answer key in minimum number of submissions?

Is the above problem already known and solved?

PS: I am not really sure about the tags. Please edit them if they are wrong.

-
Is there a particular distribution of the answers? Or should we just assume that its uniform? –  AnonSubmitter85 Mar 3 '14 at 12:13
@AnonSubmitter85 I don't see why we need to assume a distribution. –  Priyatham Mar 3 '14 at 12:16
Isn't that required to get performance analysis? Similar to average case vs worst case for sorting algorithms. Intuitively I'd guess that a binary-style of testing that recursively split the questions into two groups would outperform the basic strategy of changing one answer at a time, but only if the answers were not uniformly distributed between true and false. –  AnonSubmitter85 Mar 3 '14 at 12:22
Ok, let's assume it's uniform. –  Priyatham Mar 3 '14 at 12:23
I suspect in general that this problem parallels that of sorting with repeated values, namely a string of $0$'s and $1$'s. Not sure though; just a thought. –  AnonSubmitter85 Mar 3 '14 at 12:29

Yes, this has already been solved.

Think of this problem as a simple version of the MasterMind (code-breaker) game. In this simple version there are only 2 colors, black and white (true and false).

The maximum number of tries is $$\lfloor \frac n2 \rfloor +2$$

You can find the proof here in chapter 4.

-
Thank you!. For some reason I thought the answer might be in log scale. –  Priyatham Mar 3 '14 at 13:04