A generalization of the airplane seating puzzle

Question

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?

Answer 1

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 clearly answered by your formula.

Answer 2

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}.$$