# A generalization of the airplane seating puzzle

Let me say immediately that this isn't my puzzle. Someone posted it earlier, and I was working on it when it was deleted. It seems to me to be an excellent puzzle, too good be deleted, so I'm reposting it. If there's a good reason why I should delete this puzzle, please tell me.

In some world, everyone has $k\geq1$ feet. Everyone wears $k$ identical socks, but the socks vary from person. Each person can easily identify his own socks. When the people go to worship, they remove their socks and place them in a communal pile. At the close of the service, each person removes his socks from the pile.

One day, the first person to leave is in a hurry, and grabs $k$ socks uniformly at random. After that, each person removes all of his own socks from the pile, and if any are missing, he randomly picks just enough so that he will have one for each foot.

What is the probability that the last person to leave will find exactly $j$ of his own socks in the pile, for $0\leq j \leq k?$ (When $k=1,$ this is the airline seating puzzle.)

I've done some experimenting by computer simulation for small $n$ and $k,$ and the results lead me to believe that for given $k,$ the answer is independent of the number of people $n\geq2.$ Of course, when $n=2$ the puzzle is trivial, so I guess that the answer is $${{k\choose k-j}{k\choose j}\over{2k\choose k}}, 0\leq j\leq k$$ I don't have a clue how to prove this, though. Any ideas?

• Each person puts k socks in the pile. Each person removes k socks from the pile. The last person always removes k socks from the pile, so j = k with probability 1. Are you asking what's the probability that the last person finds j of his own socks in the pile? Jul 31, 2018 at 18:54
• @NuclearWang Sorry, I misunderstood you. I did mean $j$ of his own socks. I think I have the proof, but I want to consider it again. Jul 31, 2018 at 19:00
• I read the question before its deletion but can't now read it to find what $n$ is. Also can $k$ be $0$? Jul 31, 2018 at 19:00
• @WeatherVane Thanks, I've edited the question. Jul 31, 2018 at 19:07
• Not following your answer. If $j=k$ you think the answer is $1$?
– lulu
Jul 31, 2018 at 19:07

When the last person looks at the pile, which socks could possibly be there? Their own socks, and the socks of the first person. That's it. Any sock belonging to any other person will have been removed from the pile when that person picked up their socks.

Therefore, the question is simply this: from a set of $k$ black and $k$ white socks, $k$ socks are picked uniformly at random (we know that $k$ socks eventually remain, and everyone is indifferent to picking black or white socks). What is the probability that $j$ white socks remain?

This is a good generalization. It should be stipulated though that the socks are all distinguishable. Here is a more general question. For the $$i$$'th person, what is the probability he will collect exactly $$j$$ of his own socks?
At the turn of the $$i$$'th person comes to pick his socks, the pile is $$k$$ socks short of all the $$k(n-i+2)$$ socks of $$n-i+2$$ people consisting exactly of himself, his successors and the first person. The $$k$$ socks are taken by all his predecessors. All combinations of the $$k$$ socks are equally likely. So the total number of the combinations is $$k(n-i+2)\choose k$$.
Amongst these, we consider the combinations where $$k-j$$ socks of $$i$$'th person are taken, leaving $$j$$ socks of $$i$$'th person for himself to retrieve. There are $$k\choose k-j$$ ways to pick $$k-j$$ socks amongst $$k$$. For each of this set of $$k-j$$ socks, the remaining $$j$$ socks taken by all the predecessors are selected from all the $$k(n-i+1)$$ socks of all the successors and the first person, making the number of combinations equal to $$k(n-i+1)\choose j$$. So the total number of configurations of the $$k$$ socks taken by the predecessors is $${k\choose k-j}{k(n-i+1)\choose j}$$.
All the combinations considered above are equally likely. We conclude that the desired probability is $$\frac {{k\choose k-j}{k(n-i+1)\choose j}}{k(n-i+2)\choose k}.$$