[Guest]

At a lecture for the math courses in the university, they gave this as an example of math problems they deal with:

You have 100 People waiting outside a room, each assigned a number from 1-100, inside the room there are cards turned on their backs, each person comes in at his turn and flips exactly 50 cards and sees if he/she finds their number, then they'd flip it back, exit the room and the next person comes in...

They do not communicate at all! not even in hints or anything.

Each person only comes in and checks exactly 50 cards then puts everything back in it's place exactly as it was.

What is the probability that every person would find his/her number under the cards? (0.5)^100 right? That's a really small number with lots of zeros, what method can the people agree on so that the chances of all of them finding their cards would be much higher?

Remember they do not communicate at all after the test begins, and they can't change the cards and they can't give out any hints to anyone whatsoever (like leaving a card askew or stuff like that)

[Guest]

My wild gues

They agree to flip cards in a way that every other person flipps every even position of cards or odd position of cards.............

[Guest]

They agree that the first person flip the first 50 cards. If he sees the card of the next person, he holds the door to the room open for that person. Keep following this procedure throughout and 99 should get it correct, if the first persons card is in the first 50, 100 will get it correct

[Guest]

The first guess wouldn’t improve the odds at all, each person would still have a 50% chance of finding his card. The second guess would improve the chances but wouldn’t that be construed as a “clue” to the next person’s card location? How about instead, if and when the first person (and all who follow) finds his card, he pockets it (or leaves it flipped up.) This would not be a clue to the next person’s card location, but would exponentially improve the chances of every person who follows.

[EventHorizon]

Obviously, if everyone chooses the first 50 cards then there is no chance that all 100 people will see their number.

So my answer would be to have everyone choose a different range. Perhaps from their number to their number +49 (with wrap around).

I'm not sure if that helps the odds much over random, but it makes sure it is not impossible.

Have the first 50 people choose the first 50 cards. If they all happen to see their cards, the second 50 will definitely see theirs in the second 50 cards.

Assuming the cards are randomly distributed, the odds of such a partition occurring is (50!*50!)/100!.

This is approximately 9.25e128/9.33e157 ~= 1e-29.

randomly guessing would be .5^100 ~= 7.89e-31

That means I've improved the odds by 12.7 times. Not bad for a first attempt...

I'm thinking the top one is better, but I'm not gunna try to calculate the probabilities...

Edited April 16, 2010 by EventHorizon

[bushindo]

Obviously, if everyone chooses the first 50 cards then there is no chance that all 100 people will see their number.

So my answer would be to have everyone choose a different range. Perhaps from their number to their number +49 (with wrap around).

I'm not sure if that helps the odds much over random, but it makes sure it is not impossible.

Have the first 50 people choose the first 50 cards. If they all happen to see their cards, the second 50 will definitely see theirs in the second 50 cards.

Assuming the cards are randomly distributed, the odds of such a partition occurring is (50!*50!)/100!.

This is approximately 9.25e128/9.33e157 ~= 1e-29.

randomly guessing would be .5^100 ~= 7.89e-31

That means I've improved the odds by 12.7 times. Not bad for a first attempt...

I'm thinking the top one is better, but I'm not gunna try to calculate the probabilities...

If the board has taught me anything, it's that random permutation study is immensely interesting

Algorithm goes as follows. For prisoner N,

1) Let prisoner N goes in, and flip the N-card, let's call the card's number M

2) If M = N (the card has his number), he's done with his task.

3) If M != N, go to the M-th card, and flip it.

4) Repeat 2) and 3) until all 50 cards have been flipped or until the prisoner's card is found.

This works because the mapping between the prisoner's numbers and the card's numbers can be considered a random permutation. If all subcycles of this permutation has length < 50, then the algorithm above is guaranteed to let everyone find his card. The chance that all the subcycles of a random permutation have length < 50 is .31.

[Guest]

If the board has taught me anything, it's that random permutation study is immensely interesting

Algorithm goes as follows. For prisoner N,

1) Let prisoner N goes in, and flip the N-card, let's call the card's number M

2) If M = N (the card has his number), he's done with his task.

3) If M != N, go to the M-th card, and flip it.

4) Repeat 2) and 3) until all 50 cards have been flipped or until the prisoner's card is found.

This works because the mapping between the prisoner's numbers and the card's numbers can be considered a random permutation. If all subcycles of this permutation has length < 50, then the algorithm above is guaranteed to let everyone find his card. The chance that all the subcycles of a random permutation have length < 50 is .31.

That answer is correct, for those who did not understand the explanation, try to figure it out cause that part is harder than finding the answer itself...

[Guest]

i understand the explanation, but I'm curious as to how he got the probability.

[superprismatic]

i understand the explanation, but I'm curious as to how he got the probability.

There's an explanation under "100 Prisoners" at http://en.wikipedia.org/wiki/Random_permutation_statistics

but it is pretty terse.