Difference between revisions of "2014 AIME II Problems/Problem 13"
m (→Solution) |
m |
||
| (4 intermediate revisions by 4 users not shown) | |||
| Line 12: | Line 12: | ||
| − | Thus, if a left shoe is a part of a bad collection, its corresponding right shoe must also be in the bad collection (and vice versa). To search for bad collections, we can start at an arbitrary right shoe (say <math>R_1</math>), check the left shoe it is paired with (say <math>L_i</math>), and from the previous observation we know that <math>R_i</math> must also be in the bad collection. Then we may check the left shoe paired with <math>R_i</math>, find its counterpart, check its left pair, find its counterpart, etc. until we have found <math>L_1</math>. We can imagine each right shoe "sending" us to another right shoe (via its paired left shoe) until we reach the starting right shoe, at which point we know that we have found a bad collection if we have done this less than <math>5</math> times. | + | Thus, if a left shoe is a part of a bad collection, its corresponding right shoe must also be in the bad collection (and vice versa). To search for bad collections, we can start at an arbitrary right shoe (say <math>R_1</math>), check the left shoe it is paired with (say <math>L_i</math>), and from the previous observation, we know that <math>R_i</math> must also be in the bad collection. Then we may check the left shoe paired with <math>R_i</math>, find its counterpart, check its left pair, find its counterpart, etc. until we have found <math>L_1</math>. We can imagine each right shoe "sending" us to another right shoe (via its paired left shoe) until we reach the starting right shoe, at which point we know that we have found a bad collection if we have done this less than <math>5</math> times. |
| − | Effectively we have just traversed a ''cycle.'' The only condition for a bad pairing is that there is a cycle with length less than <math>5</math>; thus, we need to count pairings where every cycle has length at least <math>5</math>. This is only possible if there is a single cycle of length <math>10</math> or two cycles of length <math>5</math>. | + | Effectively we have just traversed a ''cycle.'' (Note: This is the cycle notation of permutations.) The only condition for a bad pairing is that there is a cycle with length less than <math>5</math>; thus, we need to count pairings where every cycle has length at least <math>5</math>. This is only possible if there is a single cycle of length <math>10</math> or two cycles of length <math>5</math>. |
| − | The first case yields <math>9!</math> working pairings. The second case yields <math>\frac{{10\choose 5}}{2}\cdot{4!}^2=\frac{10!}{2 \cdot {5!}^2} \cdot {4!}^2 | + | The first case yields <math>9!</math> working pairings. The second case yields <math>\frac{{10\choose 5}}{2}\cdot{4!}^2=\frac{10!}{2 \cdot {5!}^2} \cdot {4!}^2</math> pairings. Therefore, taking these cases out of a total of <math>10!</math>, the probability is <math>\frac{1}{10}+\frac{1}{50} = \frac{3}{25}</math>, for an answer of <math>\boxed{028}</math>. |
| + | |||
| + | |||
| + | == Video Solution == | ||
| + | https://youtu.be/RFZOHbmmy2k?si=XOfC-akwHFKh3jy0 | ||
| + | |||
| + | MathProblemSolvingSkills.com | ||
| + | |||
| + | |||
| + | ==Article/Blog post solution== | ||
| + | https://www.commonsensiblemath.com/the-power-of-graphing-2014-aime-ii-p13/ | ||
== See also == | == See also == | ||
Latest revision as of 14:33, 5 October 2023
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 m and n are relatively prime positive integers. Find 
Solution
Label the left shoes be 
and the right shoes 
. Notice that there are 
possible pairings.
Let a pairing be "bad" if it violates the stated condition. We would like a better condition to determine if a given pairing is bad.
Note that, in order to have a bad pairing, there must exist a collection of pairs that includes both the left and the right shoes of adults; in other words, it is bad if it is possible to pick pairs and properly redistribute all of its shoes to exactly people.
Thus, if a left shoe is a part of a bad collection, its corresponding right shoe must also be in the bad collection (and vice versa). To search for bad collections, we can start at an arbitrary right shoe (say 
), check the left shoe it is paired with (say 
), and from the previous observation, we know that 
must also be in the bad collection. Then we may check the left shoe paired with , find its counterpart, check its left pair, find its counterpart, etc. until we have found 
. We can imagine each right shoe "sending" us to another right shoe (via its paired left shoe) until we reach the starting right shoe, at which point we know that we have found a bad collection if we have done this less than 
times.
Effectively we have just traversed a cycle. (Note: This is the cycle notation of permutations.) The only condition for a bad pairing is that there is a cycle with length less than ; thus, we need to count pairings where every cycle has length at least . This is only possible if there is a single cycle of length 
or two cycles of length .
The first case yields 
working pairings. The second case yields 
pairings. Therefore, taking these cases out of a total of , the probability is 
, for an answer of 
.
Video Solution
https://youtu.be/RFZOHbmmy2k?si=XOfC-akwHFKh3jy0
MathProblemSolvingSkills.com
Article/Blog post solution
https://www.commonsensiblemath.com/the-power-of-graphing-2014-aime-ii-p13/
See also
| 2014 AIME II (Problems • Answer Key • Resources) | ||
| Preceded by Problem 12 |
Followed by Problem 14 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
