Author |
Topic: 100 prisoners & a light bulb (Read 166650 times) |
|
riadov
Newbie
don't get mad. get even
Gender: 
Posts: 4
|
 |
Re: 100 prisoners & a light bulb
« Reply #325 on: Feb 18th, 2005, 6:47pm » |
|
hey ICARUS u are the polite person here,10x  
btw MATTIAN try to speak 5 languages FLUENTLY (and i mean it:russian, english, french, arabic and arabic lebanese slang language);in addition that english isn't my native language(i said DON'T BE RUUUUDDDDEEE if i was wrong ;that means IF I MISUNDERSTOOD)
 think of that  and try to puzzle it or to make several forms of equations perhapse...I don't know...Oh yeah !!!! play chess with it 
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #326 on: Feb 18th, 2005, 7:19pm » |
|
Sorry, riadov, but you accidently set off something that has caused a lot of frustration. Many people are interested in this thread, and whenever they see a new post, they like to check it to see if someone has found an interesting new approach to this problem.
But far more often, it has been someone who did not bother to read even the first two or three pages, and posts a solution of "break the bulb" or "leave marks on the wall", or some other variation, without noting that this has been suggested many, many times before. There is nothing wrong with such solutions. The thing is, that is not what we find intriguing about this problem, so such solutions are just a nuisance.
Your suggestion is different from the "marker" solutions, but still bypasses why the problem is interesting to us, so all the frustration we feel tends to boil out. Still, patience is always the wiser course.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #327 on: Feb 20th, 2005, 8:32am » |
|
Hey Riadov,
Don't take my post the wrong way - As Icarus pointed out, you were something of a scapegoat for my response to the abundance of posts in this - the forum's flagship thread - which trivialize the puzzle. It is the longest thread because it has inherent intrigue due to the fact that there is no definitive answer, and no way of telling whether the current solution is in fact optimimum. It mirrors scientific development in which a good theory is said to be one which survives for a long time before it is disproven. In this thread, the best solution is about 3000 days and will remain so until it is less than that.
Also, it's very seldom that I can lash out at society and your post provided the trigger for me to do so. I think that has something to do with the fact that you did say you'd read all 22 pages, and having done so, I thought you might have noticed the building frustration with posters who attempted to solve the problem by technicality. This is a common post by newcomers except that they tend not to claim that they've read all the posts.
And finally, I've been slammed in this forum before as well - I tried to take it personally for a while, until I realised it wasn't intended that way. In my experience with this forum so far, vandalism is essentially non-existent and subscribers are here for one reason only - to solve problems because their jobs are boring, or whatever. My post was not so much a stab at you as it was a commentary on the lunacy which is our current society - call it a rant if you will.
Keep puzzling. And congrats on the languages - I know a number of cretins who don't speak any - a bit of English here and there, perhaps.
|
| « Last Edit: Feb 20th, 2005, 8:37am by mattian » |
IP Logged |
|
|
|
riadov
Newbie
don't get mad. get even
Gender:
Posts: 4
|
|
Re: 100 prisoners & a light bulb
« Reply #328 on: Feb 20th, 2005, 11:47am » |
|
no problem man i must excuse myself ,anyway i am working at the riddle but no progress so far  hope to helpful next time 
|
|
IP Logged |
|
|
|
Worcester
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #329 on: Mar 6th, 2005, 9:29am » |
|
Hi, I've read through this thread, and i don't understand AlexH's process that he describes on page 4, and offers another explanation on page 5 for. Could someone explain it in English, (not in code), to someone with a reasonable, but not Undergraduate, knowledge of mathematics.
Thanks to anybody who does this.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #330 on: Mar 6th, 2005, 3:06pm » |
|
Here is how I interpret AlexH's scheme (a variation of Paul Hammond's).
The prisoners decide in the advance meeting to break the coming days into a repeating set of 7 "stages" (7 stages for any number of prisoners from 65 to 128 - more generally, it needs to be the exponent of the least power of 2 >= the number of prisoners). If stage 7 ends without release, a new repetition of stage 1 starts, and so on. Each stage lasts a number of days decided on at the meeting, so everyone knows when the stages begin and end.
Consider the prisoners to have counts based on "tokens". There are 7 types of tokens (one for each stage), which I will call 1-tokens, 2-tokens, 3-tokens, etc. A prisoner with 2 1-tokens combines them to form a 2-token. 2 2-tokens combine to form a 3-token, etc. Each prisoner is given a single 1-token to start with, except that 28 additional 1-token are given to one or more prisoners so that the total starting 1-tokens is 128 (least power of 2 >= # of prisoners). Those prisoners receiving the extra tokens combine them to form higher order tokens as possible. No prisoner will ever have more than one token of a given type.
On a day of stage k, a prisoner can only turn on the light if he has a k-token. This represents leaving his k-token in the room for someone else to pick up.
A prisoner can pick up the token (i.e., turn off the light) in either of two circumstances: (1) he already has a k-token, in which case he combines the new one with his current to create a (k+1)-token. (If he also already has a (k+1)-token, he combines again to create a (k+2)-token, and so on.) Or (2) it is the last day of the stage, in which case he picks up the token to hold until the next stage k.
Eventually, all the 1-tokens are paired off to create 2-tokens, which are then paired off to create 3-tokens, etc, until finally the two 7-tokens are combined to create a single 8-token. The prisoner doing this announces that everyone has visited the room.
|
| « Last Edit: Mar 6th, 2005, 3:21pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
JayL
Newbie
Posts: 2
|
|
Re: 100 prisoners & a light bulb
« Reply #331 on: Mar 14th, 2005, 10:02pm » |
|
Hi, I believe I have a way of being certain that all 100 prisoners have visited the living room. The one flaw is that it takes a long time which, according to note 1, is fine.
I sincerely hope that no one has posted this solution before.
1. One person is choosen as the leader.
2. The light, which is initially off, is left off until the leader has come into the room for the first time. The leader then turns it on.
3. When someone visits the room they would notice that the light has been turned on.
4. The person then turns the light off and leaves.
5. When others, not including the leader, enter the room they are to leave the light off and not turn it on.
6. Once it is the leader's turn to enter the room again he notes that the light, which he originally turned on, has been turned off.
7. He now knows that 2 people, for sure, have been in the room. Himself and the person who turned the light off.
8. The leader then turns the light back on and leaves.
9. When others, who have not gone into the room before, enter they turn the light, if it is on, off. If the light is already off then they leave it the way it is and pretend that they have not visited the room yet.
10. When the leader comes in he can infer that 3 people have truly been to the room. He turns the light on and leaves.
11. This process continues, until every prisoner, with the exception of the leader has not only visited the room, but has turned the light off.
12. Once the leader sees that the light, that he turned on, has been turned off 99 times he can safety say that everyone have been to the room.
BTW if you have turned the light off before, you obviously don't turn it off again.
Could someone please calculate the average number of days this would take.
|
| « Last Edit: Mar 14th, 2005, 10:17pm by JayL » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: 100 prisoners & a light bulb
« Reply #332 on: Mar 15th, 2005, 12:41am » |
|
Damn! How come we did not think of that?
This, in essence, was proposed in the 11th post on the 1st page. The average time of this solution is 27 years, and was given in the last post of the 1st page.
|
|
IP Logged |
|
|
|
JayL
Newbie
Posts: 2
|
|
Re: 100 prisoners & a light bulb
« Reply #333 on: Mar 15th, 2005, 12:27pm » |
|
Are you allowed to do anything else while in the room. It doesn't really say in the question. For example if you can loosen the light bulb or entirely unscrew it instead of just flicking the light on and off. If you have more options the first, second, ...etc new person, that goes into the room can each do a certain thing untop of w/e was done before. Therefore you can reduce the time by half.
|
|
IP Logged |
|
|
|
riadov
Newbie
don't get mad. get even
Gender:
Posts: 4
|
|
Re: 100 prisoners & a light bulb
« Reply #334 on: Mar 15th, 2005, 12:46pm » |
|
on Mar 15th, 2005, 12:27pm, JayL wrote:| Are you allowed to do anything else while in the room. It doesn't really say in the question. For example if you can loosen the light bulb or entirely unscrew it instead of just flicking the light on and off. If you have more options the first, second, ...etc new person, that goes into the room can each do a certain thing untop of w/e was done before. Therefore you can reduce the time by half. |
|
man i have learned my lesson  when u read well and i mean WELL the replys ,try to find out a solution that no one proposed
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #335 on: Mar 15th, 2005, 12:49pm » |
|
HA HA HA HA !!!!
|
| « Last Edit: Mar 15th, 2005, 12:50pm by mattian » |
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 100 prisoners & a light bulb
« Reply #336 on: Mar 15th, 2005, 2:17pm » |
|
on Mar 6th, 2005, 3:06pm, Icarus wrote:A prisoner can pick up the token (i.e., turn off the light) in either of two circumstances: (1) he already has a k-token, in which case he combines the new one with his current to create a (k+1)-token. (If he also already has a (k+1)-token, he combines again to create a (k+2)-token, and so on.)
|
|
No, a k token and a k+1 token does not make a k+2 token. If a holder of a k+1 token picks a k token, a deadlock is possible.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: 100 prisoners & a light bulb
« Reply #337 on: Mar 15th, 2005, 2:45pm » |
|
One optimization that seems to be missing in the solution where token of 1, 2, 4, 8 etc are combined into a single 128-token: Instead of giving the extra 28 token to one person, spread them to have 1x16, 1x8, 2x4 and 96x1 token.
this reduces down to 100 the number of groups to be combined.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #338 on: Mar 15th, 2005, 3:04pm » |
|
on Mar 15th, 2005, 2:17pm, Leonid Broukhis wrote:
No, a k token and a k+1 token does not make a k+2 token. If a holder of a k+1 token picks a k token, a deadlock is possible.
|
|
But if you already have a k-token and a (k+1)-token, then picking up an additional k-token gives you a (k+2)-token - Icarus specified the condition that one also already have a (k+1)-token.
someone holding a (k+1)-token without a k-token would not pick up a k-token (or would pass it on immediately)
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #339 on: Mar 15th, 2005, 3:48pm » |
|
on Mar 15th, 2005, 2:17pm, Leonid Broukhis wrote:
No, a k token and a k+1 token does not make a k+2 token. If a holder of a k+1 token picks a k token, a deadlock is possible.
|
|
That is not what I was saying. The k-token can only be picked up if the person already has another k-token. He combines the two to create a single (k+1)-token. If he happens to already have another (k+1)-token (either from previous cycle, or because he got some of the spare starting tokens), he combines the newly-minted (k+1)-token with his other (k+1)-token to obtain a (k+2)-token, and so on. As I said earlier in that post, each level token is worth 2 of the level before.'
Each token level represents a binary digit in the person's token count. Whenever he picks up a k-token, he is really picking up 2k-1 1-tokens, and all the rules for combining tokens are just a codification of adding 2k-1 to his token count. I have expressed it in terms of various levels of tokens because I find it conceptually easier to think of the prisoners leaving items for each other in the room, than to talk about transfering this bit vs that bit of one number to another number.
on Mar 15th, 2005, 2:45pm, Grimbal wrote:One optimization that seems to be missing in the solution where token of 1, 2, 4, 8 etc are combined into a single 128-token: Instead of giving the extra 28 token to one person, spread them to have 1x16, 1x8, 2x4 and 96x1 token.
this reduces down to 100 the number of groups to be combined. |
|
I don't quite follow what you are saying here. There are reasons why I identified tokens by level rather than value (mostly for compatibility with other schemes). A 4-token is not 4 tokens, but a single token of level 4. Such a token is worth 24-1 = 8 tokens of level 1.
Since 28 = 16 + 8 + 4 = 24 + 23 + 22, when you give the 28 1-tokens to a prisoner, by the rules he ends up forming these higher tokens immediately anyway. Describing it as giving him 28 1-tokens instead of giving him a 5-token, a 4-token, and a 3-token, is just a convenient short-hand.
I don't see any advantage in giving some of these tokens to other prisoners. By giving them all to one prisoner, if he manages to collect a second 3-token, for example, he can immediately combine it with his initial 3-token, then his 4- & 5-tokens, to create a 6-token. He can do this without having to collect more tokens in the higher level rounds. If the tokens are spread among other prisoners instead, he has to transfer his 4-token, or receive one, before the tokens can be combined. It is token transfers, not token combinations, that require time, so spreading extra tokens out among multiple prisoners increases time instead of decreasing it.
Not long after AlexH proposed the binary method, others (pa0pa0, biwema) proposed variations that attempted what I think you are suggesting, amongst other changes. But these did not lead to any improvement. Mattian appears to have adopted something similar into his scheme as well, but I haven't figured his out well enough to say for sure if it is the same thing. Rezyk, who got the best time out of binary-based scheme, gave his 28 tokens as a lump endowment, just like AlexH did.
I am currently working on a comprehensive survey of the various schemes suggested in this thread, which I hope to post later in the week. (Which is why I was able to tell you this much about the past history). I hope this will re-invigorate the search, at least to the extent of optimizing past proposals (the best so far, due to gypo, is definitely not optimized).
---------------------------------------------
Time flies when you're pontificating, I guess. I wouldn't of thought that I spent 45 minutes or more on this post, but rmsgrey had not responded when I started it!
|
| « Last Edit: Mar 15th, 2005, 6:43pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: 100 prisoners & a light bulb
« Reply #340 on: Mar 16th, 2005, 5:12am » |
|
OK, I will speak of n-groups for a group of n 1-token. I think it is confusing to have a 3-token to have 4 items. 
If you give all extra token to one prisonner, there are 99 to have 1 and one to have 29 token. 29 is 1+4+8+16, that is 4 groups. That makes a total of 103 groups to combine. If instead you give 16, 8, 4, 4, 1, 1, 1, ..., there are exactly 100 groups. You replace four 1-groups by one 4-group.
But it is true it reduces the opportunity of multiple groupings, say if the guy with 29 token receives a group of 4.
|
| « Last Edit: Mar 16th, 2005, 5:13am by Grimbal » |
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #341 on: Mar 16th, 2005, 10:57am » |
|
on Mar 15th, 2005, 2:45pm, Grimbal wrote:One optimization that seems to be missing in the solution where token of 1, 2, 4, 8 etc are combined into a single 128-token: Instead of giving the extra 28 token to one person, spread them to have 1x16, 1x8, 2x4 and 96x1 token.
this reduces down to 100 the number of groups to be combined. |
|
Grimbal,
I did include this optimization in my solution (around page 14). The difference in my solution, however, was that instead of arbitrarily assigning these 1, 2, 4 and 8 values to prisoners, my solution was to assign those values at the beginning of each level in order to minimize the the time it would take for trading to begin in that level. So, for example, the first person in the room in level 4, automatically adds a 4-token to his balance. If he already has a 4-token, then he simply collects the free one and deposits it again in the room.
Icarus has asked me to provide a clearer description of my solution. I will do that later today.
Cheers.
|
|
IP Logged |
|
|
|
raven
Senior Riddler
"Why is a raven like a writing desk?" ~M. Hatter
Gender:
Posts: 560
|
|
Re: 100 prisoners & a light bulb
« Reply #342 on: Mar 16th, 2005, 12:10pm » |
|
After following this thread for some many months, and coming to the two current solutions myself, although my version of the second solution (tokens) does vary a little from the one everyone is going with, I have only been able to come up with one possible variant that could possibly make a difference or impact on the overall release time.
I have read all posts in this thread (no really I have) but it's been a while so maybe this idea has already been tested. My apologies if that is the case.
The variant is to include a wildcard cycle before all other cycles. So everyone who enters the room for the first time leaves the light on until the first repeat visitor, who then turns the light off and everyone from then on, during this cycle, leaves the light off.
The prisoner (I call them 'hooligans' in my world) who collected the wildcard-token, would then be required to "even it out" during subsequent regular rounds/cycles in order to integrate their token into the overall scheme of the rules.
What good is this? It could (???) help reduce the days-per-cycle of all subsequent cycles.
Go to http://www.satarah.com/raven/100.html to view the possible impact of this inclusion. *a small javascript that tests for the first revisit to the room -- refresh the page several times to see what the "range" or variance would be (yes, I could have built in 'auto-running' this test 100 or 1000 times and getting the average, but I'm lazy).
Enjoy, Raven
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: 100 prisoners & a light bulb
« Reply #343 on: Mar 16th, 2005, 1:03pm » |
|
on Mar 16th, 2005, 10:57am, mattian wrote:Grimbal,
I did include this optimization in my solution (around page 14). [...]
If he already has a 4-token, then he simply collects the free one and deposits it again in the room.
|
|
Hehe... I went there and discovered that I already proposed my optimization there. And you already told me the better way to distribute the extra groups.
But of course, it is the other way round. If he has a similar token he will collect it and merge it with his own. If he has not, he should leave it for the next prisonner.
To raven: Yes, I think it was proposed already to start with a "snowball" where everybody passes all tokens to the next one and have the first to re-enter collect all the token from previous prisonners. But you can not let it roll "as long as there is no re-entry". You have to set the length from the start, because someone who enters, say on day 20, won't know if the snowball is still rolling.
So you have to reserve S days for the "snowball". As long as nobody reenters, the light remains on, the first to re-enter (or who enters on day S) collects all the token and swiches off the light. The remaining days (until day S) the light must remain off.
The question then is how to fix S to make the snowball as efficient as possible. If S is too low you miss oportunities for a quick start, if S is too high you risk to waste too much time after the first re-entry.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: 100 prisoners & a light bulb
« Reply #344 on: Mar 16th, 2005, 1:20pm » |
|
on Mar 16th, 2005, 1:03pm, Grimbal wrote:
But of course, it is the other way round. If he has a similar token he will collect it and merge it with his own. If he has not, he should leave it for the next prisonner. |
|
Absolutely right! Sorry - my bad.
|
|
IP Logged |
|
|
|
raven
Senior Riddler
"Why is a raven like a writing desk?" ~M. Hatter
Gender:
Posts: 560
|
|
Re: 100 prisoners & a light bulb
« Reply #345 on: Mar 16th, 2005, 2:15pm » |
|
Grimbal,
I assumed that it would be taken for granted, that it would be a fixed-length cycle.
I'm sure optimization would be a simple thing (says the non-math person here), and the expense in days worth the jump start... If the jump start is enough to warrant this addition at all (which is my real question).
Raven
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 100 prisoners & a light bulb
« Reply #346 on: Mar 16th, 2005, 2:22pm » |
|
on Mar 16th, 2005, 1:03pm, Grimbal wrote:
So you have to reserve S days for the "snowball". As long as nobody reenters, the light remains on, the first to re-enter (or who enters on day S) collects all the token and swiches off the light. The remaining days (until day S) the light must remain off.
The question then is how to fix S to make the snowball as efficient as possible. If S is too low you miss oportunities for a quick start, if S is too high you risk to waste too much time after the first re-entry. |
|
According to my simulations, the average time before the first repeat is 12.2 days, and the max out of several million experiments is 50.
It is possible to have several "snowball" phases. In a subsequent phase, only people who have not seen the light on during the previous phase(s) OR have an odd number of tokens can turn the light on or leave it on. The first person that does not satisfy that condition will collect the tokens accumulated so far and the rest of the phase will be idle. Intuitively, it seems that the second phase can be beneficial, but I have doubts about the third one.
The problem with the snowball phases is that the number of tokens accumulated will most likely have several bits set and therefore no better than several different people holding the respective power-of-2 tokens.
|
|
IP Logged |
|
|
|
raven
Senior Riddler
"Why is a raven like a writing desk?" ~M. Hatter
Gender:
Posts: 560
|
|
Re: 100 prisoners & a light bulb
« Reply #347 on: Mar 16th, 2005, 2:45pm » |
|
on Mar 16th, 2005, 2:22pm, Leonid Broukhis wrote:
The problem with the snowball phases is that the number of tokens accumulated will most likely have several bits set and therefore no better than several different people holding the respective power-of-2 tokens.
|
|
Ahhh, thank you Leonid, that is what I did NOT see about this idea.
Back to the drawing board... it is true I'm still looking for a third -- unique system.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 100 prisoners & a light bulb
« Reply #348 on: Mar 16th, 2005, 3:09pm » |
|
First of all, I'm sorry, but this is not a new idea. Salem first proposed it for the single leader approach (where it shaves about 3 years off the expected run-time according to the one person who quoted a number.
The same approach was suggested by pa0pa0 for the binary approach, but AlexH says that it would save only a few days at best. Still, Rezyk included it in his version of the binary approach, which remains as the 2nd best run-time so far.
The best run-time, due to gypo, uses a variation (an improved version of a scheme by SWF) of this that picks 10 leaders for a [10, 10] 2-stage solution.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: 100 prisoners & a light bulb
« Reply #349 on: Mar 16th, 2005, 3:28pm » |
|
Since Icarus wants to sumarize the available methods, I'd like to write an analysis of this problem.
The first thing to understand is that the problem is not in terms of who switches the light on or off, or how long it remains on. The light is just a private bit of information that one prisonner sends to the next prisonner. One prisonner (the sender) decides to leave the light on or off at the end of the day, regardless of its previous state, and the next prisonner (ther receiver) receives that 1 bit of information. The problem is to make the best use of that little information. Or to make use of it at all.
The next thing to understand is that the meaning of that 1-bit message must be fixed from the start. The sender has no way to know who will receive the message, and the receiver doesn't know who sent it. It could be that the receiver enters the cell for the first time. Assuming there is a well-defined timeline whereby each message can be identified, (as is the case if there is one stay per day), the meaning of each day's message (leaving the light on) can be decided freely, but it must be decided beforehand, and it must be a function of the day only, regardless of the sender or receiver. The only thing that can depend on whatever the prisonner experienced, or even on randomness, is the decision to leave the light on.
One possible meaning for message N would be "prisonner (N mod 100) was here", where prisonners are numbered 0..99. Each prisonner collects and propagates information about all stays he knows about and hopefully someone will reach the point where he knows for sure everybody was there. It is very slow, but it is an example of propagating information.
Many solutions work in terms of tokens. Token are distributed among all prisonners and they try to transfer all token to one prisonner. Obviously it can only happen when each prisonner visited the cell at least once. A message is these solution has meaning: "I am transfering N token to you". The sender can leave the light on only if he has enough token to transfer. If the light is left on, the sender reduces his count and the receiver increases his. N is a predefined function of d, the day number. The differences between the strategies are in the choice of the function N(d), and in how a prisonner on a given day decides to transfer or not that quantity of token.
The "single leader" solution can be expressed in terms of transferring token. The token count is always 1. Everybody gets one token at the starts. Everybody leaves the light on if he has any token to transfer. If a prisonner enters the cell for the first time, he has his own token. If the light is on, he receives one token. He now has two. He transfers one by leaving the light on and keeps one. The first time he enters the cell while the light is off, he can transfer his own token to the next prisonner and return with no token. From there on, whenever he sees the light on, he accepts the token but immediately transfers it further. The leader accepts all token by conting one every time he sees the light on and keeps all token by never leaving the light on. This boils down to the rule where each prisonner switches the light on just once and the leader always turns the light off, counting how many times he does it.
One solution with a "Master counter" and 9 "Assistant counters". There is a first stage (2600 days) where Master and Assistants collect token until they have 10 (they have received 9). In a second stage (2600 days) the Assistants transfer token and the Master counts them. If he receives 9 token in this stage, the wait is over. In this solution, the first stage simply transfers single token, and the second stage transfers tens of token. In the first stage, the common prisonners get rid of their one token if they can (i.e. they did not receive one), in the second stage, the Assistants transfer their 10 tokens if they have 10.
There was an optimization to the "single leader" where the first 20 days or so a "snowball" is rolling. The light remains on as long as the snowball is rolling. The first prisonner to re-enter the cell in that period collects all the token from previous prisonners and becomes the leader. For the remaining of the pre-set period, the light remains off.
In that situation, the function N(d) is (1,2,3,4,5,...,20,1,1,1,...). On the first day, the prisonner surrenders his token to the 2nd. The second adds his token and passes it on. This continues as long as the prisonners are new. As soon as a prisonner re-enters the cell, he has no token to add, so he has not enough tokens to transfer, so he has to keep the tokens and leave the ligt off. This continues until the end of the "snowball" period, where the count returns to 1 and new prisonners have the possibility to transfer single token.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print