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

m (Solution)
m (Solution: Clarification)
Line 4: Line 4:
 
==Solution==
 
==Solution==
 
Let the left shoes be <math>L1,\dots, L10</math> and the right shoes be <math>R1,\dots, R10.</math> Notice that there are <math>10 \cdot 9\cdot 8 \cdots 1 = 10!</math> 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, <math>L1\to R2</math>, <math>L2\to R5</math>, <math>L5 \to R1</math> is a cycle of length 3). Trivially, if there is a cycle of all ten shoes (for example, <math>L1 \to R2</math>, <math>L2 \to R3, \dots, L10 \to R1</math>) then there are <math>9 \cdot 8\cdots 1 = 9!</math> working cases. Or, there will be two cycles of 5 shoes: <math>\frac{{10\choose 5}}{2}\cdot{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 <math>\frac{1}{10}</math> and the second case <math>\frac{126 \cdot 24 \cdot 24}{10!} = \frac{1}{50}</math>. Adding the probability gives <math>\frac{3}{25}</math>, for an answer of <math>\boxed{028}</math>.
 
Let the left shoes be <math>L1,\dots, L10</math> and the right shoes be <math>R1,\dots, R10.</math> Notice that there are <math>10 \cdot 9\cdot 8 \cdots 1 = 10!</math> 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, <math>L1\to R2</math>, <math>L2\to R5</math>, <math>L5 \to R1</math> is a cycle of length 3). Trivially, if there is a cycle of all ten shoes (for example, <math>L1 \to R2</math>, <math>L2 \to R3, \dots, L10 \to R1</math>) then there are <math>9 \cdot 8\cdots 1 = 9!</math> working cases. Or, there will be two cycles of 5 shoes: <math>\frac{{10\choose 5}}{2}\cdot{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 <math>\frac{1}{10}</math> and the second case <math>\frac{126 \cdot 24 \cdot 24}{10!} = \frac{1}{50}</math>. Adding the probability gives <math>\frac{3}{25}</math>, for an answer of <math>\boxed{028}</math>.
 +
 +
 +
Now, why are there <math>9!</math> cases for 10 shoes? That's because, if we had <math>L1</math>, there are of course 9 choices: all except <math>L1</math> itself.
 +
 +
Meanwhile, if we tried to see <math>L2</math>, why 8? That's because we cannot use <math>R2</math> and the <math>corresponding shoe R1</math>.
 +
 +
And so on: for <math>L5</math>, there would've only been 5 possibilities: we can't use <math>R5</math> and the <math>corresponding shoes for L1 - L4</math>.
  
 
== See also ==
 
== See also ==

Revision as of 21:13, 18 March 2017

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 $k<5$, no collection of $k$ pairs made by the child contains the shoes from exactly $k$ of the adults is $\frac{m}{n}$, where m and n are relatively prime positive integers. Find $m+n.$

Solution

Let the left shoes be $L1,\dots, L10$ and the right shoes be $R1,\dots, R10.$ Notice that there are $10 \cdot 9\cdot 8 \cdots 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\to R2$, $L2\to R5$, $L5 \to R1$ is a cycle of length 3). Trivially, if there is a cycle of all ten shoes (for example, $L1 \to R2$, $L2 \to R3, \dots, L10 \to R1$) then there are $9 \cdot 8\cdots 1 = 9!$ working cases. Or, there will be two cycles of 5 shoes: $\frac{{10\choose 5}}{2}\cdot{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 $\frac{1}{10}$ and the second case $\frac{126 \cdot 24 \cdot 24}{10!} = \frac{1}{50}$. Adding the probability gives $\frac{3}{25}$, for an answer of $\boxed{028}$.


Now, why are there $9!$ cases for 10 shoes? That's because, if we had $L1$, there are of course 9 choices: all except $L1$ itself.

Meanwhile, if we tried to see $L2$, why 8? That's because we cannot use $R2$ and the $corresponding shoe R1$.

And so on: for $L5$, there would've only been 5 possibilities: we can't use $R5$ and the $corresponding shoes for L1 - L4$.

See also

2014 AIME II (ProblemsAnswer KeyResources)
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. AMC logo.png