2014 AIME II Problems/Problem 13

Solution

Let the left shoes be L1 ... L10 and the right shoes be R1 ... R10. Notice that there are 10 * 9 * 8 * ... * 1 = 10! possible pairings. To calculate the possible cases, we casework on the number and length of cycles, where a cycle is a sequence of shoes that starts with an arbitrary shoe, is continued when that shoe is paired with another shoe and the new shoe under consideration is the paired shoe's pair, and ends with the first shoe's pair. (For example, L1 -> R2, L2 -> R5, L5 -> R1 is a cycle of length 3). Trivially, if there is a cycle of all ten shoes (for example, L1 -> R2, L2 -> R3, ..., L10 -> R1) then there are 9 * 8 * ... * 1 = 9! working cases. Or, there will be two cycles of 5 shoes: * . Now, there cannot be a cycle of 6 and a cycle of 4 by the hypothesis; by similar reasoning, our two cases are the only ones that work. To compute the probability, we see that the first case yields a probability of 1/10 and the second case . Adding the probability gives , for an answer of .