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"

(→‎Solution)
Line 3: Line 3:
  
 
==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>.
+
Label the left shoes be <math>L_1,\dots, L_{10}</math> and the right shoes <math>R_1,\dots, R_{10}</math>. Notice that there are <math>10!</math> possible pairings.
  
  
−
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.
+
Let a pairing be "bad" if it violates the stated condition. We would like a condition to determine if a given pairing is bad.
  
−
Meanwhile, if we tried to see <math>L2</math>, why 8? That's because we cannot use <math>R2</math> and the <math>corresponding</math> <math>shoe</math> <math>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</math> <math>shoes</math> <math>for
+
Note that, in order to have a bad pairing, there must exist a set of <math>k<5</math> pairs that includes both the left and the right shoes of <math>k</math> adults; in other words, it is bad if it is possible to pick <math>k</math> pairs and properly redistribute all of its shoes to exactly <math>k</math> people.
−
</math> <math>L1 - L4</math>.
+
 
 +
 
 +
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 <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>.
 +
 
 +
 
 +
The first case yields <math>9!</math> working pairings. The second case yields <math>\frac{{10\choose 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{126 \cdot 24 \cdot 24}{10!} = \frac{3}{25}</math>, for an answer of <math>\boxed{028}</math>.
  
 
== See also ==
 
== See also ==

Revision as of 00:48, 22 February 2018

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

Label the left shoes be $L_1,\dots, L_{10}$ and the right shoes $R_1,\dots, R_{10}$. Notice that there are $10!$ possible pairings.


Let a pairing be "bad" if it violates the stated condition. We would like a condition to determine if a given pairing is bad.


Note that, in order to have a bad pairing, there must exist a set of $k<5$ pairs that includes both the left and the right shoes of $k$ adults; in other words, it is bad if it is possible to pick $k$ pairs and properly redistribute all of its shoes to exactly $k$ 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 $R_1$, check the left shoe it is paired with (say $L_i$), and from the previous observation we know that $R_i$ must also be in the bad collection. Then we may check the left shoe paired with $R_i$, find its counterpart, check its left pair, find its counterpart, etc. until we have found $L_1$. 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 $5$ 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 $5$; thus, we need to count pairings where every cycle has length at least $5$. This is only possible if there is a single cycle of length $10$ or two cycles of length $5$.


The first case yields $9!$ working pairings. The second case yields $\frac{{10\choose 5}}{2}\cdot{4!}^2$ pairings. Therefore, taking these cases out of a total of $10!$, the probability is $\frac{1}{10}+\frac{126 \cdot 24 \cdot 24}{10!} = \frac{3}{25}$, for an answer of $\boxed{028}$.

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. AMC logo.png

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