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).