Suppose we have a closet with n pairs of shoes. n people will randomly pick 2 shoes from the closet. What is the probability that all of them will have 1 right shoe and 1 left shoe?
My approach to this question was like this:
We have $C(2n,2)\times C(2n-2,2) \times…\times C(2,2)$ ways for n people to choose all of the shoes.
Now, I can calculate the number of ways that none of the n people will have 1 left and 1 right. Meaning, I can calculate the ways that all n people will either have 2 right or 2 left. Then I will take the complement and divide by the number of total ways that n people can choose 2n shoes randomly
Another approach is to count the number of ways that all of them will have both right and left however I don't know how to approach it.
I thought that the first person has n ways to choose say right pair, and n ways to choose left. The second has n-1 * n-1 and so on. We get n!*n! but I am not sure if this approach is correct.
Also, Can I solve it using probability and not use counting? For instance say I have n/2n for the first person to choose a right pair, then for the left 1/n. How do I continue?
Best Answer
Alternative approach:
The probability will be expressed as
$$\frac{N}{D},$$
where it is construed that order of selection of each shoe is deemed relevant. Since this construance will be consistently applied to both the numerator and denominator, the approach is valid.
Then you have that the denominator is
$$D = (2n)!.$$
So, the problem reduces to computing the numerator.
Put the left shoes on the left side of the room, and the right shoes on the right side of the room. On each side of the room, order the $~n~$ shoes in some specific order. So, you have
Then, arbitrarily label the people Person-1, Person-2, ..., Person-n, where Person-k will be the $~k$-th person to enter the room. The $~k$-th person will automatically be assigned Left-Shoe-k and Right-Shoe-k.
So, there are two things that determine each person's selection of two shoes:
The number of different ways of randomly ordering the shoes, which is $~(n!)^2.~$
For each person, whether they select a left shoe first, or a right shoe first. This computation is represented by $~2^n.$
Therefore,
$$N = (n!)^2 \times 2^n.$$
Therefore, the probability is
$$\frac{N}{D} = \frac{(n!)^2 \times 2^n}{(2n)!}.$$
$\underline{\text{Addendum}}$
Note that in the first part of the answer, I ignored that there are $~n!~$ ways of ordering the people. This is because, in my analysis, it is irrelevant which person got which shoes.
That is, there are $~(2n)!~$ ways of ordering the selection of shoes. In this ordering, it is irrelevant which person gets the first shoe, which person gets the second shoe, and so forth. This is how the denominator of $~(2n)!~$ is computed.
So, to be consistent, in the computation of the numerator, I must regard it as irrelevant which person was designated as Person-1, which person was designated as Person-2, and so forth.
So, in the computation of the numerator, consistent with the computation of the denominator, the only thing that counts is the order of selection of the shoes, not which person got which shoes.