Probability that n people will get one right and one left shoes from n pairs of shoes.

Question

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?

Answer 1

Approach I | Probability W/o Too Much of Counting

The first person can choose one right and one left shoe in $2$ ways, each having the same probability. They can can either choose the right shoe first and then the left shoe or the other way round.

The probability of choosing a right shoe to begin with would be $\frac{n}{2n}$ [choosing any of the $n$ right shoes out of the $2n$ shoes]. Then the probability of picking a left shoe would be $\frac{n}{2n - 1}.$

So the probability of the first person choosing one right and one left shoe would be

$$2 \cdot \frac{n}{2n} \cdot \frac{n}{2n-1}$$

Again, multiplying by $2$ because they either start with the left or the right shoe.

At this stage, we have $n-1$ right and $n-1$ left shoes left. Altogether $2n - 2$.

So, for the next person, the probability of selecting one right and one left shoe would be

$$2 \cdot \frac{n-1}{2n-2} \cdot \frac{n-1}{2n-3}$$

Continuing with this, for the last person, the probability would be

$$2 \cdot \frac{1}{2} \cdot \frac{1}{1}$$

Since all of them have to make their choices one after the other, we multiply their individual probabilities. So, the required probability would be

$$ \begin{align*} P \, &= \, 2 \cdot \frac{n}{2n} \cdot \frac{n}{2n-1} \,\, \cdot \,\, 2 \cdot \frac{n-1}{2n-2} \cdot \frac{n-1}{2n-3} \,\, ... \,\, 2 \cdot \frac{1}{2} \cdot \frac{1}{1} \\[0.3cm] &= \frac{2^n \cdot (n!)^2}{(2n)!} \end{align*} $$

And that's it. Let's look at another approach.

---

Approach II | Using Counting

• Calculating Total Possibilities

There are a total of $2n$ shoes. What happens eventually is each person (of the n people) gets paired with $2$ shoes. One way to do this is to arrange all the shoes in a row and assign the first two shoes to the first person, next two to the next person and so on.

Now each set of two shoes (or pair of shoes) can be arranged among themselves in $2! = 2$ ways. And there are $n$ pairs. So, we will need to divide the total number of arrangements by $2^n$ to remove duplication. A person getting a left and a right shoe is the same as them getting the right and the left shoe.

Now, the total number of arrangement of $2n$ shoes is $(2n)!$. So,

$$\text{Total possibilities } = \frac{(2n)!}{2^n}$$

• Number of Acceptable Possibilities

Next, we determine the number of ways in which each person has $1$ right and $1$ left shoe.

Basically this is the same as no two adjacent shoes being of the same side (left or right). This is a simple problem to solve.

We start by arranging the $n$ left shoes in a row. This can be done in $n!$ ways.

Now, we can place one right shoe after each left shoe as shown below, for example.$^{[1]}$

$$L \,\, R \,\, L \,\, R \,\, L \,\, R$$

This way each pair of adjacent shoes (that people will get) will have one right and one left shoe.

And, the $n$ right shoes can be arranged among themselves in $n!$ ways.

So altogether, the number of desired arrangements is

$$\begin{align*} n! \times n! = (n!)^2 \end{align*}$$

• The probability

Hence the required probability would be

$$\begin{align*} \frac{(n!)^2}{\frac{(2n)!}{2^n}} = \frac{2^n \cdot (n!)^2}{(2n)!} \end{align*}$$

---

$^{[1]}$ We may also place one right shoe before each left shoe as shown below.

$$R \,\, L \,\, R \,\, L \,\, R \,\, L$$

But this doesn't make any difference. Each person get the same pair of shoes. As we saw in calculating the total possibilities, left or right doesn't make a difference.

Answer 2

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

• Left-Shoe-1, Left-Shoe-2, ..., Left-Shoe-n.
• Right-Shoe-1, Right-Shoe-2, ..., Right-Shoe-n.

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.

Answer 3

The way I approached this was to calculate the probability of one person getting a "correct" pair, then create a series to calculate the probability of everyone after him also getting a correct pair. Apologies if there are certain professional terms that I didn't use in this answer, but here goes.

Since there are n pairs, then there are n right and n left shoes. The probability for the first person to get a right shoe is

$$ P_1(right) = \frac{n}{2n} = \frac12 $$

And the probability of him getting a left shoe after that is

$$ P_1(left) = \frac{n}{2n-1} $$

Hence, the probability of him getting a correct pair is

$$ P_1(correct) = 2(\frac12\times\frac{n}{2n-1}) = \frac{n}{2n-1} $$

And this is multiplied by 2 since the order of picking a left or right shoe is relevant, and $ P_1(right\space then\space left) = P_1(left\space then\space right) $.

Now, there are $n-1$ pairs left. Logically, to get the probability of everyone else also getting a correct pair, I would keep multiplying by the next term with $n-1$, $n-2$, etc, until $1$:

$$ P_{all}(correct) = \frac{n}{2n-1}\times\frac{n-1}{2(n-1)-1}\times\frac{n-2}{2(n-2)-1}\times...\times\frac{2}{2(2)-1}\times\frac{1}{2(1)-1} $$

But I wanted to check, first, if $\frac{n-1}{2(n-1)-1}$ is indeed the term we get for the next person.

The probability for the second person to get a right shoe is

$$ P_2(right) = \frac{n-1}{2(n-1)} = \frac12 $$

And the probability of her getting a left shoe after that is

$$ P_2(left) = \frac{n-1}{2(n-1)-1} $$

Hence, the probability of her getting a correct pair is

$$ P_2(correct) = 2(\frac12\times\frac{n-1}{2(n-1)-1}) = \frac{n-1}{2(n-1)-1} $$

And this shows that the series $P_{all}$ works. $P_{all}$ will provide the probability of all $n$ people randomly getting a correct pair out of $n$ pairs of shoes.