Maths Olympiad Prep

Library / /193 of 377

Combinatorics Difficulty 5.1 AIME, harder Prove it United States

Problem:
A true-false test has ten questions. If you answer five questions "true" and five "false," your score is guaranteed to be at least four. How many answer keys are there for which this is true?

Solution

Solution:
Suppose that either nine or ten of the questions have the same answer. Then no matter which five questions we pick to have this answer, we will be right at least four times. Conversely, suppose that there are at least two questions with each answer; we will show that we can get a score less than four. By symmetry, assume there are at least five questions whose answer is true. Then if we label five of these false, not only will we get these five wrong, but we will also have answered all the false questions with true, for a total of at least seven incorrect. There are 2 ways for all the questions to have the same answer, and 210=202 \cdot 10 = 20 ways for one question to have a different answer from the others, for a total of 22 ways.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.