If you were to try to brute-force a multiple-choice test (with, say, m questions with n choices each), where you had unlimited attempts, and you received a total of how many questions you got right at the end, but where leaving an answer blank isn't allowed, what would be the best strategy?

The simplest way I can think of is to simply fill all As, and guess each question at a time, but that would take m*n max attempts.

  • $\begingroup$ See also the game Mastermind which is closely related -- your problem is the same as Mastermind if the white feedback pegs are ignored (and only black feedback pegs are used). $\endgroup$ – Henning Makholm May 8 '15 at 18:46
  • $\begingroup$ I think your method is $m^{n}$ attempts (max). $\endgroup$ – TravisJ May 8 '15 at 18:47
  • $\begingroup$ @TravisJ: No, that would be the stupidmost brute-force strategy (and even that is $n^m$ rather than $m^n$). The $m\times n$ strategy starts by finding the first answer (submit all possible values of it, keeping the rest of the answers constant, and see which of your submissions has a higher score than the others). Then do the same for the second answer, and so forth. Finding the correct answer to one question never takes more than $n$ submissions (in fact $n-2$ submissions is enough except for the first one) $\endgroup$ – Henning Makholm May 8 '15 at 18:49
  • $\begingroup$ @HenningMakholm, ahh, I see. I think I mis-understood the method that hintss described. $\endgroup$ – TravisJ May 8 '15 at 18:51
  • $\begingroup$ It's different in that you don't get feedback on individual questions, though. $\endgroup$ – hintss May 8 '15 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.