Mixing
A generalization of the airplane seating puzzle
Clash Royale CLAN TAG#URR8PPP
up vote
11
down vote
favorite
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 $kgeq1$ 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 $0leq 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 $ngeq2.$ Of course, when $n=2$ the puzzle is trivial, so I guess that the answer is $$
kchoose k-jkchoose jover2kchoose k, 0leq jleq k
$$
I don't have a clue how to prove this, though. Any ideas?
probability puzzle
asked Jul 31 at 18:49
saulspatz
10.3k21324
 |Â
show 6 more comments
up vote
11
down vote
favorite
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 $kgeq1$ 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 $0leq 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 $ngeq2.$ Of course, when $n=2$ the puzzle is trivial, so I guess that the answer is $$
kchoose k-jkchoose jover2kchoose k, 0leq jleq k
$$
I don't have a clue how to prove this, though. Any ideas?
probability puzzle
asked Jul 31 at 18:49
saulspatz
10.3k21324
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?
– Nuclear Wang
Jul 31 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.
– saulspatz
Jul 31 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$?
– Weather Vane
Jul 31 at 19:00
@WeatherVane Thanks, I've edited the question.
– saulspatz
Jul 31 at 19:07
Not following your answer. If $j=k$ you think the answer is $1$?
– lulu
Jul 31 at 19:07
 |Â
show 6 more comments
up vote
11
down vote
favorite
up vote
11
down vote
favorite
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 $kgeq1$ 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 $0leq 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 $ngeq2.$ Of course, when $n=2$ the puzzle is trivial, so I guess that the answer is $$
kchoose k-jkchoose jover2kchoose k, 0leq jleq k
$$
I don't have a clue how to prove this, though. Any ideas?
probability puzzle
asked Jul 31 at 18:49
saulspatz
10.3k21324
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 $kgeq1$ 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 $0leq 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 $ngeq2.$ Of course, when $n=2$ the puzzle is trivial, so I guess that the answer is $$
kchoose k-jkchoose jover2kchoose k, 0leq jleq k
$$
I don't have a clue how to prove this, though. Any ideas?
probability puzzle
asked Jul 31 at 18:49
saulspatz
10.3k21324
edited Jul 31 at 19:24
asked Jul 31 at 18:49
saulspatz
10.3k21324
asked Jul 31 at 18:49
saulspatz
10.3k21324
asked Jul 31 at 18:49
saulspatz
10.3k21324
10.3k21324
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?
– Nuclear Wang
Jul 31 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.
– saulspatz
Jul 31 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$?
– Weather Vane
Jul 31 at 19:00
@WeatherVane Thanks, I've edited the question.
– saulspatz
Jul 31 at 19:07
Not following your answer. If $j=k$ you think the answer is $1$?
– lulu
Jul 31 at 19:07
 |Â
show 6 more comments
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?
– Nuclear Wang
Jul 31 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.
– saulspatz
Jul 31 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$?
– Weather Vane
Jul 31 at 19:00
@WeatherVane Thanks, I've edited the question.
– saulspatz
Jul 31 at 19:07
Not following your answer. If $j=k$ you think the answer is $1$?
– lulu
Jul 31 at 19:07
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?
– Nuclear Wang
Jul 31 at 18:54
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?
– Nuclear Wang
Jul 31 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.
– saulspatz
Jul 31 at 19:00
@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.
– saulspatz
Jul 31 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$?
– Weather Vane
Jul 31 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$?
– Weather Vane
Jul 31 at 19:00
@WeatherVane Thanks, I've edited the question.
– saulspatz
Jul 31 at 19:07
@WeatherVane Thanks, I've edited the question.
– saulspatz
Jul 31 at 19:07
Not following your answer. If $j=k$ you think the answer is $1$?
– lulu
Jul 31 at 19:07
Not following your answer. If $j=k$ you think the answer is $1$?
– lulu
Jul 31 at 19:07
 |Â
show 6 more comments
1 Answer
1
active
oldest
votes
up vote
6
down vote
accepted
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.
answered Jul 31 at 19:29
Alon Amit
10.2k3765
1
Excellent! This is a good puzzle. Seemingly very confusing, but with a simple, utterly convincing answer.
– saulspatz
Jul 31 at 19:32
1
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!
– Alon Amit
Jul 31 at 19:34
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
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.
answered Jul 31 at 19:29
Alon Amit
10.2k3765
1
Excellent! This is a good puzzle. Seemingly very confusing, but with a simple, utterly convincing answer.
– saulspatz
Jul 31 at 19:32
1
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!
– Alon Amit
Jul 31 at 19:34
add a comment |Â
up vote
6
down vote
accepted
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.
answered Jul 31 at 19:29
Alon Amit
10.2k3765
1
Excellent! This is a good puzzle. Seemingly very confusing, but with a simple, utterly convincing answer.
– saulspatz
Jul 31 at 19:32
1
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!
– Alon Amit
Jul 31 at 19:34
add a comment |Â
up vote
6
down vote
accepted
up vote
6
down vote
accepted
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.
answered Jul 31 at 19:29
Alon Amit
10.2k3765
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.
answered Jul 31 at 19:29
Alon Amit
10.2k3765
answered Jul 31 at 19:29
Alon Amit
10.2k3765
answered Jul 31 at 19:29
Alon Amit
10.2k3765
answered Jul 31 at 19:29
Alon Amit
10.2k3765
10.2k3765
1
Excellent! This is a good puzzle. Seemingly very confusing, but with a simple, utterly convincing answer.
– saulspatz
Jul 31 at 19:32
1
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!
– Alon Amit
Jul 31 at 19:34
add a comment |Â
1
Excellent! This is a good puzzle. Seemingly very confusing, but with a simple, utterly convincing answer.
– saulspatz
Jul 31 at 19:32
1
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!
– Alon Amit
Jul 31 at 19:34
1
1
Excellent! This is a good puzzle. Seemingly very confusing, but with a simple, utterly convincing answer.
– saulspatz
Jul 31 at 19:32
Excellent! This is a good puzzle. Seemingly very confusing, but with a simple, utterly convincing answer.
– saulspatz
Jul 31 at 19:32
1
1
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!
– Alon Amit
Jul 31 at 19:34
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!
– Alon Amit
Jul 31 at 19:34
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2868358%2fa-generalization-of-the-airplane-seating-puzzle%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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?
– Nuclear Wang
Jul 31 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.
– saulspatz
Jul 31 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$?
– Weather Vane
Jul 31 at 19:00
@WeatherVane Thanks, I've edited the question.
– saulspatz
Jul 31 at 19:07
Not following your answer. If $j=k$ you think the answer is $1$?
– lulu
Jul 31 at 19:07