HMMT 二月 2005 · COMB 赛 · 第 1 题

HMMT February 2005 — COMB Round — Problem 1

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?

解析

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: 22 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 2 · 10 = 20 ways for one question to have a different answer from the others, for a total of 22 ways.