Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2014 AIME II Problems/Problem 13"

(Created page with "==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 cas...")
 
(→‎Solution)
Line 1: Line 1:
 
==Solution==
 
==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: <math>10\choose{5} / 2</math> * <math>{4!}^2</math>. 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 <math>\frac{126 * 24 * 24}{10!} = \frac{1}{50}</math>. Adding the probability gives <math>\frac{3}{25}</math>, for an answer of <math>\boxed{28}</math>.
+
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: <math>\frac{{10\choose 5}}{2}</math> * <math>{4!}^2</math>. 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 <math>\frac{126 * 24 * 24}{10!} = \frac{1}{50}</math>. Adding the probability gives <math>\frac{3}{25}</math>, for an answer of <math>\boxed{28}</math>.

Revision as of 20:47, 11 April 2014

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: $\frac{{10\choose 5}}{2}$ * ${4!}^2$. 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 $\frac{126 * 24 * 24}{10!} = \frac{1}{50}$. Adding the probability gives $\frac{3}{25}$, for an answer of $\boxed{28}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_AIME_II_Problems/Problem_13&oldid=61418"