There are $6$ pairs of shoes - $2$ pairs red, $2$ pairs blue and $2$ pairs green. $6$ people come and randomly pick a right shoe and a left shoe. What is the probability that none of them have two shoes of the same colour?

I tried as follows:

We define $A_i:$ as the event that the $i^{th}$ person is colour co-ordinated, $i=1,2,3,4,5,6$

Then we are to find $P(\bigcap_{i=1}^6 A_i^c)$. Now, $$P(\bigcap_{i=1}^6 A_i^c)=P(\bigcup_{i=1}^6 A_i)^c=1-P(\bigcup_{i=1}^6 A_i)$$ and use the inclusion-exclusion equality on $$1-P(\bigcup_{i=1}^6 A_i)$$ Now $$P(\bigcup_{i=1}^6 A_i)=\sum_{r=1}^6 (-1)^{r-1}S_r$$ $$ where S_r=\sum_{1\le i_1\le i_2\le....\le i_r} P(\bigcap_{j=1}^r A_{i_j})\quad r=1,2,...,6$$ But I am struggling to evaluate the $S_r$ quantities...


2 Answers 2


$$ \text{where} \ S_r=\sum_{\color{red}{1\leq i_1< i_2<....< i_r\leq 6}} P(\bigcap_{j=1}^r A_{i_j})\quad r=1,2,...,6$$ But I am struggling to evaluate the $S_r$ quantities...

In my answer I´m focussing on the interpretation of the formula.

First see the red marked indices. Especially the signs. You have to order the sets. First of all we have $i_j\in \{1,2,3,4,5,6 \}$.

For $r=2$ we have the following probabilities:

$P(A_1 \cap A_2 )+P(A_1 \cap A_3 )+P(A_1 \cap A_4 )+P(A_1 \cap A_5 )+P(A_1 \cap A_6 )+P(A_2 \cap A_3 )$

$+P(A_2 \cap A_4 )+P(A_2 \cap A_5 )+P(A_2 \cap A_5 )+P(A_3 \cap A_4 )+P(A_3 \cap A_5 )+P(A_3 \cap A_6 )$

$+P(A_4 \cap A_5 )+P(A_4 \cap A_6 )+P(A_5 \cap A_6 )$

You see that the first index is always smaller than the second index. The short notation is $$\sum\limits_{i=1}^{5} \sum\limits_{j>i}^6 P(A_i \cap A_j)$$

To see how to calculate the number of combinations you can imagine a table like below

$$\begin{array}{|c|c|c|c|c|c|c|} \hline &1&2&3&4&5&6 \\ \hline 1&&x&x&x&x&x \\ \hline 2 &&&x&x&x&x \\ \hline 3 &&&&x&x&x \\ \hline 4 &&&&&x&x \\ \hline 5 &&&&&&x \\ \hline 6 &&&&&& \\ \hline\end{array}$$

You count the cells above (or below) the diagonal. It can be calculated by subtracting the diagonal from the number of all cells and dividing the result by $2$: $\frac{n^2-n}{2}=\binom{n}{2}=\binom{6}{2}=15$


You're making a huge detour by focusing on the persons. You should be focussing on the shoes.


More explicitly, consider the first left red shoe. The probability that it doesn't get matched with a right red shoe is $\frac46=\frac23$.

For the second left red shoe, there are two inequivalent possibilities.

It can get matched with another right shoe of the same colour as the first left red shoe got matched with, with probability $\frac15$, and then only $1$ of the remaining $6$ colour pairings avoids a matching, for a contribution $\frac15\cdot\frac16$.

Or it can get matched with a right shoe of the third colour, with probability $\frac25$. Then we can pick one of two left blue shoes to pair it with the remaining right green shoe and one of two left green shoes to pair it with the remaining right blue shoe, and the other left green and left blue shoes can be paired with the right red shoes in either order, so $8$ of the remaining $24$ shoe pairings avoid a matching, for a contribution $\frac25\cdot\frac13$.

Thus, in total, the probability to avoid a matching is

$$ \frac23\left(\frac15\cdot\frac16+\frac25\cdot\frac13\right)=\frac19\;. $$

  • 1
    $\begingroup$ When focusing on shoes I could think of it as a matching problem where a particular coloured right shoe matches with the same coloured left shoe, but it is not like the regular matching problem as the shoes of any particular foot are not unique. So I am getting stuck there as well. $\endgroup$
    – Neel
    Jul 25, 2018 at 11:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .