Can You Fold All Your Socks?

Riddler Classic

From Anna Kómár comes a stumper about socks:

In my laundry basket, I have 14 pairs of socks that I need to pair up. To do this, I use a chair that can fit nine socks, at most. I randomly draw one clean sock at a time from the basket. If its matching counterpart is not already on the chair, then I place it in one of the nine spots. But if its counterpart is already on the chair, then I remove it from the chair (making that spot once again unoccupied) and place the folded pair in my drawer.

What is the probability I can fold all 14 pairs without ever running out of room on my chair?

Extra credit: What if I change the number of pairs of socks I own, as well as the number of socks that can fit on my chair?

Solution

Let:

• $p$ be the number of pairs of socks in the laundry basket.
• $u$ be the number of unoccupied spots on the chair.
• $f$ be the number of filled spots on the chair, awaiting its single counterpart in the laundry basket. Note that there are $f$ unpaired socks in the laundry basket, in addition to the $p$ pairs.
• $P(p, u, f)$ be the probability that all $p$ pairs can be folded without running out of room. Note that initially, $f = 0$.

I came up with a recursive definition. Every time a sock is drawn from the laundry basket, one of two things can occur.

Sock is placed on the chair.

If a sock is drawn, its counterpart is not on the chair, and there is availability on the chair, then the sock is placed on the chair. As a result:

• $p$ is decreased by 1.
• $u$ is decreased by 1.
• $f$ is increased by 1.
• The probability that a sock is drawn and its counterpart is not on the chair is $\dfrac{2p}{2p+f}$.

Sock is matched with counterpart already on the chair.

If a sock is drawn and its counterpart is on the chair, then the socks are matched and removed. As a result:

• $p$ remains the same.
• $u$ is increased by 1.
• $f$ is decreased by 1.
• The probability that a sock is drawn and its counterpart is on the chair is $\dfrac{f}{2p+f}$.

If at any point in the chore the number of unoccupied spots is greater than or equal to the number of pairs of socks remaining in the laundry basket ($u \ge p$), then $P(p, u, f) = 1$.

Otherwise, $$P(p, u, f) = \dfrac{2p}{2p+f} \cdot P(p-1, u-1, f+1) + \dfrac{f}{2p+f} \cdot P(p, u+1, f-1)$$

Note that if there is no availability remaining, the first term in the above sum is 0.

Answer

$$P(14, 9, 0) \approx 0.7005$$

Extra Credit

Using my recursive algorithm, I determined the following values.

		Unoccupied Spots on Chair
		1	2	3	4	5	6
Pairs of Socks	1	$$1$$	$$1$$	$$1$$	$$1$$	$$1$$	$$1$$
	2	$$\dfrac{1}{3}$$	$$1$$	$$1$$	$$1$$	$$1$$	$$1$$
	3	$$\dfrac{1}{15}$$	$$\dfrac{9}{15}$$	$$1$$	$$1$$	$$1$$	$$1$$
	4	$$\dfrac{1}{105}$$	$$\dfrac{27}{105}$$	$$\dfrac{81}{105}$$	$$1$$	$$1$$	$$1$$
	5	$$\dfrac{1}{945}$$	$$\dfrac{81}{945}$$	$$\dfrac{441}{945}$$	$$\dfrac{825}{945}$$	$$1$$	$$1$$
	6	$$\dfrac{1}{10395}$$	$$\dfrac{243}{10395}$$	$$\dfrac{2403}{10395}$$	$$\dfrac{6675}{10395}$$	$$\dfrac{9675}{10395}$$	$$1$$

1 Unoccupied Spot

Every draw from the laundry basket must be immediately followed by randomly drawing the matching counterpart from the laundry basket to ensure a spot on the chair for the next sock.

$$P(p, 1, 0) = \left(\dfrac{2p}{2p} \cdot \dfrac{1}{2p-1}\right) \cdot \left(\dfrac{2p-2}{2p-2} \cdot \dfrac{1}{2p-3}\right) \cdot \left(\dfrac{2p-4}{2p-4} \cdot \dfrac{1}{2p-5}\right) \cdot\cdot\cdot \left(\dfrac{4}{4} \cdot \dfrac{1}{3}\right) \cdot \left(\dfrac{2}{2} \cdot \dfrac{1}{1}\right)$$

$$ = \dfrac{1}{2p-1} \cdot \dfrac{1}{2p-3} \cdot \dfrac{1}{2p-5} \cdot\cdot\cdot \dfrac{1}{3} \cdot \dfrac{1}{1}$$
$$ = \dfrac{1}{2p-1} \cdot \dfrac{1}{2(p-1)-1} \cdot \dfrac{1}{2(p-2)-1} \cdot\cdot\cdot \dfrac{1}{2(2)-1} \cdot \dfrac{1}{2(1)-1}$$
$$ =\prod_{i = 1}^{p} \frac{1}{2i-1} $$

2 Unoccupied Spots

From the table above, it seems that

$$P(p, 2, 0) = \frac{3^{p-1}}{\prod_\limits{i = 1}^{p} (2i-1)}$$

I could not determine any other explicit definitions.

Rohan Lewis

2022.10.09

Code can be found here.