The Prisoners and the Lightbulb

Dross · 2006-09-20 21:46:06

Set-up:

Here's an interesting one for you...

There are 100 prisoners that have been taken to an alien planet, and told what is going to happen to them.

They will each be taken to a heavily guarded, individual cell and put to sleep. The aliens will - entirely at random - choose an individual each hour and wake them up. Said individual will be taken to a central room.

The central room contains only two items: a light bulb and a lightswitch that controls the bulb. When an individual is taken to the central room, they will be given an oportunity to flick the switch to turn the light bulb on or off, though they may choose not to flick the switch.

They will also be given an oportunity to say whether they want to go back to earth or not, but there is a catch: If a prisoner says they want to go back to earth and not every prisoner has had at least one visit to the central room, all the prisoners will be killed. If all the prisoners have been in the central room, however, all the prisoners will be taken back to earth as per the request.

If they have not opted to go back to earth, the individual will then be taken back to their room and put to sleep again.

Shortly after they are captured and before they are separated, the prisoners are given a few minutes to confer with one another and come up with a plan to get home. After the prisoners are separated, sufficient measures are taken to ensure that no further communication may occur between the prisoners, excluding use of the light bulb.

Additionally, although the order the prisoners are brought to the room in is random, the aliens will "fix" it so that every prisoner will visit the central room at least once every n years. The value of n is not known by the prisoners. Also, the alien world is placed in a time-lock, so the prisoners will not age during their imprisonment and it does not matter how long they spend there. Remember that, being asleep for most of the time, the prisoners will have no idea how much time has passed between each visit to the central room.

Challenge:

Find a strategy that will garuntee the prisoners get home. (not just that the prisoners will probably get home)

Last edited by Dross (2006-09-20 21:54:46)

mahmoudaljamel · 2006-09-20 22:15:51

No chance , they will be killed all !!
Dross :
give us time to think , please

numen · 2006-09-21 00:07:27

So, basically, a prisoner must be absolutely sure that everyone has visited the central room at least once when he says he wants to go home. But they can only contact eachother through the switch... So they must be clever enough to figure out what n is, right? or perhaps be able to count to 100 through the switch? I guess that's two options.

We might have to group the prisoners somehow before they are being put into the cells.

Is the switch on or off from the start?

Dross · 2006-09-21 00:41:38

numen wrote:

So they must be clever enough to figure out what n is, right?

No - because the selection of prisoners was quoted as being "at random", the n was just put in there to garuntee that, if you wait long enough, then eventually all the prisoners will have been in the room.

Instead, you could relax this condition, and give an algorithm that means that the prisoners can get home IF the prisoners have been in the room a sufficient number of times.

For all practical purposes, ignore n - there is no way the prisoners can find out what it is, and they don't need to.

numen wrote:

Is the switch on or off from the start?

Prisoners get to choose before being taken to their cells.

mathsyperson · 2006-09-21 01:43:13

I'm assuming they can't do anything other than possibly flick the switch, right? Like, they can't write on anything or whatever. Also, is there any penalty if a prisoner says they want to stay on the ship and every other prisoner had already visited?

Dross · 2006-09-21 02:11:08

I'm assuming they can't do anything other than possibly flick the switch, right? Like, they can't write on anything or whatever.

Correct - in the initial post I've put the (hopefuly) catch-all clause of "After the prisoners are separated, sufficient measures are taken to ensure that no further communication may occur between the prisoners, excluding use of the light bulb."

So if you think you've found a way the prisoners can communicate after they're separated, the aliens will have taken whatever measures ensure that they cannot.

Also, is there any penalty if a prisoner says they want to stay on the ship and every other prisoner had already visited?

None... except they don't get to leave! Like I said, the time taken is irrelevant, so there is no need to try and produce some optimum solution - just a solution will suffice.

numen · 2006-09-21 02:23:54

I think I have a solution now, it wasn't that hard when you think about it. But it'll take quite some time, but you said the time taken was irrelevant

Dross · 2006-09-21 02:58:15

Ah... I have a different way to do it (yours certainly looks different to start with!).

I'd like to know your way... I will ponder how to do it via your hint!

Dross · 2006-09-23 05:49:51

Is anybody still working on this?

Here's a hint for one way to solve this problem (different to the previous hint)

Though I still cannot find a different solution via the hint given by numen. Numen, I would be very interested to read your solution at some stage.

Last edited by Dross (2006-09-23 05:50:13)

numen · 2006-09-23 07:19:38

I really have no idea how else to solve this. Your hint is pretty much how I define my groups, if I understand it correctly. If your solution really is different, I'd like to know it as well.

I'll hold it a bit more though. I'll post my solution on monday if I can remember that

mahmoudaljamel · 2006-09-23 20:11:55

If we assign a man to say : i want to go back to earth , he can say that after he is taken to the central room the second time.
since the time is not important for them , then this is an acceptable solution based on Dross hint.

Kurre · 2006-09-23 21:24:21

mahmoudaljamel wrote:

If we assign a man to say : i want to go back to earth , he can say that after he is taken to the central room the second time.
since the time is not important for them , then this is an acceptable solution based on Dross hint.

no since all prisoners are picked randomly and therefor a prisoner can be brought to the central room twice before everyone else have been there...

Dross · 2006-09-23 23:18:36

Kurre wrote:

mahmoudaljamel wrote:
If we assign a man to say : i want to go back to earth , he can say that after he is taken to the central room the second time.
since the time is not important for them , then this is an acceptable solution based on Dross hint.
no since all prisoners are picked randomly and therefor a prisoner can be brought to the central room twice before everyone else have been there...

Indeed - it might be a million years before the time that all the prisoners are garunteed to have visited the room, and the person asigned to say they want to go back could easily be the 1st and 2nd person chosen, without even realising it!

mathsyperson · 2006-09-23 23:50:35

My best idea was along the same lines, even though I know it's not completely right.

I was thinking along the lines of "each person counts the number of times that they have been taken to visit the room. If they have visited the room x or more times, they turn on the light. If they haven't, they leave/turn the light off. If they have visited the room x or more times and the light is on, they ask to go free."

And then x can be altered. The higher it is, the longer it will be before the prisoners are freed, but also the higher the chance they have of succeeding. But unfortunately, it can never be absolutely certain. The aliens might just show one prisoner to the room x+1 times at the start.

Kurre · 2006-09-24 01:05:17

i think it is impossible.
since the lightbulb only have 2 "values", on or off, one of these must mean that everyone have been there or not. which means that someone before must know by looking at the lightbulb that he is the final prisoner to visit the room, so he can tell the next one to ask the aliens. but to know that, a prisoner before must have decided the lightbulbs state (by looking at its previous state) to tell the next prisoner, to tell the next prisoner to ask the aliens...but to know that, a prisoner before etc etc
which in my logic says that the light bulb must have 100 states, one for every prisoner.

the only solution i can come up with is that every prisoner screws(?) the lightbulb from its ground 1/100 of the total length the first time they visit the room, so the one that can remove the lightbulb asks the aliens .

or just bribe the aliens...

edit: i just saw that the time between every visit is set to one hour. How long time do every prisoner have in the room? if they stay for more than one hour, do they get company?
and also dross, i hope the solution doesnt have anything to do with the lightbulb being warm or not??

Last edited by Kurre (2006-09-24 01:11:17)

Dross · 2006-09-24 02:27:27

Kurre wrote:

i think it is impossible.
since the lightbulb only have 2 "values", on or off, one of these must mean that everyone have been there or not. which means that someone before must know by looking at the lightbulb that he is the final prisoner to visit the room, so he can tell the next one to ask the aliens. but to know that, a prisoner before must have decided the lightbulbs state (by looking at its previous state) to tell the next prisoner, to tell the next prisoner to ask the aliens...but to know that, a prisoner before etc etc
which in my logic says that the light bulb must have 100 states, one for every prisoner.

One thing I'll say, is that there are a lot of false assumptions in there...

...or possibly just one big one...

Kurre wrote:

the only solution i can come up with is that every prisoner screws(?) the lightbulb from its ground 1/100 of the total length the first time they visit the room, so the one that can remove the lightbulb asks the aliens .
or just bribe the aliens...
edit: i just saw that the time between every visit is set to one hour. How long time do every prisoner have in the room? if they stay for more than one hour, do they get company?
and also dross, i hope the solution doesnt have anything to do with the lightbulb being warm or not??

The prisoners are not allowed to touch the lightbulb - only the switch. And the solution would be the same regardless of whether or not the prisoners can touch the switch (i.e. it could be that they tell the aliens whether they want to flick the switch or not)

The prisoners get less than an hour in the room. Specifically they have little enough time in the room that they can be taken back to thier own cell and put to sleep again before it's time to wake up the next person. In particular, this means that a prisoner has no idea if they were the last person to visit the room or not. The time between visits is unimportant.

There is no "trickery" in this puzzle!

Dross · 2006-09-24 02:30:57

numen wrote:

I'll hold it a bit more though. I'll post my solution on monday if I can remember that

Would you mind leaving it until, say, Wednesday? Some members may not be able to get on the forum during weekends/very often, for whatever reason.

In fact, could you e-mail me your solution? (I don't know what the deal is with PMs on this forum... I don't seem to be able to, anyways!)

Last edited by Dross (2006-09-24 03:54:38)

numen · 2006-09-24 03:09:22

Dross wrote:

numen wrote:
I'll hold it a bit more though. I'll post my solution on monday if I can remember that
Would you mind leaving it until, say, Wednesday? Some members may not be able to get on the forum during weekends/very often, for whatever reason.
In fact, could you e-mail me your solution? (I don't know what the deal is with PMs on this forum... I don't seem to be able to, anyways!)

Sure thing. I'll e-mail my solution soon, hoping that, in return, you'll e-mail me yours Hopefully you can confirm it's correct.

Kurre · 2006-09-24 07:34:01

okey i was wrong, it was possible. I found a solution
should i wait with posting it? or should i email it?

Last edited by Kurre (2006-09-24 07:51:55)

Dross · 2006-09-24 10:58:34

I'd be grateful if you could e-mail it to me - I want to hold the solution back until Wednesday first, though. Partly to let everyone who wants to work on it, work on it, and partly to see if anybody comes up with a diferent solution.

Last edited by Dross (2006-09-30 00:10:05)

Patrick · 2006-09-24 17:47:00

I just started working on this one last night, so I'd appreciate that very much!

Dross · 2006-09-30 00:16:21

Thought I'd finally post a solution to this, if anybody was still interested!

Well done to Kurre and Numen who both got the (a...?) correct solution.

numen · 2006-09-30 10:18:58

I haven't managed to figure out another solution to this problem, all other options I had in mind doesn't seem to work out with 100% accuracy. You think this is the only solution?

Math Is Fun Forum

#1 2006-09-20 21:46:06

The Prisoners and the Lightbulb

#2 2006-09-20 22:15:51

Re: The Prisoners and the Lightbulb

#3 2006-09-21 00:07:27

Re: The Prisoners and the Lightbulb

#4 2006-09-21 00:41:38

Re: The Prisoners and the Lightbulb

#5 2006-09-21 01:43:13

Re: The Prisoners and the Lightbulb

#6 2006-09-21 02:11:08

Re: The Prisoners and the Lightbulb

#7 2006-09-21 02:23:54

Re: The Prisoners and the Lightbulb

#8 2006-09-21 02:58:15

Re: The Prisoners and the Lightbulb

#9 2006-09-23 05:49:51

Re: The Prisoners and the Lightbulb

#10 2006-09-23 07:19:38

Re: The Prisoners and the Lightbulb

#11 2006-09-23 20:11:55

Re: The Prisoners and the Lightbulb

#12 2006-09-23 21:24:21

Re: The Prisoners and the Lightbulb

#13 2006-09-23 23:18:36

Re: The Prisoners and the Lightbulb

#14 2006-09-23 23:50:35

Re: The Prisoners and the Lightbulb

#15 2006-09-24 01:05:17

Re: The Prisoners and the Lightbulb

#16 2006-09-24 02:27:27

Re: The Prisoners and the Lightbulb

#17 2006-09-24 02:30:57

Re: The Prisoners and the Lightbulb

#18 2006-09-24 03:09:22

Re: The Prisoners and the Lightbulb

#19 2006-09-24 07:34:01

Re: The Prisoners and the Lightbulb

#20 2006-09-24 10:58:34

Re: The Prisoners and the Lightbulb

#21 2006-09-24 17:47:00

Re: The Prisoners and the Lightbulb

#22 2006-09-30 00:16:21

Re: The Prisoners and the Lightbulb

#23 2006-09-30 10:18:58

Re: The Prisoners and the Lightbulb

Board footer