11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Nuclear Wang Jul 31 '18 at 18:54
  • $\begingroup$ @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. $\endgroup$ – saulspatz Jul 31 '18 at 19:00
  • $\begingroup$ I read the question before its deletion but can't now read it to find what $n$ is. Also can $k$ be $0$? $\endgroup$ – Weather Vane Jul 31 '18 at 19:00
  • $\begingroup$ @WeatherVane Thanks, I've edited the question. $\endgroup$ – saulspatz Jul 31 '18 at 19:07
  • $\begingroup$ Not following your answer. If $j=k$ you think the answer is $1$? $\endgroup$ – lulu Jul 31 '18 at 19:07
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Excellent! This is a good puzzle. Seemingly very confusing, but with a simple, utterly convincing answer. $\endgroup$ – saulspatz Jul 31 '18 at 19:32
  • 1
    $\begingroup$ I agree :) Of course, all I did was apply the logic of the solution of the original airplane puzzle. But it's really nice that the generalization is just as easy! $\endgroup$ – Alon Amit Jul 31 '18 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.