Matching Socks in Dark Room
Problem
Solution
Let $f(n)$ be the number of pairings of $n$ pairs of socks into acceptable pairs. For $n\le 2$ any pairing is acceptable. Furthermore, $f(1)=1,$ $f(2)=3.$
In general, let's start we a sock of the darkest shade. If we happen to pick a sock of the same shade, we are left with computing $f(n-1).$ Otherwise, there is a pair of socks of the next shade; we can choose any of the two and match the other one with the remaining sock of the darkest shade. This gives a recurrence:
$f(n)=f(n-1)+2f(n-2).$
The characteristic equation of the latter is $x^2-x-2=0,$ with roots $x=2$ and $x=-1.$ The general solution of the recurrence depends on two constants: $f(n)=c_12^n+c_2(-1)^n$ which are found from the initial conditions $f(1)=1,$ $f(2)=3.$ Thus we arrive at
$\displaystyle f(n)=\frac{2^{n+1}+(-1)^n}{3}.$
For $10$ pairs of socks, there are $\displaystyle f(10)=\frac{2048+1}{3}=683$ possible matchings.
To find the sought probability, we have to find the total number of pairings, absent any restrictions.
One sock can be matched with any of $19$ but when that picked, the next sock may match with any of the remaining $17,$ and so on. Thus the total number of pairings is
$19!!=19\cdot 17\cdot 15\cdot\ldots\cdot 5\cdot 3\cdot 1.$
The probability we seek equals $\displaystyle \frac{683}{19!!}\approx 10^{-6}.$
An aside
$f(n)$ could have been found via generating functions. Let's set
$\displaystyle\begin{align}F(x)&=\sum_{n=1}^{\infty}f(n)x^n\\ &=1+3x+\sum_{n=3}^{\infty}f(n-1)+2\sum_{n-3}f(n-2)x^n\\ &=1+3x+x\left(F(x)-x\right)+2x^2F(x), \end{align}$
from which
$\displaystyle\begin{align}F(x)&=\frac{x+2x^2}{1-x-2x^2}=\frac{x}{3}\left(\frac{4}{1-2x}-\frac{1}{1+x}\right)\\ &=\frac{x}{3}\left(4\sum_{n=0}^{\infty}(2x)^n-\sum_{n=0}^{\infty}(-x)^n\right)\\ &=\frac{x}{3}\sum_{n=0}^{\infty}\left(2^{n+2}-(-1)^n\right)x^n\\ &=\sum_{n=0}^{\infty}\frac{2^{n+2}-(-1)^{n+2}}{3}x^{n+1}\\ &=\sum_{n=1}^{\infty}\frac{2^{n+1}+(-1)^{n}}{3}x^{n}. \end{align}$
By definition, $f(n)=[x^n]F(x),$ the coefficient of the series by the term $x^n.$ Thus, as before,
$\displaystyle f(n)=\frac{2^{n+1}+(-1)^n}{3}.$
Acknowledgment
The problem is #184 from A Mathematical Orchard by M. I. Krusemeyer, G. T. Gilbert, L. C. Larson (MAA, 2012).
Generating Functions
- Generating Functions
- A Property of the Powers of 2
- An USAMTS problem with light switches
- Examples with series of figurate numbers
- Euler's derivation of the binary representation
- Examples with finite sums with binomial coefficients
- Fast Power Indices and Coin Change
- Number of elements of various dimensions in a tesseract
- Straight Tromino on a Chessboard
- Ways To Count
- Probability Generating Functions
- Finite Sums of Terms 2^(n-i) i^2
- Sylvester's Problem, a Second Look
- Generating Functions from Recurrences
- Binet's Formula via Generating Functions
- Number of Trials to First Success
- Another Binomial Identity with Proofs
- Matching Socks in Dark Room
|Contact| |Front page| |Contents| |Probability|
Copyright © 1996-2018 Alexander Bogomolny71999948