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 split into cases. 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 .