Socks on a clothing line

Question

Recently I was putting some socks on the clothing line after taking them from the laundry machine and I while I was doing that I came up with an interesting math problem.

I usually wash $30$ or so socks (amounting for $15$ or so pairs) and then I start putting them on clothing lines. On one clothing line I can put at most $8$ socks. Here's my method of ordering: I pick a random sock and I put it on the first line, in the same time "reserving" the place after it for it's partner. Next I pick another random sock and if it's partner is already on one of the lines I just put it in the already reserved place, otherwise I put it in the next free place. First I tend to use all the free space on the first line, then on the second and so on. For example if I have something like $x-x-x-x-$ on the first line (where $x$ is a slot filled with a sock and $-$ is an empty slot, reserved for the partner of the sock ahead of it) and I pick up a new sock from the basket then I will put it on the second line and so on.

Once while doing this I started wondering: what is the probability of filling the first line with $8$ socks before any other line is filled? What about the second line being filled first, and so on? Unfortunately I haven't been able to get anywhere close to a solution. In order to avoid inconvenience I assume I have $8n$ socks, where $n$ is the number of clothing line. My idea was to number the pairs and shuffle the $8n$ numbers, order them in a line and then look at the probability of the first four distinct numbers finding their partner before any other set of four doing it, as we go along the line of shuffled numbers. Unfortunately things start to get complicated and I can't achieve anything.

I even thought of calculating the probability of the first line NOT filling first. I set the position of the last sock from the first line to be $n$ and then I try to find all combinations of putting $4$ other pairs between the first and $n-$th place. But the calculation of this number isn't easy and I'm afraid of double counting.

Anyway I wrote a computer program and here's what I've got for which number will be filled first for $32$ socks and $4$ lines, running it three times for various amounts of tries:

$$ \begin{array}{c|lcr} Line & \text{#1} & \text{#2} & \text{#3} \\ \hline 1 & 4168 & 8388 & 21041 \\ 2 & 3281 & 6394 & 16634 \\ 3 & 2077 & 4243 & 10735 \\ 4 & 469 & 984 & 2632 \\ \hline Total & 9995 & 20009 & 51042 \end{array} $$

Answer 1

EDIT: As pointed out in the comments, this solution is flawed.

Let $l$ be the number of lines, and let $s$ be the number of pairs of socks allowed in a line (in the case of the question, 8), and let $p$ be the number of socks in a pair (in this case 2). So, we should have $lsp$ socks.

Let $P_l$ denote the probability that line 1 gets finished first (in theory this method can be generalized to find the probability that the $n$th line gets finished first, but it becomes messier). I will describe a way to calculate $P_l$ recursively (note that this is probably not the best way; see my comment to this answer. However, this method is feasible and I would calculate it in your case if I did not have to leave soon; I will come back to this.).

$P_1=1$.

For larger values of $l$, we may use the principle of inclusion exclusion as follows:

\begin{align*} &P(\textrm{first line finishes before at least one other line})\\ &=\sum_{S\subseteq\{2,3,\dots,n\}}(-1)^{\lvert S\rvert+1}P(\textrm{first line finishes before all lines in } S)\\ &=\sum_{S\subseteq\{2,3,\dots,n\}}(-1)^{\lvert S\rvert+1}P_{\lvert S\rvert+1}\\ &= \sum_{i=1}^{n-1}\binom{n-1}{i}(-1)^{i+1}P_{l+1}. \end{align*}

(To get from the second line to the third line, interpret $i$ as $\lvert S\rvert$, so while the second line sums overt all sets, the third line sums over all possible sizes of the sets. The factor of $\binom{n-1}{i}$ counts the number of sets of size $i$.)

If we rearrange, we can get $P_l$ in terms of lower values of $P_l$ and the probability that the first line finishes before at least one other line.

To calculate the probability that the first line finishes before at least one other line, take 1 minus the probability that the first line finishes last. This is the probability that the last sock comes from one of the first $s$ pairs. This is equal to the probability that the last sock comes from the first pair, plus the probability that it comes from the second pair, plus... plus the probability that it comes from the $s$th pair.

To calculate the probability that the last sock comes from the $k$th pair, this is equal to the probability that the last sock does not come from the first $k-1$ pairs multiplied by the probability that it comes from the $k$-th pair given that it does not come from the $k$-th pair.

To calculate this, it is enough to calculate the probability that the last sock comes from the first pair where there are an arbitrary number of pairs. This is easy, because there are $ps-1$ socks that could be the last and there are $p-1$ remaining socks from the first pair (after the first one), so this probability is $\frac{p-1}{ps-1}$.

Answer 2

EDIT: This solution is also wrong.

This solution generalizes to an arbitrary number of lines, pairs per line, and socks per pair. But the amount of work required increases dramatically as socks per pair goes up, unless we can find a way to get rid of the casework.

Given a random permutation of the socks, name the socks $1_1,1_2,2_1,2_1,3_1,3_2,4_1,4_2,L_{1,1},L_{1,2}\dots,L_{1,7},E_1,L_{2,1},L_{2,2}\dots,L_{2,7},E_2,\dots,E_{\frac{n}{4}-1}$ (where $n$ is the number of pairs) as follows: Say that the first 4 pairs that get introduced are pair $1$, $2$, $3$, and $4$ (so they make up the first line). $1_1$ is then the first sock that gets introduced, and $1_2$ is the other sock in its pair, and the same for $2$, $3$, and $4$.

Now let $E_1$ be the last sock that gets put up on the first line to finish that is not the first line (regardless of whether the first line finishes first or not), $E_2$ the last sock that gets put up on the second line to finish that is not the first line, etc. Finally, label the rest of the socks from the first line to finish that is not the first line $L_{1,1}$ to $L_{1,7}$ randomly, and do a similar thing for the rest of the lines.

Example (order generated by http://www.jerrydallal.com/random/random_permutation.htm):

If the socks come in the following order (where two socks are in the same pair if they have the same letter)

lhcdiidjeaelkfcfakbgghbj

becomes

$1_12_13_14_1L_{2,2}L_{2,4}4_2L_{2,5}L_{2,7}L_{2,3}L_{2,6}1_2L_{1,5}L_{1,3}3_2L_{1,4}L_{2,1}L_{1,2}L_{1,7}L_{1,1}L_{1,6}2_2E_1E_2$

(In general, $E_1$ will not be the second last, but $E_{\frac{n}{4}-1}$ will be the last unless one of the socks from one of the first 4 pairs is the last.)

The first line is the first line to be finished if and only if $1_2,2_2,3_2,$ and $4_2$ all occur before $E_1$ (and hence before $E_2$, etc. as well).

All possible resulting permutations of $1_1,\dots,E_{\frac{n}{4}-1}$ are equally likely because they all come from the same number of permutations of the socks. (EDIT: The flaw is here; they are not equally likely. It is difficult to put in words how though.)

So, to calculate the probability that the first line finishes first, we will calculate the number of possible permutations where $1_2,2_2,3_2,4_2$ all come before $E_1$, and then divide by the number of possible permutations.

To calculate the number of possible permutations:

Any possible permutation has the following structure:

Take $1_1,2_1,3_1,4_1,E_1,E_2,\dots,E_{\frac{n}{4}-1}$ and then add the rest of them. $1_2$ comes after $1_1$, and the same for $2,3,$ and $4$. $L_{i,j}$ must come before $E_i$ and after $4_1$ (and hence after $1_1,2_1,3_1$ as well).

To count this: start by adding the $L_{1,j}$ one at a time, then the $L_{2,j}$ one at a time, etc. and then add $4_2,$ then $3_2$, then $2_2$, then $1_2$.

For the $L_{i,j}$, there are

\begin{align*} &1*2*\dots*7*9*10*\dots*15*17\dots*2n-9\\ &=\frac{(2n-8)!}{8*16*\dots*(2n-8)}\\ &=\frac{(1)_{2n-8,1}}{(8)_{\frac{n}{4}-1,8}} \end{align*}

ways where $(x)_{n,k}$ is the Pockhammer k-symbol (I'm using this symbol because we're going to see a lot of sums like this later). There are then $2n-7$ places to put $4_2$, $2n-5$ places to put $3_2$, $2n-3$ places to put $2_2$, and $2n-1$ places to put $1_2$. So in total there are

$$\frac{(1)_{2n-8,1}(2n-7)(2n-5)(2n-3)(2n-1)}{(8)_{\frac{n}{4}-1,8}}=\frac{(1)_{2n-8,1}(2n-7)_{4,2}}{(8)_{\frac{n}{4}-1,8}}$$

possible permutations.

To calculate the number of possible permutations where the first line finishes first:

We split into 5 cases, dependent on how many of the socks from the first 4 pairs show up after $4_1$.

By direct computation, for each integer $1\le i\le4$, the number of permutations of $1_12_13_14_11_22_23_24_2$ which are possible where $i$ of them are after $4_1$ is (0 is impossible because $4_2$ comes after $4_1$):

$i=1:15$

$i=2:30$

$i=3:36$

$i=4:24$

(I did this by computer. My code is in the appendix.)

For each case, all that's left to do is place the $L_{i,j}$. In all cases, we will choose positions for the $L_{1,j}$ first, one at a time, then $L_{2,j}$, etc.

Case $i=1$:

\begin{align*} &2*3*\dots*8*10*11\dots*16*18\dots*2n-8\\ &=\frac{(2n-7)!}{9*17*\dots*(2n-7)}\\ &=\frac{(2)_{2n-8,1}}{(9)_{\frac{n}{4}-1,8}} \end{align*}

ways.

Case $i=2$:

\begin{align*} &3*4*\dots*9*11*12\dots*17*19\dots*2n-7\\ &=\frac{(2n-6)!}{10*18*\dots*(2n-6)}\\ &=\frac{(3)_{2n-8,1}}{(10)_{\frac{n}{4}-1,8}} \end{align*}

ways.

Case $i=3$:

\begin{align*} &4*5*\dots*10*12*13\dots*18*20\dots*2n-6\\ &=\frac{(2n-5)!}{11*19*\dots*(2n-5)}\\ &=\frac{(4)_{2n-8,1}}{(11)_{\frac{n}{4}-1,8}} \end{align*}

ways.

Case $i=4$:

\begin{align*} &5*6*\dots*11*13*14\dots*19*21\dots*2n-5\\ &=\frac{(2n-4)!}{12*20*\dots*(2n-4)}\\ &=\frac{(5)_{2n-8,1}}{(12)_{\frac{n}{4}-1,8}} \end{align*}

ways.

In total:

$$15*\frac{(2)_{2n-8,1}}{(9)_{\frac{n}{4}-1,8}}+30*\frac{(3)_{2n-8,1}}{(10)_{\frac{n}{4}-1,8}}+36*\frac{(4)_{2n-8,1}}{(11)_{\frac{n}{4}-1,8}}+24*\frac{(5)_{2n-8,1}}{(12)_{\frac{n}{4}-1,8}}$$

possible permutations where the first line finishes first.

Finally, our answer is:

$$\boxed{\frac{15*\frac{(2)_{2n-8,1}}{(9)_{\frac{n}{4}-1,8}}+30*\frac{(3)_{2n-8,1}}{(10)_{\frac{n}{4}-1,8}}+36*\frac{(4)_{2n-8,1}}{(11)_{\frac{n}{4}-1,8}}+24*\frac{(5)_{2n-8,1}}{(12)_{\frac{n}{4}-1,8}}}{\frac{(1)_{2n-8,1}(2n-7)_{4,2}}{(8)_{\frac{n}{4}-1,8}}}}.$$

In the case of 32 socks, by plugging into WolframAlpha, the numerator becomes 58301463783867752448000000 and the denominator becomes 122559766074795905856000000 and the exact result becomes 1323392/2781999 or about 0.476. In comparison, the asker's data gives (4168+8388+21041)/(9995+20009+51042) which is about 0.41, which suggests that, almost certainly, either I made a mistake or the asker's pseudorandom number generator has some patterns (if my answer were exact, this result is something like 35 standard deviations below the mean). Given this, I might try to calculate small exact values at some point, but I'm too tired right now.

Appendix:

import java.util.*;
import java.lang.*;

class Rextester//Needless to say, I wrote this code on Rextester
{  
    public static void main(String args[])
    {
        int[] amounts = new int[4];
        for(int i = 0; i < 105; i++) {
            int one = i%7;
            int two = (i/7)%5;
            int three = (i/35);
            ArrayList<Integer> construct = new ArrayList<Integer>();
            construct.add(1);
            construct.add(2);
            construct.add(3);
            construct.add(4);
            construct.add(5);

            construct.add(3+three,6);
            construct.add(2+two,7);
            construct.add(1+one,8);

            amounts[sort(construct)-1]++;
        }
        System.out.println(Arrays.toString(amounts));
    }

    public static int sort(ArrayList<Integer> construct){
        return 7-construct.indexOf(4);
    }
}