Math Riddle: God and the 100 Reasoning Leaguers

[ebbixx]

Don't fool yourself whit the halted of the game. Because at begining you have and amazingly small chance, but if he gets to the last one, the last one has only 50%chance of wining (so it would be wrong to assume that the odds are 50%), fantom odds count.

I'm not sure I'm following you. If Player 1 fails the game is over and all subsequent choices are meaningless. The strategy I'm looking for would be one that eliminates strategies that have no possibility of success... for instance, if all players choose to search the set [1,2], there's a 100% chance that 2 will find their names, but also 100% that 2 will fail, and the posibility of failure in the game itself is 100%.

You see a flaw in this?

 

[aeroeng314]

Well right away we know that a losing strategy is for everyone to look at the same set of coffins. If everyone looked in the same coffins, someone would be guaranteed to fail even though the odds of any one person's coffin being in the examined half is 50%.

Just an example of how strategy influences the odds. It also demonstrates that a strategy must also completely cover every coffin, but we already knew that.

What makes things trickier is that the best strategy may have people change which coffins they examine while they're still in the room. Sort of like a weird variation of the Monty Hall problem.

After reading the problem again, it was never actually stated that the players had to look in their own coffin, only that they had to figure out which one was theirs. However, the further clarifications make me think the opposite (that if you don't look in your coffin during your turn, you fail).

So, there are 100891344545564193334812497256 different sets of 50 coffins to look in. We have to pick the 100 of those that gives the highest probability of each person finding their own coffin. Maximization problem...huge solution space...sounds like a job for a GA. Or, alternatively, time spent actually thinking about it instead of goofing around.

 

[Master_Ghost_Knight]

I'm not sure I'm following you. If Player 1 fails the game is over and all subsequent choices are meaningless. The strategy I'm looking for would be one that eliminates strategies that have no possibility of success... for instance, if all players choose to search the set [1,2], there's a 100% chance that 2 will find their names, but also 100% that 2 will fail, and the posibility of failure in the game itself is 100%.

You see a flaw in this?

I taught some one sugest something else a bit difrent (i.e. to assume that if he got his turn then it is because some one else found his own and then calculate the odds of that)

 

[porkytree]

My thoughts on this problem.

Can the person coming out of the room pick the next person to enter?

If so, then the arrangement is that the 1st, 3rd, 5th ..... entrants would check the odd numbered coffins. The 2nd, 4th, 6th etc entrants would check the even numbered coffins.

When a person exits the room they pick a person whose name that they have NOT seen to enter next. The next person would then be sure to find their name in one of the coffins.

 

[ebbixx]

My thoughts on this problem.

Can the person coming out of the room pick the next person to enter?

Sounds like communication to me. Plus, if they could, then you could boost the overall chance of success to 1/2, rather than 5/12.

If Player 1 finds his name in the pre-agreed set (p=0.5) all he needs to do is pick as Player 2 the owner of the other coffin with the understanding that Player 2 will check the same set OR he tags either of those whose names he didn't see with the understanding that they pick the set he didn't check. The first option seems closer to failsafe though, at least in the 4-player version, since after Player 2, Players 3 and 4 would also know that their names had to be in the set not checked yet.

In any case, to prevent all communication you'd pretty much have to send players to a third room after they'd checked their 50 coffins, even if the game terminated the moment someone failed

I'm still stuck on Turn 3, btw, but I'm not giving this puzzle all that much attention.

 

[Salv]

I'm not sure on the math on this or anything.
If the first person enters and finds their own coffin, couldn't they just close the lid so the next person coming in still has their 50 checks but only a choice of 99 coffins?

 

[Pulsar]

</COLOR>

If the first person enters and finds their own coffin, couldn't they just close the lid so the next person coming in still has their 50 checks but only a choice of 99 coffins?

No, the persons must leave the room unchanged. All coffins are closed btw, it would be easy if they weren't.

Can the person coming out of the room pick the next person to enter?

No, that's a form of communication.

Wanted to clarify: is 5/12 the odds for the 4-person game, the 100-person game
or both?

5/12 is the odds for the 4-person game only. The odds for the 100-person game are a bit less, just over 0.3.

Well right away we know that a losing strategy is for everyone to look
at the same set of coffins. If everyone looked in the same coffins,
someone would be guaranteed to fail even though the odds of any one
person's coffin being in the examined half is 50%.
Just an example of how strategy influences the odds. It also demonstrates that a strategy must also completely cover every coffin, but we already knew that.

Correct.

After reading the problem again, it was never actually stated that the players had to look in their own coffin.

They do have to look in their own coffin.

What makes things trickier is that the best strategy may have people change which coffins they examine while they're still in the room. Sort of like a weird variation of the Monty Hall problem.

<i></i>
<COLOR color="#40FF40">You're getting close!

Don't worry, the solution doesn't involve writing a computer algorithm, just a deep insight into the mathematics. It's all about combinatorics.

First off all, look at the simplest possible variant: only 2 people, 2 coffins, and each one can check just 1 coffin. In this case, the best strategy is straightforward. With that in mind, you can try the problem with 4 people. Write down all possible scenarios. From that, you can try to figure out which coffins each individual should check, to get the maximum success rate of 5/12.

 

[aeroeng314]

Don't worry, the solution doesn't involve writing a computer algorithm

Well of course not. But I could and it would be cool for its own sake.

First off all, look at the simplest possible variant: only 2 people, 2 coffins, and each one can check just 1 coffin.

And the odds of success are simple too: 1/2.

I guess I should really sit down and analyze the odds so I can compute the chance of success for any selection strategy. Well, I am bored and it is something to do.

Let's say that as you were going into the room, you were going to check the first and second coffins. Let's say that, upon opening the first coffin, you see a name that isn't yours. The probability that the second coffin contains your name is the probability that the coffin that contains your name is one of the first two given that it isn't the first. So, something like P(A1 U A2 | ~A1) = P( (A1 U A2) ^ ~A1 ) / P(~A1)

P( (A1 U A2) ^ ~A1) = P(A2) - P(A2 ^ A1)

Since A2 and A1 are mutually exclusive (your name can't be on two different non-quantum coffins) P(A1 ^ A2) = 0. So we end up with P(A1 U A2 | ~A1) = P(A2)/(1 - P(A1)) = 1/4/(3/4) = 1/3. So no Monty Hall effects here. Even after opening the first coffin, the remaining ones have equal probability of being your coffin (unless I've made a mistake), so I'm having difficulty imagining how your choices would (or should) change, but this may only be relevant for the case with 4 people.

 

[Ozymandyus]

Well, this is a case I already presented where you must assume that the first person found his coffin in the set he checked and therefore should check only coffins that have been checked the least. But it doesn't do much to raise your chances... in the case of two coffins and one check it raises your chances to 50% from 25%, but in the case of 4 coffins with 2 looks you only get .5(1st person)x .66(second person) x .5(third person) x 1(fourth person). = 16.5%... much better than 6.25% of randomly guessing but still not very good.

It continues to get worse as you increase the number of coffins, and at the point of 100 coffins you are only raising your chances by an infinitesimal amount.

No Monty Hall effects are possible as that requires someone who has knowledge of what names are in the coffins doing the revealing - you picking a set of coffins opening a few and changing your mind does not affect the odds at all.

 

[Aught3]

1 2 3 4 <--- Coffin number
1 2 3 4 <--- People's names
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

Don't know if this will help anybody but I generated a list of all possible combinations of four names inside four coffins. Since we know which coffin is which I called them 1,2,3, & 4 and I also called the people 1,2,3, & 4. If each person picks the coffin that corresponds to their name first then the next coffin down there is a 8.33% chance everyone will find their names rather than the 6.25% chance by random guessing.

 

[Nelson]

I've played around a bit with the 4 coffin problem and I believe I can increase the chances to 5/24 ~20.8% (unfortunately not the 5/12 discussed) . I will call the players 1, 2, 3, 4 and the coffins A, B, C, D in an attempt to avoid confusion. Here is the choice scheme that the players agree on ahead of time:

Player 1 picks coffins A and B.

Player 2 picks coffin A. If A is player 1, then player 2 picks coffin B.
If A is not player 1 then player 2 picks coffin C.

Player 3 picks coffins C and D.

Player 4 picks coffin D. If D is player 3, then player 4 picks coffin C.
If D is not player 3, then player 4 picks coffin B.

This plan will lead to the players finding their coffins for 5 of the 24 possible setups listed above:

1 2 3 4
1 2 4 3
1 4 2 3
2 1 3 4
2 1 4 3

So for players 1 and 3 it is complete chance if they find their own coffin. When player 2 comes in, if he sees that coffin A is not player 1, then he must assume that coffin B IS player 1 and play accordingly. If this is not the case then the game is already lost. Each player should not consider where he has the highest chance to find his coffin, but where he has the highest chance to find his coffin assuming everyone before him as been successful. This same reasoning holds for player 4's choices. I haven't had a lot of time to tweak this. I'm only hoping it will trigger some productive thought and discussion.

 

[aeroeng314]

This plan will lead to the players finding their coffins for 5 of the 24 possible setups listed above:

1 2 3 4
1 2 4 3
1 4 2 3
2 1 3 4
2 1 4 3

That one line doesn't make sense. Player 2 looks in A and sees 1 and then looks in B and sees 4. Neither of those are two. That case is a failure.

 

[Ozymandyus]

Misreading errors... ignore.

 

[Nelson]

Seems I jumped the gun and made a mistake, there are only 4 working combinations with that method.

1 2 3 4
1 2 4 3
2 1 3 4
2 1 4 3

The one that aero pointed out does not work. I'll try tweaking the strategy a bit.

 

[aeroeng314]

1 2 3 4
1 2 4 3
1 4 2 3
2 1 3 4
2 1 4 3

The way I'm reading it, the first two lines don't work either. If person 2 looked in coffin 1and person 1's name was in it they would skip to coffin 3.

The third line I presume was meant to be 1 3 4 2 which works. Still, only leaves you with 3 working combinations...

My method of alternating first two last two allows for 4 possible combinations as I mentioned... 16.6%
1324
2314
1423
2413

Wait, what?

Player 2 picks coffin A. If A is player 1, then player 2 picks coffin B.

If Player 2 sees 1 in coffin A, then he looks in coffin B, he doesn't go to C. He only goes to C if he doesn't find #1 in A.

Also, 1342 doesn't work, because no part of the strategy has player 2 looking in coffin D or player 3 looking in coffin B.

 

[Nelson]

New strategy with 6/24 success (assuming I did not make another error)

Player 1 picks coffins A and B.

Player 2 picks coffin B.
If B is player 1, then player 2 picks coffin A.
If B is player 3, then player 2 picks coffin C.
If B is player 4, then player 2 picks coffin D.

Player 3 picks coffin C.
If C is player 2, then player 3 picks coffin B.
If C is player 4, then player 3 picks coffin D.

Player 4 picks coffin D.
If D is player 3, then player 4 picks coffin C.
If D is player 2, then player 4 picks coffin B.

Now I THINK this should work for:
1 2 3 4
1 2 4 3
1 3 2 4
1 4 3 2
2 1 3 4
2 1 4 3

25% success. Feel free to correct me if I made a mistake.

 

[Ozymandyus]

Wait, what?


If Player 2 sees 1 in coffin A, then he looks in coffin B, he doesn't go to C. He only goes to C if he doesn't find #1 in A.

Also, 1342 doesn't work, because no part of the strategy has player 2 looking in coffin D or player 3 looking in coffin B.

Ah yeah I had misremembered how he wrote it, I had been thinking he wrote it the other way around.
Then he's right, his way actually does get another one...
1 2 3 4
1 2 4 3
2 1 3 4
2 1 4 3
Player 4's strategy should be:
Player 4 picks coffin D. If D is player 3, then player 4 picks coffin C.
If D is not player 3, then player 4 picks coffin A.
AND then you can add:
2 3 4 1

Ah, there you go now you are onto something with that last post.

 

[Ozymandyus]

You made a couple mistakes with always saying player 2 picks.... no matter what player you were talking about... but I assume that was some copy paste error.
Looks right other than that... Now just need to add 4 more combinations and you're there! Pretty sure you just need to add contingencies to player 1 and you have it.

 

[Nelson]

Indeed I did. It has been corrected in the original post. Thanks.

 

[Ozymandyus]

New strategy with 6/24 success (assuming I did not make another error)

Player 1 picks coffins A and B.

Player 2 picks coffin B.
If B is player 1, then player 2 picks coffin A.
If B is player 3, then player 2 picks coffin C.
If B is player 4, then player 2 picks coffin D.

Player 3 picks coffin C.
If C is player 2, then player 3 picks coffin B.
If C is player 4, then player 3 picks coffin D.

Player 4 picks coffin D.
If D is player 3, then player 4 picks coffin C.
If D is player 2, then player 4 picks coffin B.

Now I THINK this should work for:
1 2 3 4
1 2 4 3
1 3 2 4
1 4 3 2
2 1 3 4
2 1 4 3

25% success. Feel free to correct me if I made a mistake.

Okay, you got it, I'm guessing we just add the contingencies for player 1 and it should add a few more possible win scenarios...
Player one looks in coffin A
If A is player 2, then player 1 picks coffin B.
If A is player 3, then player 1 picks coffin C.
If A is player 4, then player 1 picks coffin D.

Player 2 picks coffin B.
If B is player 1, then player 2 picks coffin A.
If B is player 3, then player 2 picks coffin C.
If B is player 4, then player 2 picks coffin D.

Player 3 picks coffin C.
If C is player 1, then player 3 picks coffin A
If C is player 2, then player 3 picks coffin B.
If C is player 4, then player 3 picks coffin D.

Player 4 picks coffin D.
If D is player 1, then player 4 picks coffin A.
If D is player 3, then player 4 picks coffin C.
If D is player 2, then player 4 picks coffin B.

This yields success on:
1234
1243
1324
1432
2134
2143
3412
3214
4231
4321

I think.

To extrapolate it out to a large group, you just need more and more rules so every time one of the later people opens a coffin they get more and more information about what is in the other coffins.

Yeah, it works after all. Crazy math and all its crazy workings. I'd still just rather cheat.