Problem:
Ten adults enter a room, remove their shoes, and toss their shoes into a pile. Later, a child randomly pairs each left shoe with a right shoe without regard to which shoes belong together. The probability that for every positive integer , no collection of pairs made by the child contains the shoes from exactly of the adults is , where and are relatively prime positive integers. Find .
Solution:
Let and represent the right and left shoes, respectively, from the th adult. Call a set of pairs made by the child good if contains the shoes from exactly adults. The condition to be satisfied is that no good set contains fewer than pairs. Note that if a set of pairs is good, then the complementary set of pairs is also good. Therefore the required condition can be met in only one of two ways:
The set of all pairs is the only good set. In this case can be paired with any of right shoes cannot be paired with . Relabeling if necessary, it may be assumed that is paired with . Then can be paired with any of 8 right shoes cannot be paired with or . Again by relabeling, it may be assumed that is paired with , and can be paired with any of right shoes. Continuing, it is seen that there are pairings for which the set of all pairs is the only good set.
There are good sets of pairs each. The set of left shoes can be partitioned into sets of left shoes in ways. For each such partition of the left shoes, the reasoning of the preceding case can be used to establish that for each of the sets of left shoes, there are possible arrangements of right shoes that result in a good set of pairs. Thus there are pairings for which there are good sets of pairs each.
The total number of possible pairings is , so the required probability is . The requested sum is .
There is a permutation such that the pairs made by the child are of the form . There are equally likely permutations. The permutation will factor into cycles of various lengths. For the conditions of the problem to be met, the permutation can have no cycle of length less than . This can happen if the permutation is a single cycle of length where no subset of fewer than all pairs of shoes can all be properly matched such as . It can also happen if the permutation is the product of two cycles of length where the pairs of shoes partition into two groups of size , and no proper subset of either group can be properly matched such as . Counting the number of cycles of length and products of two cycles of length is then the same as the counting in the two cases of the previous solution.
The problems on this page are the property of the MAA's American Mathematics Competitions