# Hard Logic Problem of True or False questions

• Nov 17th 2012, 07:39 PM
blehbleh
Hard Logic Problem of True or False questions
A contest consists of 30 true or false questions. You know nothing about the subject matter.
Whenever you answer the contest problem you are told of the number of questions you answered correctly.
How will you solve the contest repeatedly such that you get a perfect score on exactly your 25th attempt?
• Nov 19th 2012, 03:43 PM
Stephen347
Re: Hard Logic Problem of True or False questions
Test(TT)

0 Correct => FF
2 Correct => TT

1 Correct: Test(TFT)

Since we changed one of the answers of the first two questions, we will get either 0 or 2 correct answers from questions 1 and 2, but not only 1. Thus getting 0 or 1 answers correct in this test must result from getting questions 1 and 2 wrong, and question 3 wrong or right, respectively. Similarly, getting 2 or 3 questions correct must result from getting questions 1 and 2 correct, and getting question 3 wrong or right, respectively.
Hence:

0 Correct => FTF
1 Correct => FTT
2 Correct => TFF
3 Correct => TFT

So in 1 turn, you can either know 0 or 2 correct answers. After 2 turns, it is possible to know either 2, 3, or 4 correct answers. In 3 turns, it is possible to know 3, 4, 5, or 6 correct answers. But in 4 turns, it is possible to know 5, 6, 7, or 8 answers. So, after 4 turns we always know at least 5 correct answers, following the method above.

After the first sequence of 4 turns, set the first question to be incorrect and next however many known answers to be their correct answer. This way we will never accidentally answer the whole test before the 25th turn, because question 1 will always be wrong. So, in 4 turns, we should have 1 wrong and at least 4 right. Then there are, at most, 25 question left, which by the method above, can be solved in at most 20 turns (5 questions for every 4 turns). It is definitely possible, in fact likely, to finish sooner than this, but in the worst case scenario it takes 20 turns. Thus, we have used 24 of our turns (4 on deducing the first 5 questions (then changing the first to be incorrect) and 20 on deducing the last 25 questions). We now know all of the correct answers to the questions, so on our 25th time taking the test we have finally answered all of the 30 questions correctly. If we happen to know the correct answers to all the questions in less then 24 moves, then we continue to test with the wrong answer in question 1 until the 25th turn, when we set it right and answer.

If the goal were just to minimize the maximum possible number of turns necessary to complete the test (rather than to get it right on exactly the 25th try), it can be done in just 21 turns. This is done by repeating the testing procedure above 18 times, each pair of tests resulting in only knowing 3 correct answers. Hence, at this point we know 27 answers. Then, it could be that in the next test of two answers, we learn 2 correct answers, resulting in 19 tests and 29 correct answers. On the twentieth test, we could guess the final question incorrectly, but on the 21st we will have definitely gotten them all correct.