First let me paste the question.

This problem is based on an (almost) true story. A child, who shall remain nameless, has a large pile of clean socks. This pile contains m pairs of socks with pictures and patterns and n pure white socks. Each pair of socks consists of two identical socks and every pair is unique — no two pairs look the same. All pure white socks are identical. Each day, the child randomly selects two socks from the pile, puts them on, and heads for school. But today is a picture day and the child needs to wear two identical socks. So the child randomly selects two socks and if both socks are identical, the child puts them on and heads out the door. If the two socks are not identical, the child throws the socks into the laundry basket (they are now dirty — don’t ask why) and continues the same process of randomly selecting two socks from the pile of remaining clean socks. As this process continues, the parents are starting to get worried: Will this child ever make it to school today? Please help them to compute the probability that the child will not find a pair of identical socks using this process. This problem is based on an (almost) true story.

First of all, the limitations are n<=500 pairs of socks, and m<=200 white socks. I've really tried to solve question every way i can. I used permutation of 7! and then count the paired socks. At test problem, there are 3 white and 2 paired socks. I could only solve this by counting all paired socks in 7! permutations. Which is O(n^n) and really inefficient. Can you help me how i can solve this question? I used python by the way, and this is a competitive programming question.

I'm just solving these questions for fun, it's an open question. I've really tried 2 days to solve this, but still couldn't. Appreciate any help.

At initial test answer, there are 3 white socks and 2 paired socks (total of 7 socks). And the answer is:0.457142857142857 Mar 23 21 views

## 1 answer to this question.

Another way to look at the problem is that the child pulls pairs of socks until there are none or just one left, then looks for a matching pair. Calculate the solution using Probability 101 after computing Pr(no pair is a white match) and Pr(no pair is a patterned match | no pair is a white match).

Pr(no pair is a white match): If and only if m+2 >=2n, a white match is assured. If m+2 <2n, no pair is a white match unless and until either m is odd and there are exactly mpairs with exactly one white sock and the leftover sock is white, or m is even and there are exactly m-1 pairs with exactly one white sock and the leftover sock is white.
Consider the patterned socks to be indistinguishable for this calculation. The socks can be drawn in (m + 2n) different ways. When m is even, count the number of ways to draw the socks without a white pair as (m/2 + n) pick m ways to choose pairings with a white sock times 2m ways to draw those pairs. When m is odd, we obtain (((m1)/2 + n) select (m-1)) *2m-1 ways to have a white leftover sock and ((m1)/2 pick m) 2m ways to have a patterned leftover sock.

Pr(no pair is a patterned match | no pair is a white match): I'll take care of the situation where m is even, and you or someone else can take care of the other case. We have a total of m/2 + n pairs, with m containing exactly one white sock and n -m/2 pairs containing two patterned socks. The alternating sum is obtained by using inclusion-exclusion on subsets of matching patterns.

```        i                    1            1                  1
∑  (−1)  (m choose i) (---------- × ---------- × … × ---------------)
i≥0                     2n + m − 1   2n + m - 3       2n + m - 2i + 1```

If the number of ways to choose the I patterns is m choose I and the probability that all I are matched is the product (for each pattern in some order, we reveal the first sock and then compute the probability that its mate matches).

The odd case works similarly to the other examples, except that we divide them into groups based on whether the residual sock is white or not. answered Mar 25 by
• 6,000 points

## probability of getting three of a kind by drawing 5 cards

from collections package import counter to count ...READ MORE

## Simple algorithm for generating random numbers with bigger/smaller probability

To move the density in one way, ...READ MORE

## Calculate Z-Score from Probability Value - R programming

It's named qnorm qnorm(p=0.841344746068543) Output 1 The following family of functions ...READ MORE

## Example to run KNN algorithm using python

Have a look at this one: from sklearn.datasets ...READ MORE

+1 vote

## Different data structures in R

The different data types in R are ...READ MORE

+1 vote