100 prisoners and a lightbulb

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Prelates, Moderators General

100 prisoners and a lightbulb

Postby Yakk » Thu Apr 12, 2007 6:19 pm UTC

Edit: Changed it to an easier version of the same puzzle. The original version is one of the varients. Also cleared up the fact that the switch and the lightbulb are connected.

"Take a look around you. I am going to lock up all 100 of you scum. Unless you can solve my puzzle, none of you will ever see the light of day, and none of you will ever see each other, ever again.

I am going to throw you all into cells. Every day, right after supper, I will randomly pick a prisoner, and take them to a room. In that room there is one lightbulb and one switch.

The only thing you will be permitted to do in the room is look at the lightbulb, and flip the switch that turns the lightbulb on and off if you want to.

Then you will be removed from the room, and returned to your cell, unless you claim that every single prisoner has been in the room.

If you make this claim, and you are right, you are all free to go.

If you make this claim, and you are wrong, you will all be killed.

Enjoy your last hour of contact with each other, scumbags. You get to spend the next hour thinking up the best plan your feeble minds are capable of."


Can the prisoners escape?

(Note: This is a reasonably famous puzzle. Many people will have the answer at their fingertips. I advise you to try solving it before reading the spoilers!)

Varients:

1. The prisoners cannot keep time. They cannot tell how many days it has been since the start of the test, or how many days it has been since they last where in the room.

2. The prisoners are robots. They can all follow the same algorithm, but they are not allowed to have a distinct prisoner before hand.
Last edited by Yakk on Thu Apr 12, 2007 11:01 pm UTC, edited 3 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10450
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby ekim » Thu Apr 12, 2007 6:33 pm UTC

Yes, but you need the promise that "randomly pick" includes everyone, or just that at any given point in time, everyone will get called in at some point in the future.

The trick: assign someone the job of turning the light off, and everyone else the job of turning the light on.
ekim
 
Posts: 82
Joined: Mon Dec 18, 2006 12:40 pm UTC
Location: Seattle

Postby bbctol » Thu Apr 12, 2007 9:02 pm UTC

Do they have to flip the switch? Can they flip the switch as often as they like? Does the switch control the lightbulb? If so, I think I can figure this out.
User avatar
bbctol
Super Deluxe Forum Title of DESTINYâ„¢
 
Posts: 3137
Joined: Tue Mar 06, 2007 10:27 pm UTC
Location: The Twilight Zone

Postby Lior » Thu Apr 12, 2007 9:13 pm UTC

Is the initial state of the lightbulb known?
What is the time frame for "every once in a while"? I have an idea, but if the time frame for each visit is long it might take them many many years.
User avatar
Lior
 
Posts: 15
Joined: Sat Apr 07, 2007 3:15 pm UTC
Location: Israel

Postby SittingInTheDark » Thu Apr 12, 2007 9:29 pm UTC

i think the 100 prisoners can only talk to each other together once for a strategy and then they can't communicate because if that weren't the case each one would just shout "i was in"

so here's the solution:

make one the master, only he may turn the switch on

if someone other goes in and
- the light is on he turns it off, but only if hasn't turned it off once, otherwise let it be

- the light is off let it be

each time the master turns the light on he counts one up
so if he counts to 99 all other were in there, but problem is what happens if light was off at beginning and master comes in first, would be a problem, or not?
no

each one may turn light off 2 times and master counts 2*99-1, so he might miss a second one from one person but that doesn't matter because everyone just has to be in at least once
SittingInTheDark
 
Posts: 1
Joined: Thu Apr 12, 2007 9:21 pm UTC

Postby Castaway » Thu Apr 12, 2007 9:34 pm UTC

this is out there, but here goes something that I made up: So, the first person goes in and breaks the lightbulb into 100+ pieces, and puts one in a line. Then, every prisoner that goes in henceforth puts one more piece in the pile. If/when there are 100 shards in that line, then somebody makes the claim that everybody's been in there and voila! everyone wins!
You've just lost twenty dollars and my self respect.

Rat wrote: so i sprinted back down this hill like a fucking mountain goat
User avatar
Castaway
Mr. Fancy-Pants
 
Posts: 2150
Joined: Wed Apr 11, 2007 1:05 am UTC
Location: Brooklyn

Postby imMAW » Thu Apr 12, 2007 9:42 pm UTC

First, pick the smartest person in the group to decide how long it will take for the bulb to burn out. Divide this number by 100, and have everyone leave the bulb on for that amount of time. When the bulb burns out, pray that the persons estimate was right, and claim everyone has been in. :D
imMAW
 
Posts: 112
Joined: Sun Mar 18, 2007 10:30 pm UTC
Location: Chicago

Postby Yakk » Thu Apr 12, 2007 10:55 pm UTC

Yes, you can't communicate other than through the lightbulb.

Yes, the switch controls the lightbulb.

You, and every other prisoner, will be shot if you violate the rules above.

Changed the puzzle to an easier version. Varient #1 is what I orginally posted.

Castaway wrote:
this is out there, but here goes something that I made up: So, the first person goes in and breaks the lightbulb into 100+ pieces, and puts one in a line. Then, every prisoner that goes in henceforth puts one more piece in the pile. If/when there are 100 shards in that line, then somebody makes the claim that everybody's been in there and voila! everyone wins!


Congradulations, you where all shot. :)
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10450
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby Cosmologicon » Fri Apr 13, 2007 12:30 am UTC

Man, I always feel bad for the poor schlubs in this puzzle. Why don't you make it 20 prisoners instead of 100, and at least give them a chance of getting out before Andy Dufresne?
User avatar
Cosmologicon
 
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

Postby Castaway » Fri Apr 13, 2007 1:26 am UTC

if it helps, they aren't real prisoners. Our entire legal system is not based on Oedipus and The Sphynx.
You've just lost twenty dollars and my self respect.

Rat wrote: so i sprinted back down this hill like a fucking mountain goat
User avatar
Castaway
Mr. Fancy-Pants
 
Posts: 2150
Joined: Wed Apr 11, 2007 1:05 am UTC
Location: Brooklyn

Postby HenryS » Fri Apr 13, 2007 2:54 am UTC

Cosmologicon wrote:Man, I always feel bad for the poor schlubs in this puzzle. Why don't you make it 20 prisoners instead of 100, and at least give them a chance of getting out before Andy Dufresne?
As we noted in http://www.segerman.org/prisoners.pdf (lots of spoilers), there are strategies for 100 prisoners with expected times less than 4000 days, or about 11 years.

[edit]Even more fun variants: not only do they need to know that everyone else has been in the room, they also need to all have transmitted messages of arbitrary lengths to everyone else.
Last edited by HenryS on Fri Apr 13, 2007 4:34 am UTC, edited 1 time in total.
User avatar
HenryS
 
Posts: 199
Joined: Mon Nov 27, 2006 9:16 am UTC
Location: Melbourne

Re: 100 prisoners and a lightbulb

Postby skeptical scientist » Fri Apr 13, 2007 4:15 am UTC

For variant 2:

Each prisoner follows the following strategy:
Put n=0

If you see the light off, and n is not -1, turn the light on, and increment n.

If you see the light on, and n is not -1, turn it off, and decrement n.

If n=100, report that all prisoners have been in the room.

Note that the sum, over all prisoners, of that prisoners value for n is always 0 (if the light is off) or 1 (if the light is on). So the only way that n can ever reach 100 is if all other prisoners have n=-1, so if the report is ever made, it will be correct, since n=0 until a prisoner has entered the room. So we need only show that a report will eventually be made.

Note further that if some prisoner's n reaches -1, that prisoner never does anything again, and their value stays constant at -1. If we call such a robot inactive, the amount of active robots is decreasing. Also, if n is not -1, then either n=99 (so the next time they go in the room, assuming the light is off, n will reach 100 and they will win), or there is another active robot. If there are two active robots, then depending on who is randomly picked to be in the room in what order, either can have their value of n go up or down. If the one with the lowest value is repeatedly sent in when the light is on, turns it off, and someone with the higher n value is then sent in and turns it on, that robot will become inactive, so every robot has a nonzero probability of becoming inactive in at most 2*n+1 days. Since we have an infinite number of days to work with, each robot will, with statistical certainty, eventually become inactive unless they are the only remaining active robot, so with a statistical certainty, the robots will win, assuming the choice of robot is truly random.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby Cosmologicon » Fri Apr 13, 2007 5:33 am UTC

HenryS wrote:
Cosmologicon wrote:Man, I always feel bad for the poor schlubs in this puzzle. Why don't you make it 20 prisoners instead of 100, and at least give them a chance of getting out before Andy Dufresne?
As we noted in http://www.segerman.org/prisoners.pdf (lots of spoilers), there are strategies for 100 prisoners with expected times less than 4000 days, or about 11 years.

Yeah, if you run an optimization on the free parameters of a certain complicated model! These people have one hour to discuss it, and probably not a computer. I think the best they can hope for is a slight modification of Strategy 2, which (IIRC) gives them an expected time around 23 years.
User avatar
Cosmologicon
 
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

Postby Captain_Thunder » Fri Apr 13, 2007 9:58 am UTC

Assumming a different person is chosen each time to go into the room, all they would have to do is wait 100 days. The person who goes in after the 100th supper would be able to say that they are the last one to go in the room.
Captain_Thunder
 
Posts: 83
Joined: Tue Mar 27, 2007 9:18 pm UTC

Postby skeptical scientist » Fri Apr 13, 2007 1:12 pm UTC

Captain_Thunder wrote:
Assumming a different person is chosen each time to go into the room, all they would have to do is wait 100 days. The person who goes in after the 100th supper would be able to say that they are the last one to go in the room.

They're chosen randomly each time, so the probability of that happening is 100!/100^100, or about 1x10^-42. Congratulations, you're all dead.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby hermaj » Fri Apr 13, 2007 1:17 pm UTC

Yakk, did you use the search function at all before posting this thread? I cannot help but think that this puzzle has been presented before - and for that matter, more than once.


EDIT:
http://forums.xkcd.com/viewtopic.php?t=73

And a variant replacing switch with turning an object upside-down and right-side-up. http://forums.xkcd.com/viewtopic.php?t=514


I'll leave this open for now, I guess, unless another mod sees fit to close it. (These puzzles were presented a while back, I guess.) That said; for next time - search function, please.
Last edited by hermaj on Fri Apr 13, 2007 1:23 pm UTC, edited 1 time in total.
User avatar
hermaj
 
Posts: 6139
Joined: Sun Oct 15, 2006 10:37 am UTC
Location: Sydney, Australia

Postby skeptical scientist » Fri Apr 13, 2007 1:19 pm UTC

Cosmologicon wrote:Yeah, if you run an optimization on the free parameters of a certain complicated model! These people have one hour to discuss it, and probably not a computer. I think the best they can hope for is a slight modification of Strategy 2, which (IIRC) gives them an expected time around 23 years.

I imagine that beats the hell out of my variant 2 strategy, where you have to wait for a random walk in n variables to hit some hyperplane 100 different times. Fortunately robots generally have long lifespans.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby skeptical scientist » Fri Apr 13, 2007 1:20 pm UTC

hermaj wrote:Yakk, did you use the search function at all before posting this thread? I cannot help but think that this puzzle has been presented before - and for that matter, more than once.

If it's been posted long enough ago that people don't remember it, and many haven't seen it, what's the harm? It's not like people are reading through the puzzle archives, so sufficiently good puzzles merit reposting every now and then.

If people repost a puzzle from a few days ago or lower down the page, then that's kind of silly, but if someone posts a puzzle from a year ago, then the puzzle was probably interesting enough to be worth reposting.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby Belial » Fri Apr 13, 2007 1:34 pm UTC

You bump the previous thread, don't make a new one.
addams wrote:A drunk neighbor is better than a sober Belial.
User avatar
Belial
A terrible sound heard from a distance
 
Posts: 30227
Joined: Sat Apr 15, 2006 4:04 am UTC

Postby HiEv » Fri Apr 13, 2007 2:00 pm UTC

Cosmologicon wrote:
HenryS wrote:As we noted in http://www.segerman.org/prisoners.pdf (lots of spoilers), there are strategies for 100 prisoners with expected times less than 4000 days, or about 11 years.
Yeah, if you run an optimization on the free parameters of a certain complicated model! These people have one hour to discuss it, and probably not a computer. I think the best they can hope for is a slight modification of Strategy 2, which (IIRC) gives them an expected time around 23 years.

Well, I guess it depends on whether you're willing to trade a shortened stay for a degree of uncertainty. I ran a few simulations of this situation 100,000 times, and the largest number of days I saw before all 100 prisoners had been to that room was 1,775 days (4 years and 314 days.)

Just to give you a few other sample statistics:

The smallest number of days I ever saw: 226 days
Average number of days needed: ~520 days
Median number of days needed: ~500 days
Number of days needed to be successful 99% of the time: ~915 days (~2.5 years)
Number of days needed to be successful 99.5% of the time: ~985 days (~2.7 years)

So, if they're willing to simply play the odds, they could get out in considerably less time. :)
The difference between intelligence and stupidity is that intelligence has its limits.
User avatar
HiEv
 
Posts: 37
Joined: Wed Apr 11, 2007 7:45 am UTC

Postby ptveite » Fri Apr 13, 2007 2:22 pm UTC

I've seen this before with 3 prisoners....much more humane, and the same basic answer.
ptveite
 
Posts: 159
Joined: Tue Dec 12, 2006 3:15 pm UTC

Postby Yakk » Fri Apr 13, 2007 2:25 pm UTC

Sorry: the only lightbulb threads in the logic puzzles form where different.

The switch thread contains a very similar puzzle, except for the lack of a lightbulb, and the lack of varients. :/ Didn't find that one before I posted.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10450
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby Cosmologicon » Fri Apr 13, 2007 4:57 pm UTC

HiEv wrote:I ran a few simulations of this situation 100,000 times, and the largest number of days I saw before all 100 prisoners had been to that room was 1,775 days (4 years and 314 days.)

Just to give you a few other sample statistics:

The smallest number of days I ever saw: 226 days
Average number of days needed: ~520 days
Median number of days needed: ~500 days
Number of days needed to be successful 99% of the time: ~915 days (~2.5 years)
Number of days needed to be successful 99.5% of the time: ~985 days (~2.7 years)

So, if they're willing to simply play the odds, they could get out in considerably less time. :)

That's pretty good, but you can also do it by hand. For any large number of days N, the probability that you get them all in that much time can be estimated very well by 1 - 100(0.99^N). (The second-order term, which can be used as an upper-limit of the error on this estimate, is 4950(0.98^N).) So you can see that you have a 99999/100000 chance after 1604 days.

But of course this is a puzzle! When I'm telling it, I say the warden tells them, "If you make this claim, and you can prove that you are right, you are all free to go. If you make this claim, and you cannot prove it, you will all be killed."


I just realized that my favorite strategy (that takes about 23 years I think) works with Yakk's variant 2 but not with variant 1, that is, the prisoners must be able to keep time:
Basically it's just like SittingInTheDark's solution, except that the master is assigned at runtime. The first person who enters the room twice becomes the master, and gets a head start at counting everyone who's already been in the room once. In the first 100 days, nobody touches the light except that the master turns it off on her second visit. If someone enters the room in the first 100 days and it's on, they consider themselves counted, and if not, they just leave it alone. The master begins with the count set to the day before her second visit.
User avatar
Cosmologicon
 
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

Postby Yakk » Fri Apr 13, 2007 6:35 pm UTC

My first solution to this was epicly inefficient:


Every prisoner gets a number, from 1 to 100.

They count days.

If DayNum != PrisonerNumber mod 100, they turn off the light. Otherwise they leave it alone.

Prisoner #1 turns on the light if it is off and it is Prisoner #1's day.

Prisoner #100 says "we have all been in the room" if he enters the room on his day and the light is on.

The expected wait time is rather ridiculous. :)
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10450
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby skeptical scientist » Fri Apr 13, 2007 6:49 pm UTC

Cosmologicon wrote:Basically it's just like SittingInTheDark's solution, except that the master is assigned at runtime. The first person who enters the room twice becomes the master, and gets a head start at counting everyone who's already been in the room once. In the first 100 days, nobody touches the light except that the master turns it off on her second visit. If someone enters the room in the first 100 days and it's on, they consider themselves counted, and if not, they just leave it alone. The master begins with the count set to the day before her second visit.

This doesn't seem like it works.
If the first person who enters twice is the master, they need to know they're the first person to enter twice. If we assume the light starts on, then how does someone know if the light has ever been turned off, assuming that the light is on when they enter?

Also, when I first read the puzzle, I could have sword it said the intervals were also random, so that's the version I solved (well, the variant where they all follow the same strategy, and the intervals are random.)
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby Yakk » Fri Apr 13, 2007 6:52 pm UTC

skeptical scientist wrote:Also, when I first read the puzzle, I could have sword it said the intervals were also random, so that's the version I solved (well, the variant where they all follow the same strategy, and the intervals are random.)


Edit:Changed it to an easier version of the same puzzle. The original version is one of the varients. Also cleared up the fact that the switch and the lightbulb are connected.


Yes, I changed it. I decided to post varients, and figured "why not post the easiest varient as the main puzzle".

I then documented my change. I source control gud!
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10450
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby skeptical scientist » Fri Apr 13, 2007 7:01 pm UTC

Yakk wrote:My first solution to this was epicly inefficient:

The expected wait time is rather ridiculous. :)

Yes, an expected wait of 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 times the estimated age of the universe is a little ridiculous, isn't it?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby Yakk » Fri Apr 13, 2007 7:13 pm UTC

googel^2 powa!
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10450
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby Cosmologicon » Fri Apr 13, 2007 8:02 pm UTC

Hey skeptical scientist, I think my solution works fine. I think if you reread it you'll understand, but I can explain if you need. Just remember that it only works if the prisoners can keep track of time! Yours is the best solution I've seen that works under both variants 1 and 2 simultaneously.
User avatar
Cosmologicon
 
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

Postby skeptical scientist » Fri Apr 13, 2007 9:03 pm UTC

Cosmologicon wrote:Hey skeptical scientist, I think my solution works fine. I think if you reread it you'll understand, but I can explain if you need. Just remember that it only works if the prisoners can keep track of time! Yours is the best solution I've seen that works under both variants 1 and 2 simultaneously.

Nevermind, I missed the fact that nobody was allowed to touch the light in the first 100 days, except for the unique person who can turn it off.
Last edited by skeptical scientist on Fri Apr 13, 2007 9:07 pm UTC, edited 1 time in total.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby Cosmologicon » Fri Apr 13, 2007 9:06 pm UTC

Nobody turns on the light in the first 100 days.
User avatar
Cosmologicon
 
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA

Postby skeptical scientist » Fri Apr 13, 2007 9:07 pm UTC

Boo, you beat my rereading!
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby Yakk » Fri Apr 13, 2007 10:18 pm UTC

Ah, but there is a refinement!


If P#N has entered the room on day X and seen the light on, he knows that every prisoner from P#1 to P#X-1 has been in the room.

From then on, he turns the light on on days 1 through X-1 (but not on day X).

If X=N, then he turns the light on on days 1 through X.

This changes the expected wait time quite considerably. :)

It takes 100 iterations for prisoner #1 to be on day 1.

This almost certainly then results in two people knowing about prisoner #1.

Knowledge that prisoner #1 has been in the room then grows hyperbolicly.

When either of the two people enters the room on day 1, they have a 98/100 chance of informing someone else that someone else has been in the room.

Then a 97/100. Then 96/100.

As #1 stays on more and more, #2 becomes more and more likely to see it. Once he leaves the light on, the number of people who know about #2 grows at a similar rate.

Not sure what the exact bound is, but is is much better than 100^100.

:)
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10450
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby skeptical scientist » Fri Apr 13, 2007 10:41 pm UTC

Yakk wrote:Ah, but there is a refinement!


If P#N has entered the room on day X and seen the light on, he knows that every prisoner from P#1 to P#X-1 has been in the room.

From then on, he turns the light on on days 1 through X-1 (but not on day X).

If X=N, then he turns the light on on days 1 through X.

This changes the expected wait time quite considerably. :)

It takes 100 iterations for prisoner #1 to be on day 1.

This almost certainly then results in two people knowing about prisoner #1.

Knowledge that prisoner #1 has been in the room then grows hyperbolicly.

When either of the two people enters the room on day 1, they have a 98/100 chance of informing someone else that someone else has been in the room.

Then a 97/100. Then 96/100.

As #1 stays on more and more, #2 becomes more and more likely to see it. Once he leaves the light on, the number of people who know about #2 grows at a similar rate.

Not sure what the exact bound is, but is is much better than 100^100.

:)

Yeah, uh, Yakk, I'm still not impressed by the efficiency of your algorithm. In a world where exptime algorithms are considered bad, an algorithm which takes o(n!) time is beyond silly, and even a huge improvement is still a really bad algorithm.

Edit: although I have to say, there is something appealing about tremendously bad algorithms. It's like the origin of Graham's number. A bad upper bound is boring, but a hideously bad upper bound is funny.
Last edited by skeptical scientist on Fri Apr 13, 2007 10:50 pm UTC, edited 1 time in total.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby fynch » Fri Apr 13, 2007 10:44 pm UTC

ptveite wrote:I've seen this before with 3 prisoners....much more humane, and the same basic answer.



Humane for us... or for the prisoners?
User avatar
fynch
 
Posts: 69
Joined: Tue Mar 27, 2007 6:30 pm UTC

Postby Yakk » Fri Apr 13, 2007 11:15 pm UTC

*nod*: I'm well aware how horrid the algorithm, even with 'refinement', is.

I am curious how much faster the refinement makes it.

Knowledge of #1 gets spread at a rate of 100 * 100/N *(100-N)/100 assuming N people already know about #1.

This is bounded by 100^2.

If everyone knows about #1, then it takes roughly the same amount of time to find out about #2.

So this places an upper bound on the time it takes to solve the problem using my refinement at 100^3! A pretty good speedup from 100^100 eh?

As a bonus, individual prisoners can figure out the refinement independantly, after they leave and enter their rooms, and executing the refinement won't mess up the algorithm.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10450
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby skeptical scientist » Sat Apr 14, 2007 7:03 am UTC

Yakk wrote:So this places an upper bound on the time it takes to solve the problem using my refinement at 100^3! A pretty good speedup from 100^100 eh?

Assuming you're right about this, you've brought the time down from an absurd power of 10 times the age of the universe to roughly 1/3 of the age of the universe. An impressive speed-up, to be sure, but still slightly impractical.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby Yakk » Sat Apr 14, 2007 2:08 pm UTC

100^3 is is 2700 years.

An eyeblink. :) I'm sorry if you exist in an 8000 year old universe, but I'm communicating to you from a far older one. Understanding the inter-universe communication method would make an interesting project. Are there any wormholes on your internet connection?
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10450
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby skeptical scientist » Sat Apr 14, 2007 2:32 pm UTC

Oh, I was reading that as 10^(3!) because of the exclamation point. :P
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6152
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby Nidht » Sat Apr 14, 2007 7:26 pm UTC

We can't assume the warden turns the light on or off at the end of each prisoner's session.

Each visitor to the room scratches a mark on the wall, someplace obscure, making it look inconspicuous. Then all it takes is counting.
User avatar
Nidht
 
Posts: 6
Joined: Sat Apr 07, 2007 4:20 pm UTC

Next

Return to Logic Puzzles

Who is online

Users browsing this forum: No registered users and 10 guests