Question

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 P. Find P.

Answer 1

I'm thinking about approaching this with indicator variables....

Answer 2

do you know the answer?

Answer 3

That would sound like a good idea if I knew what it was...
This is a #13 from the AIME I took today, so I don't have the answers yet.

Answer 4

I'll have to meditate on this for a bit, and I have to eat. In the meantime let me call in the cavalry:
@Zarkon
whenever he comes online....

Answer 5

" no collection of K pairs made by the child contains the shoes from exactly K of the adults is P"
does this mean the same thing as "the probability that K pairs don't match is P"

Answer 6

no, I think it means that NONE of the adults' shoes are in those pairs.

Answer 7

@ybarrap

Answer 8

We need the probability (P) that none of the K pairs of shoes selected match any of their owners.

Is that how you see this problem?

Answer 9

I think that's right. That's what I meant by "the probability that K pairs don't match is P", but that was not BTaylor's interpretation of the problem.

Answer 10

but I guess it is a combination of the two interpretations, that none of the K match.

Answer 11

"none of the K pairs..."
yeah I guess you and BTaylor are saying the same thing, sorry

Answer 12

The probability that the 1st pair is not a match is
$$
\cfrac{9}{10}
$$
The probability that 1st 2 pairs don' match is
$$
\cfrac{9}{10}\cfrac{8}{9}=\cfrac{8}{10}
$$
So, the probability that the 1st k shoes don't match is
$$
P=\cfrac{9}{10}\cfrac{8}{9}\cdots\cfrac{10-k}{10-(k-1)}=\cfrac{10-k}{10}
$$
Where k=1,2,3,4 and n=10.

For k=1
$$
P=\cfrac{9}{10}
$$
For k=2
$$
P=\cfrac{8}{10}\cfrac{}{}
$$
and so on.

Does this make sense?

Answer 13

I had to stare at that answer for a long time because it seemed too simple, but I do believe it's right.

Answer 14

Here's the actual solution:
http://www.artofproblemsolving.com/Wiki/index.php/2014_AIME_II_Problems/Problem_13
I have no clue how to interpret it. I don't know why I even tried to attempt it. I'm just mad that earlier in the test I got a problem right except the last step when I put 65+102=177. Got the stats right, not the 2nd grade arithmetic. Grr...

Answer 15

My initial solution was so way off because I made an incorrect assumptions about the owners and shoes in group of K pairs of shoes.

I see now how this was solved, but I had not thought about using permutation cycles.

http://mathworld.wolfram.com/PermutationCycle.html

Every permutation can be specified as a cycle or set of cycles. In a cycle, all the shoes and their owners are in the same set. That is, all the left and right shoes are in the set, they just aren't paired with each other.

But in this problem, they specify that some of the owners of the shoes are not in the set of K selected by the child. Meaning, that there are some left shoes that don't have a corresponding right shoe among the K pair selected.

This means that we can not have cycles of length 6 and 4 or of size 7 and 3 or of size 8 and 2 or of size 9 and 1. Because cycles are of length 6 and 4, for example, describe the same permutation as cycles of length 4 and 6, this leave two other possibilities:

One cycle of length 10 or
Two cycles, each of length 5

This means that these are the only ways that permutations can occur. There is a one-to-one relationship between cycles and permutations. It is easier to work with cycles in this problem because cycles are mutually exclusive sets.

The probability the cycle with length 10 is clear I think (in your solution).
The one with two cycles is more complicated.

Each cycle of length 5 has 4! permutations. And each of these five has
$$
\binom{10}{5}
$$
ways to arrange the left shoe within each cycle. But when you arrange these, there is automatically an arrangement in the 2nd cycle by the shoes remaining. To compensate, we divide this by 2. So the final probability is
$$
\large{
\cfrac{\binom{10}{5}4!4!}{2\times10!}
}
$$

This was a difficult problem, even if you knew to use cycles. It took me some time to understand this solution.

I hope my notes about this helps you.