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