Math Riddle: God and the 100 Reasoning Leaguers

[Pulsar]

All right, good job sofar! Time for a few clarifications.</COLOR>

To more or by more... which is it?

Ah, sorry for that. I mean To more than 30%: a strategy so that the chance that everyone finds his own coffin, and the group passes the test, is more than 0.3, instead of (0.5)^100.
As for your formula: you added probabilities that were not independent; as pointed out by aeroeng314 and Master_Ghost_Knight, if an individual checks 50 coffins randomly, his chances of success are indeed 0.5.

I'd like to add the possibility of only checking 1 box at a time

That would help a lot , but no: everyone gets to enter the room only once, check at most 50 coffins, and leave.

I will assume that God will leave the room the same between examinations; He is a bastard, but scrambling the room between each examination would make any sort of strategy completely pointless and no improvement in your odds could possibly be made. I will also assume, for the same reason, that the coffins are ordered, so they can be referred to each by a unique ordinal.

<COLOR color="#FFFF80">
Correct. The coffins are ordered - that is, each one can decide beforehand which coffins he'll check. And the order of the coffins remains the same during the test. You're on the right track, but you're not there yet .

The question is, how can they check the coffins in a specific order, rather than randomly? And what order would that be?

I'll post the answer in due time. The full mathematical analysis is complicated, but I think you can find the correct strategy, even if you're not able to calculate why it works. Carry on!

 

[Aught3]

So, instead of checking randomly everyone agrees to check a different set of 50?

Maximum coverage, every coffin is checked twice?

Edit: thinking about it on the train this morning, I realised what I meant was every coffin will be checked 50 times.

 

[Master_Ghost_Knight]

That would eliminate repeated combinations

 

[Netheralian]

Just to add my 2 cents...

Maybe look at this from the other direction. I.e. the probability we are looking to achieve is 30%. The first guy has a 50% chance of getting it right - i don't see how we can possibly do better than that. But now to acheive better than 30% total, the second guy already must have a chance of better than 60%. I'm guessing its some sort of exponential decay asymptotic around 30%.

So if you can solve it with a strategy for the first two people then I think we are on our way... I don't see it...

 

[Master_Ghost_Knight]

I can think of a way by reshufleing the coffins, but you are not allowed to do that. Theorticaly it looks identical altough it isn't.

 

[Ozymandyus]

Ah, sorry for that. I mean To more than 30%: a strategy so that the chance that everyone finds his own coffin, and the group passes the test, is more than 0.3, instead of (0.5)^100.
As for your formula: you added probabilities that were not independent; as pointed out by aeroeng314 and Master_Ghost_Knight, if an individual checks 50 coffins randomly, his chances of success are indeed 0.5.

Correct. The coffins are ordered - that is, each one can decide beforehand which coffins he'll check. And the order of the coffins remains the same during the test. You're on the right track, but you're not there yet .

The question is, how can they check the coffins in a specific order, rather than randomly? And what order would that be?

I'll post the answer in due time. The full mathematical analysis is complicated, but I think you can find the correct strategy, even if you're not able to calculate why it works. Carry on!

Assuming manipulations of the communication rule by various signals is not allowed (such as coming out early if you find your coffin or timing one minute per coffin you check so as to signal the next person which coffin is yours or theirs), I'm at a loss.

I can think of a couple things that could barely increase my chances: I.E. knowing which set of boxes different people examined, I HAVE to assume that one of the coffins they examined was their coffin (because I'm screwed if anything else is true.) So If I am second and I know the first guy looked at the first 50, I can assume theres a higher probability of my box being in the second set of 50 because the first guy's box must be in the first 50 for it to matter at all. But the overall chances are only a tiny bit higher. Again, math isn't my strong suit, but I know that this isn't any kind of solution - I think it raises my chances to something like 1.30388924 × 10^-30 instead of 7.88860905 × 10^-31 ... wheee.

Even the the best plan can't increase your chances to 30% without ANY method of signalling that I can think of, so I guess I give up - I'd really love to see the solution. It better not use the Monty Hall problem... that wouldn't work here.

 

[Aught3]

Using the method I suggested earlier the last 50 people (who have the best odds) have a 62.8% chance of finding their name rather than a 50% chance that a random guesser would have. Even if all 100 people had these improved odds it is still only a 1 : 6.7x10^-21 chance everyone will find their name rather than 1 : 7.9x10^-31. Nowhere near 0.3.

Damn, I thought it was a good suggestion.

 

[Ozymandyus]

Using the method I suggested earlier the last 50 people (who have the best odds) have a 62.8% chance of finding their name rather than a 50% chance that a random guesser would have. Even if all 100 people had these improved odds it is still only a 1 : 6.7x10^-21 chance everyone will find their name rather than 1 : 7.9x10^-31. Nowhere near 0.3.

Damn, I thought it was a good suggestion.

Wait, what is this method? I somehow can't find the suggestion so I'm a bit confused.

 

[Aught3]

Correct. The coffins are ordered - that is, each one can decide beforehand which coffins he'll check. And the order of the coffins remains the same during the test. You're on the right track, but you're not there yet

So everyone knows for sure which coffin is which? Are they allowed to mark them before you start?

I have another idea if this is the case, but when I calculated the odds it wasn't 0.3. So my question is would the odds change based on the number of coffins? I used four coffins with two choices each, but I have no idea how to scale up my calculation.

 

[ebbixx]

I have another idea if this is the case, but when I calculated the odds it wasn't 0.3. So my question is would the odds change based on the number of coffins? I used four coffins with two choices each, but I have no idea how to scale up my calculation.

This is starting to sound like a game theory problem to me, but that's probably as far as I'm likely to get.

 

[Pulsar]

Time for some clues!

Tip: every time an individual opens a coffin, he sees the name of one of the Leaguers. Even if it's not his own name, the information is still very useful for him.

Let me also increase the restrictions: during the test, not a single form of communication is allowed between the Leaguers, no signaling, not even tricks by waiting for a specific time; an individual cannot know in any way whether the other Leaguers have succeeded or not. And the coffins may not be moved.</COLOR>

So everyone knows for sure which coffin
is which? Are they allowed to mark them before you start?

Yes, that's OK. The coffins can be numbered from 1 to 100 before the test begins, so everyone can clearly distinguish each coffin.

I have another idea if this is the case, but when I calculated the odds it
wasn't 0.3. So my question is would the odds change based on the number
of coffins? I used four coffins with two choices each, but I have no
idea how to scale up my calculation.

<COLOR color="#FFFF80">
That's an excellent idea. Try to solve the case with 4 people, 4 coffins, and everyone can check 2 coffins. This case is much easier to visualize. If you can find the best strategy with 4 people, you've basically solved the puzzle.
And yes, the odds change with the number of coffins: in the case of 4 coffins, the chances of success are more than 40%! Do post your idea, it might inspire others, and I can give more clues.

 

[aeroeng314]

an individual cannot know in any way whether the other Leaguers have succeeded or not.

So God waits until everyone has had a turn before burying everyone alive even if the first person failed?

 

[Pulsar]

</COLOR>

So God waits until everyone has had a turn before burying everyone alive even if the first person failed?

<COLOR color="#FFFF80">
Hmmm, good point. Well, as soon as one individual fails, it's pointless to continue, and God might as well stop the test.
So I'll refrase: an individual cannot know how well the others have done (e.g. how fast they found their coffin), so he can't draw conclusions from that.

 

[ebbixx]

Let me also increase the restrictions: during the test, not a single form of communication is allowed between the Leaguers, no signaling, not even tricks by waiting for a specific time; an individual cannot know in any way whether the other Leaguers have succeeded or not. And the coffins may not be moved.

Just to clarify (and avoid wasting time) -- the players cannot communicate during the test. Does during extend to before the first person enters the room, or are we allowed to confer and develop a plan before the first person enters?

And since it seems the game will end when the first person fails, can we assume then that a person leaving the room is a sign that they in fact found their own coffin?

In which case, in the 4-person game it would seem that player 2 has a better chance of finding his name in the coffins player 1 did not inspect, since at least one of those two coffins would certainly NOT contain his name?

So, splitting the coffins into 2 sets (either odds or evens, or first 50/last 50) would seem to be more productive than purely random choice?

 

[Pulsar]

</COLOR>

Just to clarify (and avoid wasting time) -- the players cannot communicate during the test. Does during extend to before the first person enters the room, or are we allowed to confer and develop a plan before the first person enters?

<COLOR color="#FFFF80">
The Leaguers are allowed to confer and develop a plan before the first person enters. In fact, it's essential. But as soon as the first person enters, all communication is forbidden.

 

[ebbixx]

The Leaguers are allowed to confer and develop a plan before the first person enters. In fact, it's essential. But as soon as the first person enters, all communication is forbidden.

Thanks... please take a look at my expansion of the previous post, then.

My remaining concern is, is there something besides splitting the coffins into two sets that can be done, since in the 4-person game, player 3 is faced with equal odds of failure no matter which half she chooses, yet if she could deduce which 2 coffins players 1 & 2 had failed to find their names in, she could be certain to locate her name.

I'm not as confident on this one, but it seems player 3 should probably choose a "mixed" set, that is, one from the set chosen my player 1 and one from player 2's set?

 

[Pulsar]

</COLOR>

And since it seems the game will end when the first person fails, can we assume then that a person leaving the room is a sign that they in fact found their own coffin?

Sure, but it doesn't matter that much. By choosing the best strategy, they already know their odds of success before the first one enters the room.

In which case, in the 4-person game it would seem that player 2 has a better chance of finding his name in the coffins player 1 did not inspect, since at least one of those two coffins would certainly NOT contain his name?

So, splitting the coffins into 2 sets (either odds or evens, or first 50/last 50) would seem to be more productive than purely random choice?

<COLOR color="#FFFF80">
Aha, yes, now we're getting somewhere. That's a good starting point, but they can do even better. I'll give you the exact chances of success for the best strategy: 5/12.

 

[Master_Ghost_Knight]

Aha, yes, now we're getting somewhere. That's a good starting point, but they can do even better. I'll give you the exact chances of success for the best strategy: 5/12.

If that is the case, then it is based on flaud thinking since you have no garantee that any of them finds his own.
unless of course you eliminate any repeating combination that renders everyone automaticaly loss. (i.e. eliminate every combination that renders at least 1 coffin unchosen, or a set of picked coffins that doesn't match the number of potential candidates)

 

[ebbixx]

Aha, yes, now we're getting somewhere. That's a good starting point, but they can do even better. I'll give you the exact chances of success for the best strategy: 5/12.

For some reason my previous reply failed to post.

Wanted to clarify: is 5/12 the odds for the 4-person game, the 100-person game or both? From context I'm assuming you meant the 4 person-game, since there are 6 possible sets of 2 choices available to each player. That is:

[1,2] [3,4] [1,3] [2,4] [1,4] and [2,3]

One can grid those choices and calculate individual odds for each set, at least for turns 1 and 2. It should be possible for the remaining steps as well.

Assuming the game is halted when someone fails to find their name, If Player 1 chose the set [1,2] then the odds for Player 3 are 2/3 for [3,4] but 1/3 for [1,2], unless I'm confusing myself again. I'm still puzzling over how to calculate prob. values for the other mixed sets though.

Waiting for someone to shoot this down.

 

[Master_Ghost_Knight]

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.