The clueless student: solution

This is to capture notes on my progress toward a solution to the “matching quiz” problem presented in the previous post, which can be re-stated more concisely as follows: what is the optimal strategy for choosing quiz answers specified as a function , not necessarily a bijection, that maximizes the probability of agreeing with a randomly chosen “solution” bijection in at least questions?

A strategy is characterized by a partition of , with the parts corresponding to the sizes of the classes of the equivalence kernel of the chosen function .  The number of parts in the partition indicates the number of distinct quiz answers.  For example,

corresponds to a bijection, and the single-part partition corresponds to a constant function, i.e., writing the same answer for all questions.  Note that any function with the same partition “signature” has the same probability of success.

So, given a guessing strategy specified as a partition with parts:

what is the probability of getting at least answers correct?  First, we can compute the probability that exactly some subset of distinct answers is correct using inclusion-exclusion:

And so the overall probability of at least correct answers is

We can collapse this sum of sums by observing that a particular subset in the inner summation appears times in the outer summation for a given size .  Using the identity

we can compute the overall probability of at least correct answers as

At this point, I’m stuck; I don’t see a better approach than simply evaluating all possible strategies (i.e., generating all integer partitions of ) for small values of , and looking for patterns.  Following is the conjectured optimal strategy which holds for :

• If , then as pointed out in the previous post, write down the same answer times, guaranteeing exactly one correct answer.
• For , write one answer times, and another (different) answer times.
• For , select an “almost-permutation,” corresponding to the integer partition , so that exactly one answer gets duplicated (and thus exactly one answer is missing).
• Otherwise, select a random permutation.

Actually, we can describe this strategy more efficiently as follows: (a) select distinct answers, and distribute them as evenly as possible among the questions… unless , in which case (b) just select a random permutation.  I think (a) is what intuition would suggest is always the optimal approach– it was my wife’s immediate response when I described the problem to her– but I don’t have a good explanation for the qualification (b).