At Least I Have 2 Shoes, Even If They Do Not Match

Hi, this is my facebook id, which I had earlier deactivated. Actually, after 2 incorrect attempts, I answered 0.089 instead of 0.0089 in excitation. Here is the solution:

First , it is very simple and clear that the total number of possible ways is $(5!)^2$ . (Permutate 5 left and 5 right shoes).

Now, let us evaluate the favourable ways.

Say, all 5 people picked their left shoe. Then, the 5 right shoes can be distributed in $5! \bigg(1-1/1! + 1/2! \dots -1/5!\bigg) =44$ ways using dearrangement theorem.

Now, it is not possible that 4 people pick their left shoe. This is because the one who picks a right shoe has to pick a left one now, but only 1 right shoe is left, and that is his own.

Now, say 3 people pick left and 2 pick right. Hence, the left shoes remaining are to be dearranged in two people(who had picked their own right), and the right shoes left are to be dearranged in 3 people. Also, we have to select 3 people who pick left. Hence, number of ways = ${5 \choose 2} \times 2!\bigg(1 - 1/1! + 1/2!\bigg)\times 3! \bigg(1-1/1!+1/2!-1/3!\bigg) = 20$

Now, by symmetry, if all 5 pick right then, number of ways is 44, and if 3 pick right and 2 left, then number of ways is 20.

Hence, required probability = $\frac{44+20+44+20}{(5!)^2} = \frac{2}{225} = 0.0088888888888 \dots$

Here is a general solution for $N$ people.

Suppose everyone has selected shoes such that each person has exactly one correct shoe. Let $m$ be the number of people who have the correct left shoe.

How many ways can this happen? There are $\binom{N}{m}$ ways of choosing the $m$ people to have the correct left-foot shoe. Now, there must be $N-m$ people with the wrong left-foot shoe. The number of ways of arranging the wrong left-foot shoes is is called a derangement of the $N-m$ people, denoted $d_{N-m}$ .

Since each person has one correct shoe, there must be $m$ people with the wrong right-foot shoe, so there are $d_m$ ways of arranging the right-foot shoes.

Adding up all cases, we find that the number of arrangements is $\sum_{m=0}^{N}{ \binom{N}{m} d_{m} d_{N-m} }$

To convert to a probability, we divide by the total number of ways of randomly assigning shoes , since each way has an equal chance of occurring. This is $N!$ for the left-foot shoes and $N!$ for the right-foot shoes, for a total of:

$P(N) = \frac{\sum_{m=0}^{N}{ \binom{N}{m} d_{m} d_{N-m} }}{{N!}^2}$

In the $N=5$ case this gives us $2(d_5 + \binom{5}{2}d_2 d_3) / {120}^2 = \boxed{2 \over 225}$ . (I consulted a table to find $d_5 = 44$ ).

case1: for all of them to get their right shoe right, they have to get the left wrong. there are 44 ways to do this.
case 2:3 get their right shoe correct two get their left .there are 10 ways to select the people and two ways to select the wrong shoes. total 2 * 10=20.
the problem is symmetric with respect to left and right, hence favourable outcomes=2(20+44)=128.
total possible outcomes= 5!*5!.
probability =128/14400

Total (5!)(5!) ways of assigning shoes. If all 5 correct left shoes, then all 5 wrong right shoes, which can be given in (5! - no. of 4 correct - no. of 3 correct - no. of 2 correct - no. of 1 correct) = (5! - 1 - 0 - 20 - 40 - 15) = 44 Only 4 correct shoes cannot be given , as the other will be left with correct only. If 3 correct left shoes, then in the similar fashion can be shown that the number is 20. Similarly. 3 correct right + 2 correct left = 20 5 correct right = 44 Total 44+20+20+44 combinations out of (5!)(5!) that makes 0.008888888...

We define $P_n$ the probability that when n people leave, they all have exactly one of their own shoes.

We define $Q_n$ the probability that when n people leave, they all have exactly one of their shoes, supposing one of the right shoes has been replaced with a stranger's one.

First, let's determine $Q_n$ :

The one with the missing right shoe (let's name him Pierre) must take his left shoe: $\frac{1}{n}$ . For his right shoe, (1) he can take the stranger's shoe $\frac{1}{n}$ or (2) he can take another one, let's say the one that belongs to François $\frac{n-1}{n}$ . In case (1), we're left with $n-1$ people and their shoes, which lead to probability $P_{n-1}$ . In case (2), we're left with $n-1$ people and their shoes, but still with the stranger's right shoe replacing now François' shoe: that is $Q_{n-1}$ .

$Q_n=\frac{1}{n}(\frac{1}{n}P_{n-1} + \frac{n-1}{n}Q_{n-1})\hspace{3cm}(i)$

Let's determine $P_n$ :

The first one to leave (let it be Pierre) can take his own left shoe or his own right shoe (2 symmetrical ways). The probability is then $\frac{1}{n}$ for his own shoe and $\frac{n-1}{n}$ for the other one. We're left with $n-1$ people with their shoe, one of their shoe replaced with Pierre's one. It doesn't matter if it a right or a left shoe missing, it the same probability $Q_{n-1}$ .

$P_n=2\frac{1}{n}\frac{n-1}{n}Q_{n-1}\hspace{3cm}(ii)$

Therefore, from (ii), we have :

$Q_{n-1}=\frac{1}{2}n\frac{n}{n-1}P_{n}\hspace{3cm}(iii)$

Substituing in (ii) $Q_{n-1}$ with (i):

$P_n\,=\,2\frac{1}{n}\frac{n-1}{n}( \frac{1}{n-1}(\frac{1}{n-1}P_{n-2} + \frac{n-2}{n-1}Q_{n-2} ))$

Substituing in the latter $Q_{n-2}$ with (iii): $P_n\,=\,2\frac{1}{n}\frac{n-1}{n}( \frac{1}{n-1}(\frac{1}{n-1}P_{n-2} + \frac{n-2}{n-1} ( \frac{1}{2}(n-1)\frac{n-1}{n-2}P_{n-1} )) )$

Recursive formula for $P_n$ :

$P_n\,=\,\frac{1}{n^2}( (n-1)P_{n-1} + \frac{2}{n-1}P_{n-2} )$

Using it with $P_0=1$ and $P_1=0$ , we have:

$P_2=\frac{1}{2}$ , $P_3=\frac{1}{9}$ , $P_4=\frac{1}{24}$ , $P_5=\frac{2}{225}$ .

---

Why Pierre and François? For Pierre Richard and his character name François Perrin in The Tall Blond Man with One Black Shoe :)