Pairing Socks

Samuel takes the $10$ socks in some order. He wears the first two on Monday, the second two on Tuesday, and so on.

There are $\frac{10!}{2^5} = 113400$ orders in which the $10$ socks can be chosen, all equally likely.

Let $A_j$ be the set of orderings for which Samuel wears matching socks on day $j$ , for $1 \le j \le 5$ .

• for any $1 \le i \le 5$ , if Samuel wears matching socks on day $i$ , then there are $5$ choices of which pair of socks he will wear that day, and then $\frac{8!}{2^4}$ ways of choosing socks for the other four days. Thus $|A_i| \; = \; 5 \times \frac{8!}{2^4} \; = \; 12600$
• for any $1 \le i < j \le 5$ , if Samuel wears matching socks on days $i$ and $j$ ,then there are $5$ choices of colour for the socks on day $i$ , then $4$ choices of colour for the socks on day $j$ , and then $\frac{6!}{2^3}$ ways of choosing the socks on the other three days. Thus $|A_i \cap A_j| \; = \; 5 \times 4 \times \frac{6!}{2^3} \; =\;1800$
• Similarly, for any $1 \le i < j < k \le 5$ , $|A_i \cap A_j \cap A_k| \; = \; 5 \times 4 \times 3 \times \frac{4!}{2^2} \; = \; 360$
• Similarly, for any $1 \le i < j < k < m \le 5$ , $|A_i \cap A_j \cap A_k \cap A_m| \; =\; 5 \times 4 \times 3 \times 2 \times \frac{2!}{2} \; = \; 120$
• Finally $|A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5| \; = \; 5 \times 4 \times 3 \times 2 \times 1 \; = \; 120$

Using the Inclusion-Exclusion Principle, we deduce that $\begin{aligned} \big|A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5\big| & = 5 \times 12600 - 10\times1800 + 10\times360 - 5\times120 + 120 \\ & = 48120 \end{aligned}$ Thus the probability that Samuel never wears a pair of matching socks is $\frac{113400 - 48120}{113400} \; = \; \frac{544}{945}$ making the answer $544 + 945 = \boxed{1489}$ .