Math Riddle: God and the 100 Reasoning Leaguers

[Pulsar]

Greetings, fellow Leagers. It's been a while since I've seen a math riddle on this board, so I decided to post one for the aficionadoes. Let those brains work!

It's April Fools Day in Heaven, the most feared day of the year by everyone floating there, for they know God's legendary sinister sense of humor; Jesus still screams when someone dares to mention his crucifixion, and Noah still has nightmares about piles of dinosaur poo on a shaky boat... God really is a bastard. The only one appreciating God's jokes is the Devil, God's old partner-in-crime (yes, they are good friends. Their so-called animosity was actually God's very first prank). So, satan pays his immortal pall a visit, eager to know what the Almighty has in stock this year.

-"So, what will it be this time? A Flood? Plagues? Asking a poor guy to sacrifice his son?", the Devil asks in delight.
-"All done that", God replies. "Nah, I've become interested in two groups of people, having some amusing quarrels down there. One group call themselves 'creationists' - very dense crowd. Really, I haven't seen such stupidity since I gave those stones to Moses! The other gang is very intriguing - 'The League of Reason' they're called. Smart guys, except for their disbelief in us of course!"
-"Hahaha", the Devil roars. "And what's your plan?"
-"I'm going to test them. You'll see."

Thus, God descends to earth and gathers the cream of both groups: 100 creationists and 100 Leaguers. The former immediately start crying, screaming, kneeling and praying - much to the Lord's irritation. The Leaguers stand back silently, rather surprised by His existence, but swiftly regaining their confidence and curiosity.

"Behold", God shouts, "I come here to test you." He turns to the creationists. "Behind me, you see a room. This room is filled with 100 closed coffins. Inside each coffin, I have written one of your names - thus, everyone has his own coffin. You will enter this room, each in turn. You have to find the coffin that has your own name inside. However, each of you can only look inside 50 coffins! Afterwards, you leave the room exactly as it was when you entered, and the next of you can enter. You are NOT allowed to communicate during or after the test! If ALL of you are able to find your own coffin, I will promise you eternal life at my side. BUT, if even a single one of you fails, I will bury all of you alive in your coffin, and you will be damned forever!!! You may confer before you begin. HAHAHAHA!!!"

The creationists tremble heavily, totally confused. Surely the Lord cannot be this cruel? "Have no fear, my fellow sheep", Kent Hovind, their self-appointed leader, reassures. "He is only testing our faith! Let us pray, and His Love will guide us. AMEN!"
So they begin. In turn, each of them enters the room, checking 50 coffins at random. Unsurprisingly, only half of them finds his own coffin. So God carries out His punishment, much to His delight.
Of course, the creationists should have known this. Since each of them had 50% chance of success, their combined chances were a mere (1/2)^100, virtually nil.

The Leaguers, laughing at the creationists' stupidity, cheer in unison. "So", God says, "you think you can do better?" And with a snap of his fingers, he creates a new room, with 100 coffins for the Leaguers. "Go ahead, unbelievers, use those brains I created for you! Impress me."

So the Leaguers debate for a while, after which they speak to God: "Well, we think we can boost our chances to more than 30%."
"We'll see", God said, surprised (He's not all that omniscient). And the Leaguers start the test. Sadly, the odds were still against them, and despite their nifty strategy, they don't succeed either. So God, though approving their ingenious plan, kills them all. I told you He was a bastard.

But, dear Leaguers, can you figure out what this strategy was? How did they improve their chances of success by more than 30%?

P.S. Sorry for the random story. I got carried away

 

[Ozymandyus]

"Behold", God shouts, "I come here to test you." He turns to the creationists. "Behind me, you see a room. This room is filled with 100 closed coffins. Inside each coffin, I have written one of your names - thus, everyone has his own coffin. You will enter this room, each in turn. You have to find the coffin that has your own name inside. However, each of you can only look inside 50 coffins! Afterwards, you leave the room exactly as it was when you entered, and the next of you can enter. You are NOT allowed to communicate during or after the test! If ALL of you are able to find your own coffin, I will promise you eternal life at my side. BUT, if even a single one of you fails, I will bury all of you alive in your coffin, and you will be damned forever!!! You may confer before you begin. HAHAHAHA!!!"

I would suggest we all change our names to Ozymandyus.

Or that instead of LOOKING in coffins we FEEL around for the writing.

Or just not take the test as he doesn't give a timeline for when we have to do this by.

Or we leave the ROOM as we found it, but alter the coffins in whatever way to mark ours or mark the ones for the next few people to go.

Thankfully god doesn't use very precise language. And I'm not about to take a 70% risk of being buried alive and damned for eternity.

 

[ebbixx]

So the Leaguers debate for a while, after which they speak to God: "Well, we think we can boost our chances to more than 30%."
"We'll see", God said, surprised (He's not all that omniscient). And the Leaguers start the test. Sadly, the odds were still against them, and despite their nifty strategy, they don't succeed either. So God, though approving their ingenious plan, kills them all. I told you He was a bastard.

But, dear Leaguers, can you figure out what this strategy was? How did they improve their chances of success by more than 30%?

P.S. Sorry for the random story. I got carried away

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

Increasing a 7.88860951..^-31 probability by 30% is still a roughly 1^-30 p value. (Not that a 70% chance of failure is a wager I would willingly take either).

I'm with Ozy... we all change to the same name and increase the odds to nearly certain success, unless someone gets smote. Which, judging from his book seems just like something he would do.

 

[Master_Ghost_Knight]

I don't think that is the solution, because then we could not only do that but also choose the first 50 coffins, and then the odds would be 50% altougheter (total), and not a 30% increase for each.

 

[ImprobableJoe]

Kick God in the nuts and make a run for it? If you can make it to an iron chariot, you're golden!

Seriously, I suck at these puzzles, but I look forward to the solution.

 

[ebbixx]

I don't think that is the solution, because then we could not only do that but also choose the first 50 coffins, and then the odds would be 50% altougheter (total), and not a 30% increase for each.

You don't think what, precisely, is the solution?

I see no one, so far, who has offered an actual guess at Pulsar's specific puzzle.

I know I got stuck on clarifying terms and cracking jokes.

You're making a hash of probability calculations here, though.

For one thing, you don't know the layout of the room; and you'll only be able to say anything about its layout after communication is prohibited.

It may or may not be possible to identify which 50 are the "first 50" considering this is God we're talking about. There's nothing in the set-up for instance, to prevent God from randomizing the room, either by juggling coffins between guessers, or simply by spinning the entire room around in some way.

It's an all or nothing game. Even the failure of one in 50 to find the coffin bearing her own name will result in total failure.

If one could simply leave the coffin bearing one's name open after finding it, that would increase the favorable odds immensely, though the formula's a little longer than I want to type out here. But the rules state, "leave the room as you found it." Unless you can argue that the coffins are not part of the room, opening or otherwise marking successful "hits" would violate the rules.

Then again, considering this is God we're dealing with I say screw the rules.

 

[ebbixx]

So they begin. In turn, each of them enters the room, checking 50 coffins at random. Unsurprisingly, only half of them finds his own coffin. So God carries out His punishment, much to His delight.
Of course, the creationists should have known this. Since each of them had 50% chance of success, their combined chances were a mere (1/2)^100, virtually nil.

I could be wrong (it's been a long time since I did probabilities) but isn't the probability of any individual finding their own marked coffin closer to p=0.68817?

After all, the probability of finding the desired one on the first try is 1/100, but for each successive try it improves slightly ... 1/99, 1/98, 1/97 ... 1/51? Summing those probabilties gave me the nearly 69% chance of discovery, assuming no memory wipe between tries. Granted, 0.6882^100 is still an incredibly tiny number (5.88^-17 for the masochists in the cheap seats) so I still wouldn't accept the wager except under coercion. But doing the math probably did calculate my mathematical odds at something better than a 30% increase from how they were stated in the question, though it didn't actually change those odds at all.

Does this mean I win?

Approx. form:

Now do I win?

Ooops, even though the Christians may not have done the math, their odds would be the same as mine, unless they chose to let God randomize the coffins between attempts. Somehow I'm guessing this isn't the answer you were looking for. After all, God believers can still manage to learn math, as evidenced by their ownership of casinos, hotels and other businesses where it can come in handy.

Or have I forgotten something here?

 

[aeroeng314]

Well, there's no time limit...

There is the obvious "trick" solution of just waiting until everyone dies as has been suggested.

There's also a trickier approach of using time to communicate to everyone else. 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. I feel that this assumptions are valid since the problem essentially states that there's some way to improve the odds and if either of these assumptions doesn't hold, then that can't possibly be the case (since a selection strategy requires the ability to identify coffins uniquely without opening them).*

The first thing would be to determine the order in which we enter the room. Each person knows who goes after them and, so, can also look for both their own coffin and their successors coffin. The first person to enter the room will then search the "first" 50 coffins. If he doesn't find his own, then we're fucked. If he does, he still looks in coffins for his successors name. Now we need a way to communicate to his successor whether or not his name was in the first 50 coffins. Since the sacrificial sheep went first, we know beforehand how much time it takes to examine 50 coffins. Let's say that if both names are found in the first 50, then the examiner will come back out as soon as he finishes examining the coffins. If he only finds his name, he goes and looks at the 50 coffins he just looked at (presumably that's legal, if not, he can simply go and pretend to look, it really doesn't matter; the point is to waste enough time that it becomes apparent to everyone outside that he didn't find his successors name). We don't worry about the case that he doesn't find his own name, because then we all get buried alive.

Each person to enter the room then does the same thing. If they find their successors name in the 50 coffins they look in (those coffins being either the first or second 50, depending on whether their predecessor found their name), they come out as quickly as possible. If they don't find their successors name, they waste time.

The odds with this strategy are 50%**, because it relies on the first person finding their own coffin. If the first finds their coffin, then this method allows everyone else to find theirs as well. Now, this is better than the 30% stated in the problem. But, then, the problem statement wasn't very specific and only stated that the odds were more than 30%. From what I know about math, 50 is bigger than 30 even for extremely large values of 30.

I could also be wrong since my solution depends on my interpretation of "no communication" and whether it's correct.

*Please scrutinize these assumptions.
**There's a 50% chance the first person's coffin is in the first half of all the coffins.

I'd double-check that sum. I'm pretty sure that a sum isn't involved. This one is definitely wrong because if you were allowed to look at 63 coffins, this formula says that the probability of finding your coffin would exceed 1, and that doesn't make sense. Statistics has never really been my strong point, so I'll work this out later

 

[Aught3]

You multiply the values rather than sum them, don't you?

Oh, and also you can't calculate it going the positive way, you have to go by chances of not finding it. You're right that the probability of finding it the first time is 1/100 but if you find it on the first go you don't keep looking. The chance of not finding it on the first go is 99/100 if this happens then you open another coffin, chance of not finding it 98/99. You keep going down like this until you have opened 50 coffins. The you multiply all these values together and you will get 1/2 or 50% chance of not finding your name, which means you have a 50% chance to find your name.

Edited 'cause I didn't get it right the first two times :roll:

 

[Ozymandyus]

I had a similar plan as aero, with trying to get around the communication problem by using time or some other signal, and helping the people that come after us. Wasn't sure if it would count as communication.

I'd like to add the possibility of only checking 1 box at a time(theres no stipulation that you cant go in multiple times - just that you can't look in more than 50 boxes), and all line up according to our numbers, and each go in and look in one box at a time. If we find our name in a coffin, we sit out instead of going to the end of the line. If we find the name of the guy behind us we can perhaps use the time technique, so he will know his box was the one we checked. We go through systematically: person 1 checks box 1, person 2 box 2, etc. then get back in line. If you find your coffin you remove yourself from the lineup - because clearly you don't need to check coffins anymore. Each time you go through you add 2 to the number of the box you are checking (basically you check every other box and your partner the inbetween ones, or vice versa). If you are not allowed to use the buddy system then you check every box except the ones that were already filled. Everyone knows which boxes are filled because we are all progressing systematically and stopping when we find ours, so everyone skips the already filled coffins when they get to that number.

If we are allowed to use time as a signal then this would yield a near 100% chance I think... not sure what the likelihood would be without that, but it would still be raised significantly. It does require an obvious number system for the coffins that we would all intuitively agree on - which would require some knowledge of whether the room was a square or a circle or what not. I have no idea on the probability of success on this system without signalling, I'm way too lazy to do the math. I think it may actually be the 0.688^100th amount that someone else suggested.

Edit: Meh, I explained this poorly. You would still want everyone checking boxes if the time as signal idea works, so you could just have three set amounts of time - come out quickly if your box isn't you or the next in line, come out in double the time if it Is the next in line, and come out in triple the time if its your coffin. Everyone keeps track of which coffins have been figured out and skips those coffins. That's the only way to get the 100% chance thing.

 

[ebbixx]

I'd double-check that sum. I'm pretty sure that a sum isn't involved. This one is definitely wrong because if you were allowed to look at 63 coffins, this formula says that the probability of finding your coffin would exceed 1, and that doesn't make sense. Statistics has never really been my strong point, so I'll work this out later

Thanks for catching that... I was pretty sure I was way rusty on this. Still, there is a relationship there that's different than a simple 50/50 chance, unless the condition is that one must pick one's 50 all at once. Someone who recalls probabilities better than I do will remind us, I hope.

I like your solution, but I'd tend to look at it as a form of communication, as you said. And if the coffins are arrayed in some way other than a grid, I'd also maintain that it might be hard to come up with a numbering scheme. But if we take a very long time, I suppose we might arrive at a scheme that anticipates all possible arrangements?

_____________

The statements made above (at least about the "different than 50/50" business) are complete claptrap, which I would have sorted out myself, had I been awake in writing them. I'm leaving them in place only as a relic of my own humiliation. Unless there's a mechanism in place, such as an agreed on system to allow the players to identify and eliminate correct hits, the individual's p of finding their own name remains 0.5. As others have kindly reminded me, though I did confirm it for myself as well, eventually. Thanks all.

 

[aeroeng314]

Time to settle the probability issue. Let's consider the probability that my coffin is not the first I look in. This probability is 99/100. Now, the probability that it's not the second coffin I look in given that it wasn't the first coffin is 98/100/(99/100) = 98/99. This pattern continues. The probability that it's not in the first 50 coffins I look in is 99/100 * 98/99 * 97/98 * ... * 50/51. What is the value of this product? It's exactly 1/2. The sequence can be seen as a "telescoping" sequence. The 99 in the first term cancels with the 99 in the second. All those middle terms cancel out leaving 50/100.

Nothing tricky here, intuition actually gets the probability right in this case (something intuition is notoriously bad at doing). Even taking the road of conditional probabilities (to avoid any Monty Hall issues that might arise) yields this answer. 50% is correct.

 

[ebbixx]

Oh, and also you can't calculate it going the positive way, you have to go by chances of not finding it. You're right that the probability of finding it the first time is 1/100 but if you find it on the first go you don't keep looking. The chance of not finding it on the first go is 99/100 if this happens then you open another coffin, chance of not finding it 98/99. You keep going down like this until you have opened 50 coffins. The you multiply all these values together and you will get 1/2 or 50% chance of not finding your name, which means you have a 50% chance to find your name.

Not meaning to be contrary, but is there a notation convention to express what you're saying? Because every way I've tried to calculate that is giving me values of 1 or greater, ratther than 0.5. Meaning an almost certainty of NOT finding it, which doesn't seem intuitively right. The probablity of finding it should at least be 0.5 or greater for each player.

(100!-50!)
________
(99!-49!)

doesn't seem to do it. And this pretty clearly is a no go:

Then again it's past my bedtime here so I may not be thinking straight.

Here's the link if you want to play around with it:

http://www64.wolframalpha.com/input/?i=(100-50)!/(99-49)!

Still, this ought to evaluate as:

100x99x98...x50 div 99x98x97 ... x49 which should be expressible somehow through factorials, shouldn't it? I think I need to dig out more math books.

 

[Aught3]

I think it would be:
(99!/49!)/(100!/50!)

You have to remember that factorials are multiplied not added, so you need to divide rather than subtract the second factorial.

http://www64.wolframalpha.com/input/?i=(99!/49!)/(100!/50!)

 

[Master_Ghost_Knight]

You don't think what, precisely, is the solution?

Changing the name is not a solution.

Neither the starting probability is difrent from 1/2 each because the probability of one getting right is:

(i.e. the probability of hiting the first, plust the probability of hitting the second knowing that missed the first, plus the probability of hitting the third knowing that all previouse have failed and so on)
Which by an amazing coincidence we can rearrange like this:

Which can be as easily transformed like this:

In a more simple answer 50 trys out of 100. 50/100=1/2

We are missing something else altogheter.

Edit: actualy the odds of finding the coffin for each is about 51% because he can open 50, but if he is not in those 50 he can guess in one of the remaining 50.

 

[ebbixx]

[
Changing the name is not a solution.

Sorry, I thought it was clear that changing everyone's name was a joke. Albeit, one that would seem to be a perfect "cheat."

 

[ebbixx]

I think it would be:
(99!/49!)/(100!/50!)

You have to remember that factorials are multiplied not added, so you need to divide rather than subtract the second factorial.

http://www64.wolframalpha.com/input/?i=(99!/49!)/(100!/50!)

Thanks. Damn I'm rusty.

Working it out more or less longhand (not all the way, but enough to suss out the pattern) I confirmed to myself that you are correct. Thanks for the refresher.

 

[ebbixx]

If we are allowed to use time as a signal then this would yield a near 100% chance I think... not sure what the likelihood would be without that, but it would still be raised significantly. It does require an obvious number system for the coffins that we would all intuitively agree on - which would require some knowledge of whether the room was a square or a circle or what not. I have no idea on the probability of success on this system without signalling, I'm way too lazy to do the math. I think it may actually be the 0.688^100th amount that someone else suggested.

I think you have the best approach so far, even if we eliminate all the tweaks that look like a direct form of communication... the timing codes, that is.

I understand wanting to avoid the math, still I'd like to see it. (From someone a bit less rusty that myself -- aeroeng314?)

0.688^100 is still an incredibly small chance, if that is the odds. Did Pulsar ever answer the question whether he meant the odds would increase by more than 30% or to more than 30%?

 

[scikidus]

However, each of you can only look inside 50 coffins!

It seems pretty clear to me that we should all stab our eyes out, rendering us blind, and making it impossible to look inside any coffins.

Also, if you can mark which coffin is yours, don't you have a probability of 50/100*50/99*50/98*...*50/50 = 50^51/(100!/49!) = 49! * 50^51 / 100! ~= 2.894485874950688008802120028875766981050308899782... x 10^-9?

 

[aeroeng314]

Which by an amazing coincidence we can rearrange like this:

It shouldn't be thought of as amazing or a coincidence. I've shown, using other methods, that the probability of finding your coffin is 1/2 (the odds that your coffin happens to be in a particular half of the total coffins is 1/2 and the probability of not finding your coffin using conditional probabilities). Using any method you want, you should always end up with 1/2, so it shouldn't come as a surprise that the resulting expression can be manipulated in some way such that a bunch of terms cancel out.

A possible coffin numbering system would be to number them by their distance from the door and resolve ties by the direction from the door. Of course, this assumes that everyone can measure distance and direction "accurately enough". It might be more reasonable to use direction as the primary classification and distance as the tie-breaker, actually.

Also, if you can mark which coffin is yours, don't you have a probability

It would vastly increase the odds, but as you pointed out, they would still be unbelievably small.