The clueless student

The following problem appeared in Marilyn vos Savant’s “Ask Marilyn” column in the 25 July 2004 issue of Parade magazine:

A high school student who hadn’t opened his American history book in weeks was dismayed to walk into class and be greeted with a pop quiz.  It was in the form of two lists, one naming the 24 presidents in office during the 19th century in alphabetical order and another list noting their terms in office, but scrambled.  The object was to match the presidents with their terms.  The completely clueless student had to guess every time.  On average, how many did he guess correctly? — Bob Hendel

This is a nice problem, with an equally nice answer, which Marilyn boiled down to just two words: “Only one!”  That the average number of correct guesses is exactly one, no matter how many questions (i.e., presidents and terms) in the quiz, is a great demonstration of the power of linearity of expectation.  But I wonder if Marilyn recognized that there are at least two reasonable interpretations of how the student might “guess every time”:

1. Match each president with a term, using each available term exactly once.  In other words, select a random permutation of the terms.
2. Match each president with a randomly selected term, where each term may be used more than once, or not at all.  In other words, select a random function mapping presidents to terms.

Fortunately, it doesn’t matter; the average number of correct guesses– one– is the same in either case.

But now let’s make the problem more interesting: suppose that this 24-question quiz is the last exam of the school year, and our clueless student needs just one correct answer to pass the class.  What should he do?  Using either of the two methods above, the probability that he gets every answer wrong, and fails the class, is about , or about 0.37.  (The actual probabilities are different for the two methods, but both converge to in the limit as the number of questions grows large.)

There is a better strategy, though: if he instead selects one term of office– any term of office– and writes that same term for every president in the quiz, then he is guaranteed to get exactly one answer correct!

The motivation for this post is to generalize this problem: given a matching quiz with questions and corresponding possible answers, and a desired “target” score of , what guessing strategy maximizes the probability of at least correct answers?  How are such strategies characterized, and given such a strategy, how do we compute the corresponding probability of success?