Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Is there a particular distribution of the answers? Or should we just assume that its uniform? –  AnonSubmitter85 Mar 3 at 12:13
    
@AnonSubmitter85 I don't see why we need to assume a distribution. –  Priyatham Mar 3 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 at 12:22
    
Ok, let's assume it's uniform. –  Priyatham Mar 3 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 at 12:29

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you!. For some reason I thought the answer might be in log scale. –  Priyatham Mar 3 at 13:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.