Club of Abusers

To enter the Club of Abusers, you have to pass a qualifying exam of 100 True/False questions; the passing grade is 51 questions correct. The questions are so obscure, and rumors say that the graders also mark them in such a way to try to prevent you from passing.

However, for some reason, you are allowed to retake the exam as many times as you wish. As long as any one of the exams receive a passing grade, you are admitted into the club.

To prove that you're worthy to enter the club, you need to abuse this qualifying exam. Take the exam enough times so that at least one is guaranteed to have a passing grade, no matter what the actual answers are. Of course, don't take it too much times; you don't want to spend too long just to enter the club.

To recap:

  • You have k k exam sheets. For each exam, you have 100 questions; all the exams are the same, including the question order (and thus have the same sequence of correct answers).
  • For each question, give an answer of either True or False (each question has two choices).
  • You must submit all exam sheets at the same time; there is no feedback for any exam sheet that you can use to fill in another exam sheet.
  • If any of the exams is correct on at least 51 questions, you win.
  • Find the smallest positive integer k k that allows you to always win with an appropriate strategy.


The answer is 4.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Ivan Koswara
May 24, 2015

First, we claim that 4 \boxed{4} exams is enough.

  • For the first exam, answer everything True.
  • For the second exam, answer everything False.
  • For the third exam, answer everything True, except the last question which is answered False.
  • For the fourth exam, answer everything False, except the last question which is answered True.

Let c 1 , c 2 , c 3 , c 4 c_1, c_2, c_3, c_4 be the number of correct answers on the first, second, third, and fourth exams respectively.

Note that c 1 + c 2 = 100 c_1 + c_2 = 100 ; each question is answered correctly by exactly one of first exam and second exam. If either of c 1 , c 2 c_1, c_2 is less than 50 50 , then the other will necessarily be greater than 50 50 , so you win. Thus if you still don't win, c 1 = c 2 = 50 c_1 = c_2 = 50 .

Next, note that c 3 = c 1 ± 1 c_3 = c_1 \pm 1 , since a difference of a single question will either make a correct answer incorrect, or an incorrect answer correct; the number of correct answer changes by exactly 1 1 . If c 3 = c 1 + 1 c_3 = c_1 + 1 , we have c 3 = 51 c_3 = 51 and we're done. Otherwise, c 3 = c 1 1 = 49 c_3 = c_1 - 1 = 49 . But then c 3 + c 4 = 100 c_3 + c_4 = 100 once again, so c 4 = 51 c_4 = 51 and we're done.

Next, we claim that 3 3 exams is not enough.

Suppose there is such way to take only 3 3 exams and guaranteeing a win. For each question, there are 3 3 exams and 2 2 choices; by Pigeonhole Principle, we can take one choice that is chosen at least twice. Assume that the correct answer is the other choice.

If all exams have no more than 50 50 correct answers, then we're done. Otherwise there is such exam; without loss of generality, suppose that it is the first exam. Now choose any 50 50 questions that the first exam answers correctly, and fix their answers; for the remaining questions, make their correct answers to be opposite of what the first exam answered. By construction, the first exam only scores 50 50 ; in addition, for the questions where the first exam answers correctly, the second and third exams don't answer correctly, and thus each of the second and third exams can score at most 50 50 as well (since they have 50 50 wrong answers already). This proves that 3 3 exams is not enough.

Moderator note:

Brilliant question and answer! I love how a simple difference of one answer solved the whole thing. Follow up question: Instead of only two choices True/False, we have three choices, say Left/Middle/Right. What is the minimum number of entries you need to submit this time? Is the system still (reasonably) beatable?

Challenge Master: Three-choice questions are extremely difficult to beat with the original 51 of 100. The reason I choose 51 is because doing the all-True and all-False leave you with just one off from the target. Thus with three-choice questions, let's consider doing 101 of 300, so that all-Left, all-Middle, and all-Right leave you one off from the target.

This one is still pretty easy to beat with a similar method. Do all-Left, all-Middle, and all-Right; either one of them scores 101 and we win, or all three score 100. Now likewise, modify the answer of the last question into all three possibilities: add all-Left-but-the-last-is-Middle, all-Middle-but-the-last-is-Right, and all-Right-but-the-last-is-Left. At least one of these tests will give an additional point from the last question (the one that gets the correct answer), so 6 6 tests is enough.

However, the method to prove lower bound above is not strong enough; I can only prove that 4 4 tests is not enough. (Each question has a choice picked by only one test. If everything scores below 101, we're done; otherwise, take one that scores over 100, take 100 of the correctly answered questions and fix their choices, and make sure none of the remaining questions have answers as given in this high-scoring test. We now have 3 tests with 2 choices, aiming to score 101 of 200, which is proven impossible above.)

Ivan Koswara - 6 years ago

Amazing question and elegant solution! Definitely going to share this with people outside of brilliant.

Dylan Pentland - 6 years ago

This solution is simply BRILLIANT

Saaket Sharma - 6 years ago
Suhas Shetiya
May 30, 2015

Kindly help me out here My steps:

Step 1. Mark Everything true Possibility 1: Marks greater than 50 We enter the club Possibility 2: Marks less than 50 Step2: Mark everything False we enter the club Possibility 3: Marks equal to 50 Step2: We mark Last question false Sub Possibility 1: If we get 51 i.e. last question was infact False We enter the club Sub Possibility 2: If we get 49 i.e. last question was infact True Step3: Mark First 99 Falso and last one True We Enter the club

I see 3 steps are enough In the solution given step 2 is redundant

Once we know how many are true, why are we again calculating how many are False ?

You don't get the feedback of your exams. You must fill in all exams at the same time before you submit them, so you cannot decide how to fill the second exam based on the first exam.

Ivan Koswara - 6 years ago

Log in to reply

Then yes we need 4 tries !

Suhas Shetiya - 6 years ago
M-Cee Malicsi
Dec 29, 2020

It doesnt matter how you will answer everything, as long as the two sets of questions are entirely opposite of each other, and the other two sets are the same for the 1st two sets except one certain question is changed for both.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...