THE ULTIMATE RIDDLE PART TWO.

sweet wrote:

deeprunxc wrote:

You make sure everyone changes the light once. If the prisoner goes into the room and the light is off, and he has never turned it on, then he turns it on. If the light is off, and he has turned it on once already, he leaves it alone. You designate one person the "On" person. This is the only person who can turn the light on. Every time he walks into the room and the light is on he will turn it off. Once he turns it off 99 times than every has been in the room.

Why hasn't anyone acknowledged that this solution works?

That certainly works, but is it optimal? I can't think of anything better, it's definitely better than waiting a really long time.

It is entirely possible that every prisoner will visit the room, making it posible for someone to make that assertion with 100% certainty. I won't deny that fact. What the problem requires you to explain is how 100 prisoners will know whether or not each has been in the room with 100% certainty. Remember, they are in solitary confinement with no means of communication.

Yes, but HOW WILL THEY KNOW? That is the crux of the problem.

How on God's Earth did you even come up with this analogy. This isn't even close to my argument. Random selection means that YOU might (or might not) win the lottery, but the question isn't about just YOU, it's about the status of 99 other people, none of which you can communicate with.

i don't know if there's a way to prove that you have the most-efficient algorithm. however, we can place a limit on how good that algorithm is.

clearly, the minimum time for all the prisoners to be freed is 100 days. however, this could only occur by a very lucky (1/10^42) guess.

you can count how much information a person has by the maximum number of independent yes/no questions he can answer. "independent" simply means that knowing the answers to some of the questions still does not give you the answer to other questions.

in order for a given prisoner to know for certain that he should declare that everyone has entered the room, he needs to know the state of 99 other people

this leads to 99 independent yes/no questions:

has prisoner 1 entered the room yet?

has prisoner 2 entered the room yet?

has prisoner 3 entered the room yet?

...

when a prisoner enters the room for the second time, he now knows that the message he gets from the bulb is one of four possibilities

first visit on, second visit on

first visit on, second visit off

first visit off, second visit on

first visit off, second visit off

This means that the most independent yes/no questions he could answer with this information is 4

on his third time in the room, he now knows the state is one of eight possibilities (each of the four from last time can have "third visit on" or "third visit off" appended to it)

the fourth visit gives 16 possibilities, the fifth 32, sixth 64, and seventh 128

so after seven visits to the room, the maximum amount of information a prisoner could get is enough to answer 128 yes/no questions

this means that no matter how clever the prisoners are, they can never get someone to know with certainty that everyone else has entered the room until that prisoner has entered the room 7 times.

this sets the new bare minimum for escaping the prison with certainty to 106 days.

if the prisoners name a certain guy to be the guy who will set them free, and if they were to invent an algorithm that would get him the information he needs, then the probability distribution for time for him to enter the room seven times is binomial.

on average it would take 700 days to free the prisoners.

actually a little more, because it's possible the guy would enter the room 7 times, and still find not everybody had entered, in which case you would have to wait another 100 days.

however, it is likely that no such efficient algorithm for communicating the information through the light bulb exists. this merely sets a minimum bound on how fast they can get out. i think the minimum average time is longer, but i don't know how to prove that no better algorithm than those already found exists

in as far as finding the probability that everyone has visited the room after a certain number of days, i'm embarrassed to admit i thought about it a while and don't know the answer. i asked my friend who is smarter than i am and he didn't know, either.

anyway, i know that the method of .99^n for the probability that a given guy has not entered the room isn't helpful, because the individual prisoners' probabilities are not independent.

if anyone does figure out the exact probability (approximate is pretty easy) i'd be interested in seeing it

jrm wrote:

You make sure everyone changes the light once. If the prisoner goes into the room and the light is off, and he has never turned it on, then he turns it on. If the light is off, and he has turned it on once already, he leaves it alone. You designate one person the "On" person. This is the only person who can turn the light on. Every time he walks into the room and the light is on he will turn it off. Once he turns it off 99 times than every has been in the room.

That certainly works, but is it optimal? I can't think of anything better, it's definitely better than waiting a really long time.

Okay, so explain to me how these two statements don't conflict:

If the prisoner goes into the room and the light is off, and he has never turned it on, then he turns it on. If the light is off, and he has turned it on once already, he leaves it alone. You designate one person the "On" person. This is the only person who can turn the light on.

How can the other prisoners meet your condition when you state that the "On" person is the only person who can turn on the light?

Pamela Anderson's Left Nipple wrote:

jrm wrote:

If the prisoner goes into the room and the light is off, and he has never turned it on, then he turns it on. If the light is off, and he has turned it on once already, he leaves it alone. You designate one person the "On" person. This is the only person who can turn the light on.

How can the other prisoners meet your condition when you state that the "On" person is the only person who can turn on the light?

Typo? Replace On with Off in the last bold section.

Are you really still trying to argue that this solution doesn't work? Yes, the guy made a mistake when he stated his solution, but the idea is pretty simple and it works.

I told my wife this riddle last night and the first thing she said to me was "why don't the prisoners leave a shoe or something the first time in the room then when a guy counts 100 shoes they are done."

....that never crossed my mind. Why don't women run the world?

If the prisoner goes into the room and the light is off, and he has never turned it on, then he turns it on. If the light is off, and he has turned it on once already, he leaves it alone. You designate one person the "OFF" person. This is the only person who can turn the light off.

I think this will shut me up for a while...

Dear god. Others ways smarter than us have contributed an inordinate amount of time on this. Check out this link to a Berkely researcher and his message board for riddles.

(Kinda cool to click around and read math grad students brag about how their algorithm knocked 29 days off of the certainty time line...).

Apparently these guys don't run.

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard

;action=display;num=1027805293;start=0

Pamela Anderson's Left Nipple wrote:

I think this will shut me up for a while...

Thank God. I'm glad you're not as much of ass as you seem, and that you can accept when you're wrong. The next step you need to learn is how to apologize to everyone you've been an ass to in the course of your extended parade of wrongheadedness.

Pamela Anderson's Left Nipple wrote:

How on God's Earth did you even come up with this analogy. This isn't even close to my argument. Random selection means that YOU might (or might not) win the lottery, but the question isn't about just YOU, it's about the status of 99 other people, none of which you can communicate with.

Your argument: because there is a chance that they will never make it into the room, there is NO way for them to confirm that they have all been in the room.

My analogy: because there is a chance that I will never win the lotter, there is NO way for me to confirm that I've been in lottery.

You weren't making any claims about communication; you were just saying that the chance of them never making it kept there from ever being an acceptable solution. I didn't think it was my job to state the answer, as I thought it had already been laid out pretty clearly how the light DOES allow for communication.

this is correct.

Let me change gears on this, so we can use our brains and stop attacking each other.

10 straight-jacketed prisoners are on death row. Tomorrow they will be arranged in single file, all facing one direction. The guy in the front of the line (he can't see anything in front of him) will be called the 1st guy, and the guy in the back of the line (he can see the heads of the other nine people) will be called the 10th guy. An executioner will then put a hat on everyone's head; the hat will either be black or white, totally random. Prisoners cannot see the color of their own hat. The executioner then goes to the 10th guy and asks him what color hat he is wearing; the prisoner can respond with either "black" or "white". If what he says matches the color of the hat he's wearing, he will live. Else, he dies. The executioner then proceeds to the 9th guy, and asks the same question, then asks the 8th guy ... this continues until all of the prisoners have been queried.

This is the night before the execution. The prisoners are allowed to get together to discuss a plan for maximizing the number of lives saved tomorrow. What is the optimal plan?

I can accept that I am wrong, but go back to each psot where I was an ass and tell me which situation where I was correct in dispelling their given solutions. Even when I said I was wrong about their being an actual solution, I was correct in stating that the solution, the assertion with 100% accuracy that all prisoners had been in the room, could never come to fruition. In other words, even though an accurate plan had been designed, it is theortically possible that the plan could never be implemented.

No, sorry, apples and oranges again. Your analogy has you making an assertion for yourself. As I was addressing the problem with the proposed solution, I was stating that one person could not make an assertion for the whole group, which, of course I was wrong.

I was wrong, and I admit I was wrong. However, every claim that I argued against was incorrect as well. Please note that someone pointed out the typo (which really wasn't a typo, as the poster typed "ON" in the same sentence in for both instances), I reposted the solution with the correct wording, and then admitted my mistake. It takes big balls to do that, and since I'm only a nipple and one half of a great set of cans, that in and of itself is a miracle.

Agreed there.

The way your statement was phrased, you were not just addressing one proposed solution, but claiming that no solution could be ever be found.

Fair enough. And you made me laugh enough to admit that I was being a bit of an ass myself there, so whatever.

It's a trick question.

You can't bury survivors.

At least the 10th guy can save one life for sure. Since he has a 50/50 chance of wearing a black or a white hat, there's nothing he can do to save his own life, but he has 100% chance to save the 9th guy.

He should say the color of the hat of the 9th guy in front of him. That would allow the 9th guy to know about his color, and save his life.

Also, if I were in that situation, I would discuss a way to indicate the color in front of me.

Of course, the 9th guy is going to say Black if the 10th guy tipped him about that color, but he should also be able to tell the 8th guy about his color. They just have to use a code--for example "it's black" means the 8th guy is black too, and just "black" means the 8th guy is not wearing black. Hopefully the executioner won't get it.

That way, they can save with certainty 9 guys out of 10, and perhaps 10 / 10 if the first guess is a lucky one. That's a good 90 to 100 % saving ratio.

If you just want to talk probabilities, they should count the number of black and white hats in front of them, and take an educated guess.

I'd rather choose option 1.

Without any codes, #'s 10,8,6,4,2 would say the color of the hat in front of them. This way #'s 9,7,5,3,1 would guarantee survival. Plus average odds would say another two or three of the even numbered group lived.

With codes, Alice runner's solution is a good way to save 9 at least and leave the tenth at the mercy of chance.

It is entirely possible that every prisoner will visit the room, making it posible for someone to make that assertion with 100% certainty. I won't deny that fact. What the problem requires you to explain is how 100 prisoners will know whether or not each has been in the room with 100% certainty. Remember, they are in solitary confinement with no means of communication.

listen jackass, before you act all smart maybe you should make sure you yourself understand what the riddle says. the riddle never says all 100 prisoners must know whether or not each has been in the room. only one person must know if all 100 have been in the room.

Alice Runner wrote:

If you just want to talk probabilities, they should count the number of black and white hats in front of them, and take an educated guess.

I'd rather choose option 1.

That won't help, since each hat is randomly chosen; there aren't five and five of each. If there would, it would be quite easy to save all ten lives, since each prisoner can see all of the heads in front of him or her.