# Feller shoe-matching problem

This problem have been taken from the book' An Introduction to Probability Theory and Its Applications' by Williams Feller(1906-1970)

Note:- Assume in each case that all possible arrangements have the same probability.

Ten pair of shoes are in a closet. Four shoes are selected at random.Find the probability that there will be at least one pair among the four shoes selected

Solution:-

Answer provided by the author is $$\frac{\binom{55}{2}}{\binom{20}{4}}=\frac{1485}{4845}=\frac{99}{323}$$

we want to find the probability that there will be at least one pair of shoes among the four shoes selected which is equal to the probability that remains after deducting the probability of no pairs of shoes among the four shoes selected from the total probability. Let us calculate the probability of picking 1st,2nd,3rd and 4th shoes so that there are no pairs.

The probability of 1st shoes 20/20

2nd shoes 18/19, 3rd shoes 16/18 and 4th shoes 14/17. If we deduct the product of these result from the total probability, we get the our desired result.i-e $$1-\frac{20*18*16*14}{20*19*18*17}=\frac{99}{323}$$ combination

• As this is self study, please add the self-study tag to the question and edit your question to explain in words the thinking behind your proposed solution. That way an answer could help explain not only which answer is correct but also why one is wrong. – EdM Sep 21 '18 at 15:24
• What is the rationale for your formula? If you can justify it using the axioms of probability, it's likely correct; but if you cannot find a justification, you have no basis to suppose it is right. (BTW, Feller's answer is correct.) – whuber Sep 21 '18 at 15:39

Comment: Here is a simulation in R of a million draws of four shoes from the closet. In the closet each pair has its own number from 1 to 10. If my draw results in exactly four uniquely different numbers, I have no pairs. Otherwise, I have at least one pair. The vector nr.unique has a million entries, each of which can be a number from 2 (I drew 2 pairs of shoes) through 4 (no pairs).

The vector nr.uniq < 4 is a 'logical' vector containing TRUEs and FALSEs. Its mean is its proportion of TRUEs.

With a million draws the margin of simulation error should be less than 0.001 in 95% of such simulations. Results agree with Feller's answer.

set.seed(921)
closet = rep(1:10, 2)
nr.uniq = replicate( 10^6, length(unique(sample(closet,4))) )
mean(nr.uniq < 4);  99/323
[1] 0.306618      # simulated result