1

You have n pairs of socks, ie 2n socks, with shades of gray numbered from 1-white to n-black. You blindly remove the socks from the drawer and pair them at random. What the probability such that every paired different at most at one color?

Note: The colors between 1 and n, so the pair (1,2) is legal and the pair (1,3) isn't legal because the difference in the colors is 2 and not 1 or 0.

The answer: $\frac{(2^{n+1}+(-1)^n)2^nn!}{3(2n)!}$

I could not figure out how to solve the question and get to the closed expression in the answers. I would be happy if you keep the answer simple as much as possible. Thanks.

Yakir
  • 95
  • Do you mean "differ by one graylevel step"? – David G. Stork Mar 17 '21 at 17:41
  • yes - that what I mean – Yakir Mar 17 '21 at 17:53
  • @Yakir, Just in case you do not know, "Thanks" in the question does NOT count. The way to express thanks on StackExchange sites is upvoting the comments or the answers or accepting answer! Thanks in word without upvote or acceptance is more like the antithesis of thanks. (This comment will be deleted upon feedback.) – Apass.Jack Oct 09 '21 at 01:36

1 Answers1

4

Let $F(n)$ be the number of pairings where each pair differs by $1$ or $0$. One of the socks with color $n$ must be paired with either $(i)$ the other sock of color $n$ or $(ii)$ one of the two socks of color $n-1$. In case $(i)$ the remaining socks are all of colors $n-1$ and lower and may thus be paired in $F(n-1)$ ways. In case $(ii)$ since 1 sock of color $n$ is paired with $1$ sock of color $n-1$ the other sock of color $n$ must be paired with the other sock of color $n-1$. There are two ways that this can happen, but after that the remaining $2(n-2)$ may be paired in $F(n-2)$ ways. This shows that $$F(n)=1\cdot F(n-1)+2\cdot F(n-2)$$ You can see easily that $F(1)=1$ and $F(2)=3$. Induction may then by used to show that $F(n)=\frac{2^{n+1}+(-1)^{n}}{3}$ from which the result follows because the total number of pairings is $\frac{(2n)!}{2^nn!}$.

user293794
  • 3,668