Author |
Topic: 100 prisoners & a light bulb (Read 166662 times) |
|
James Fingas
Uberpuzzler
Gender: 
Posts: 949
|
 |
Re: 100 prisoners & a light bulb
« Reply #200 on: Oct 22nd, 2003, 7:56am » |
|
Here's another possibility that might cut down on the average time (don't know if anyone's investigated it yet). When a person creates the crown, they destroy one token, making 99 total tokens. We could then add up tokens in groups of 3 and 9, or 11 instead of groups of 2, 4, 8, etc.
|
|
 IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: 100 prisoners & a light bulb
« Reply #201 on: Oct 22nd, 2003, 8:26pm » |
|
I still believe that the token/crown family of solutions is for a more restricted problem that guarantees that a person will go to the central room exactly on the day that the prisoners deem "first". Nothing in the rules prevents the warden from starting the procedure the day of the original meeting, or the day after, or the next Monday.
Can the token/crown solution be adapted to the more general rules?
|
|
IP Logged |
|
|
|
gypo
Newbie
Gender:
Posts: 1
|
|
Re: 100 prisoners & a light bulb
« Reply #202 on: Oct 23rd, 2003, 4:29am » |
|
Hi guys,
I believe I have a solution that lets the prisoners out in under 3500 days (mean 3489, st. dev. 664 based on 1,000,000 simulations).
The method is a standard {10,10} with ninety drones, ten counters (who have badges) and a single leader (who has a crown as well as a badge). The improvement on previous methods comes from the opening stage (stage 0), where the counters and the leader are decided. The rest is a standard {10,10}: stage 1, where the counters count up to 10; stage 2, where the leader counts the counters (and announces when he reaches 100); and then infinitely recurring stages 3 (shortened stage 1) and 4 (shortened 2).
As I said above, the improvement comes from a new approach to stage 0. I will describe the algorithm in two steps, first a basic version (which isn't very good but gets the basic idea across) and then an improved version which gets around a key limitation of the simple approach.
So, the basic algorithm. Initially all prisoners have a single token, zero badges and zero crowns. Stage 0 is 40 days long, which is divided into 10 cycles of 4 days each.
* At the start of each cycle the light is always off (see later).
* On day 0 of each cycle, if the prisoner has one or more tokens he turns the light on and subtracts one token from his inventory. If he has no tokens, he leaves the light off and adds a badge to his inventory.
* On days 1 and 2, if the light is off the prisoner does nothing. If the light is on and the prisoner has one or more tokens, he leaves the light on and subtracts one token from his inventory. If the light is on and the prisoner has no tokens, he switches the light off and adds d tokens and a badge to his inventory (where d is 1 on day 1 and 2 on day 2).
* On day 3, if the light is off the prisoner does nothing. If the light is on, the prisoner adds three tokens and a badge to his inventory and turns the light off. (So the light is always off at the start of the next cycle.)
* Whoever gets the badge during the first cycle also gets the crown.
The algorithm was inspired by Salem's leader selection; the idea was to repeat this a few times to get more of the benefit that makes the leader selection process worthwhile.
The main failure of this simple approach is that very often one prisoner ends up with two badges. This means that he has to count up to 20 during stages 1 and 3, which is enough to add about 200 days to the expectation.
I have discovered a neat way of almost completely avoiding this. Among other things, the modification depends on the following insight: if a prisoner has a badge, he is allowed to have a negative number of tokens. This is OK, because the leader counts only what the counters signal to him and can't announce until all counters have signalled (and are therefore no longer in the red).
The algorithm is then modified as follows:
* Initially, all prisoners have one token each, zero badges and zero crowns (same as before).
* On day 0 of each cycle, if the light is on, the prisoner gets a badge and three tokens. If the light is off he gets nothing. If he now has one or more tokens or one or more badge, he turns the light on and subtracts one token from his inventory, even if he ends up with a negative number of tokens. If the prisoner has no tokens and no badges, he switches the light off and gets a badge.
* On days 1 and 2, the prisoner does nothing if the light is off. If the light is on and he has a token or a badge, he leaves the light on and subtracts one token from his inventory. If the light is on but he has no tokens or badges, he turns the light off and adds d tokens and a badge to his inventory.
* On day 3, if the light is off the prisoner does nothing. If the light is on and he doesn't have a badge already, he switches the light off and gets three tokens and a badge. If the light is on and he already has a badge, he leaves the light on and does nothing.
* Whoever gets a badge during cycle 0 also gets a crown.
* On day 1 of stage 1, if the light is on, the prisoner gets a badge and three tokens, switches the light off and pretends it was off to start with.
This opening will result in somewhere between 14 and 25 drones (out of 90) being counted during the first 40 days, which gives you some idea of the power of the method.
I haven't really optimised the stage lengths very thoroughly, but this is what I used to achieve the 3489 days: stage 0: 10 cycles of 4 days; stage 1: 2000 days; stage 2: 1500 days; stage 3: 300 days; stage 4: 300 days.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: 100 prisoners & a light bulb
« Reply #203 on: Oct 23rd, 2003, 9:55am » |
|
on Oct 22nd, 2003, 8:26pm, Leonid Broukhis wrote:| Can the token/crown solution be adapted to the more general rules? |
|
Maybe it can ... you don't know when things will start, but if you set up the stages so they repeated forever, you might be able to make it work. But you still need to know the initial state of the light bulb.
stage 1, stage 2, stage 3, stage 4, stage 1, stage 2, stage 3, stage 4 ...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #204 on: Oct 24th, 2003, 1:49pm » |
|
You don't need to know precisely when day 1 is, provided you know a day after which things will definitely have started. If so, you can agree an arbitrary "day 1"
It's just been pointed out to me that you don't need to know the initial state of the bulb, or the time of day one - the designated counter turns the bulb off at every opportunity; everyone else turns it on twice. When the count reaches 198, then either everyone's been twice, or the bulb started off on, and one person has only been once.
[edit]Re-reading the 2 lightbulbs thread, I noticed this had already been pointed out there too - in fact, starting everyone with two tokens works under the most hostile of possible conditions - where the warden can any prisoner to the room at any time, can set the initial state of the lightbulb to whatever he wants, listens in on the strategy session and wants to see the prisoners dead if possible, or imprisoned for arbitrarily long, but (in order to make any solution possible) has to follow a strategy that sees all prisoners visiting the room an infinite number of times before time omega (least infinite ordinal) if they don't claim before then.[/edit]
Anyway, cycling through states with an unknown start and known initial state has problems because the actual start time changes the value of the intial lit bulb.
[edit] Except that if you know the bulb starts on, you simply invert your system[/edit]
|
| « Last Edit: Oct 27th, 2003, 1:02pm by rmsgrey » |
IP Logged |
|
|
|
aznbrotha
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #205 on: Oct 27th, 2003, 6:11pm » |
|
umm i dunno if its already mentioned but the prisoners could mark tallies only the first time they go in (so the second time they can just sit around). whenever a prisoner that never been in there before sees 99 tallies then he knows that he is the 100th one, but if this was his second or more turn and he sees 100 tallies that means everybody has gone.
....Does it make sense?
|
|
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 #206 on: Oct 27th, 2003, 6:41pm » |
|
aznbrotha, yes in the 9 pages of this thread you can find this idea in various forms mentioned repeatedly.
The quest behind this discussion is what to do when these "outside the box" type answers are not allowed, so you follow the situation described. This is a tricky discussion which has already produced some very interesting ideas.
(One of these days, we are going to have to do as William suggested in creating the headers, and use it list the best solutions, and point out that the discussion is long past the "other solutions". But I was kinda hoping that a moderator more involved in this thread than me would take care of it!  )
|
|
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
|
|
|
halfwind
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #207 on: Nov 13th, 2003, 2:45pm » |
|
Can the prisoners make a mark on the wall? So if he/she has been in the room before, they don't make a mark, but if going in for the first time, he/she makes a mark. After you count 100 such marks, you can be certain that all of them have been in that room.
Now the light bulb. Hmm. Who needs a light bulb, ha! And besides it does not say that the warden cannot or will not turn off the lights if the prisoner leaves it on.
|
|
IP Logged |
|
|
|
Bitter and/or Twisted
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #208 on: Nov 13th, 2003, 6:12pm » |
|
Congratulations, halfwit, you are the 10.000th person to propose that solution. Please accept this "I can't be bothered to read the current page, let alone the whole thread!" T-Shirt, with our compliments.
|
|
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 #209 on: Nov 13th, 2003, 6:35pm » |
|
Bitter and/or Twisted: I would ask that you consider that being rude and insulting lowers other's opinion of you rather than the one you insult.
Halfwind - while I do not condone the behavior of this guy, if you would please read my post that immediately precedes yours, it might help you to understand the frustration we feel when someone keeps suggesting these same things over and over again that do not at all address the particular problem we are considering.
|
|
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
|
|
|
Bitter and/or Twisted
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #210 on: Nov 13th, 2003, 7:11pm » |
|
Sorry, I was only joshing. Apologies to halfwind and any other offendees.
|
|
IP Logged |
|
|
|
GCR1320
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #211 on: Dec 20th, 2003, 11:40am » |
|
Ahhh ummm I'm just looking around and although I didn't read all 9 pages I thought I would throw this one out there.
Each prisoner leaves something in the living room the first time they go (shoe, clothing, tooth, hair, etc.).
Once there are 100 items you know that each prisoner has been in the room.
Once again, this assumed that people can leave things behind, but it is the best thing I can come up with. Because I do not believe the solution lies within probability.
|
|
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 #212 on: Dec 20th, 2003, 11:48am » |
|
Apparently you didn't read much at all, because you can find many variations of this idea posted, some on the first page. The discussion moved long ago from consideration of these ideas to the question of what is the best procedure possible strictly within the parameters stated in the problem.
|
|
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
|
|
|
GCR1320
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #213 on: Dec 20th, 2003, 3:40pm » |
|
Well thanks for being an ass about it.
And no, this was not suggested on the first page of this thread.
|
|
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 #214 on: Dec 21st, 2003, 11:49am » |
|
I'm sorry I offended you. I am only expressing my frustration with seeing that someone has posted to this thread, and checking in to see if they have had any new insight, only to find the same idea, which bypasses the very things that make this problem interesting, posted another time.
You are correct, the first appearence of the this concept (leaving markers in the room) is in reply #44 on the second page (unless I missed an earlier one).
It also occurs in replies #86, #131, #132, #145, #146, #169, #173, #178, #180, #205, #207, and of course your own reply(#211).
I should have been more courteous in pointing this out, though. (In the few posts preceding yours, you will see that I chided someone else for the same fault.) I apologise.
|
|
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
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #215 on: Dec 23rd, 2003, 9:22am » |
|
If you allow marking the wall as a form of leaving a marker (not exactly, but very closely related) then the first appearance is reply #13 - on the first page. Had I gone from memory, I'd have thought of that one as the first appearance.
|
|
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 #216 on: Dec 23rd, 2003, 4:25pm » |
|
It's the same idea (each person leaves something in the room to indicate their presence), so yes, it does count and I was correct in my original statement after all (I missed it because I was scanning rather than reading the posts - there may well be other occurences too). That does not excuse being rude about it though.
Since no one else seems to be interested in doing it, I suppose I ought to summarize the thread like William originally intended with the headers. But it would take more effort than I want to invest right now, particularly since I have never bothered to comprehend the details of the more complicated solutions.
|
|
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
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: 100 prisoners & a light bulb
« Reply #217 on: Dec 23rd, 2003, 6:21pm » |
|
hat this thread needs is to be split into two pieces, or maybe lock it and put links to two new threads each with a summary at the beginning. First thread would go in the Easy section and include alternate intepretations of the question, such as allowing prisoners to check-in on a sign up sheet left in the room (or otherwise leave a mark). Second thread would go in the Hard section and address the intended problem.
For the Hard version, the question should be carefully rephrased. Maybe have a custodian return the room to the same condition each day before the next prisoner visits, except the light is left in the same on/off state. Or have 100 different lightbulb rooms with a common switch, such that each prisoner only ever sees two rooms: his own cell and his own light viewing/switching room.
Icarus, if you are looking for a volunteer to write summaries, I would be willing if given the go ahead, but not if they would just be more posts buried on page 10 of this thread.
|
|
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 #218 on: Dec 23rd, 2003, 11:39pm » |
|
If you're willing to summarize it - I was thinking of a short description of each of the solution methods along with the expected release time - I would be glad to put a link to it in the header, similar to what I did with the 0.999... thread.
I would agree with you above having an easy version - except that I would call it trivial rather than just easy. If you leave open the possibility of prisoners leaving marks, then the solution is obvious, so what is the point in even asking?
|
|
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
|
|
|
snaily
Newbie
Posts: 5
|
|
Re: 100 prisoners & a light bulb
« Reply #219 on: Feb 10th, 2004, 8:29am » |
|
*doubts this will get read or even matter, but here's my 3.282348 cents*
The riddle itself is open-ended and so naturally a lot of people are going to jump right for the tally marks on the wall or break the lightbulb theory. I understand why those are not generally accepted answers to this riddle. The guard brings them into the room and lets them fiddle with the lightbulb/switch/toggle mechanism, then apparently they just go back to their cells. The guard would notice things being tallied or broken or any other obvious attempt and would probably just cover those up (the riddle only says that they can toggle the lightbulb not do anything else, so the guard can just undo whatever else they do). But in order for the riddle to even have an answer we have to accept that the guard doesn't mess with the state of the lightbulb/toggle mechanism, otherwise all solutions wouldn't work. So whatever the prisoners do with their turn at the lightbulb dictates how quickly they can 100% exit prison. Fine ... so my first answer to this problem yielded the result of 2,000 days (or 1,600 depending).
I read through the 9 pages and I like a lot of the answers, however the point is to find an "optimal" solution using only the lightbulb/toggle and nothing else, and with those conditions 2,500+ days is ridiculously high. I am semi-intelligent but when the binary solution started to get into the 4th or 5th page I had trouble not getting dizzy and falling out of my chair. Ultimately, that system, although complex, and requiring extensive knowledge and laser-cunning, somehow works, it's terribly slow.
Now some people have alluded to out-of-the-box solutions and unfortunately none have really typed out the specifics, so the needlessly complex "I have a degree in computers and math and am not afraid to show it" system still stands as "optimum". Hopefully some people will think otherwise after this post.
This riddle involves a light bulb and presumably a switch that turns it off and on. I don't know about the countries these people are from, but in America (and in most places that are of this world) people don't have to screw in and out lightbulbs to turn them on or off ... we have like ... buttons and stuff for that. Now lightbulbs on Earth typically do screw in and out and can typically screw a full turn without showing any outward sign that this has happened. In other words, turn a lightbulb 1 turn in it's socket, balance it, and then walk away. From a distance can you tell that it's not fully tightened ... of course not.
So how many "states" can a lightbulb/switch situation be in?
1) bulb off switch off
2) bulb half turn switch off
3) bulb full turn switch off
4) bulb screwed in tight switch on (light on)
5) bulb turned slightly (like 1/4 or maybe half) switch on (light on)
6) bulb turned full turn switch on (light would be off)
So using 1 as the default position you can do a simple leader scenario. Pick a leader who is able to count. Then tell everyone the order of light bulb progression. Half turn, full turn, screwed in and on, turned slightly and on, switch on but light off. If you enter the room and the light isn't done it's progression then you toggle it. If you toggle then you're done forever, never touch the light or anything again. If it's done it's progression when you enter, then wait til the next time to touch it. When the leader/counter enters the room he can tell whether 1, 2, 3, 4, 5, or 0 new people have been there. Add that number. When it gets to 99 you are free. With an average of 100 visits per time in the room you would need 20 sequences of 5 counts, so 2,000 days. Let's give or take a big margin and say 1,000-3,000 days expected or about 3-8.5 years with just under 6 as the average expected time. Sure beats a decade.
Now if the guard has the ability to fiddle with the bulb and switch then you are all negated. All of the prior solutions fail instantly. He could turn the bulb on or off or do anything, so the riddle is meaningless. If the guard can't touch the bulb or switch directly, which the riddle implies, only the prisoners can, then my method (which I'm sure a few have hinted at in less word) is entirely valid. The guard standing at the door and looking at the bulb will be physically unable to tell if it's semi-turned or not, and all but the last step the switch position matches the light (but you can ignore that one and still get 2,500 days as a total if you wanted).
This solution doesn't exactly think-outside-the-box, it just uses common sense. It was the first solution I thought of and as such it can probably be improved to even less days by someone who knows more about math. I get the feeling that anyone who doesn't use the "binary-math-anal" solution will get told that they are doing it wrong, but it's actually a simple problem if you think about it for a second.
You can either have 100 prisoners all know and understand a computer based language thingy that even I, a somewhat intelligent person didn't even begin to grasp, then have them not only count days (how can they do that? even if they get meals they can't see the sun, so can a human really be expected to know the difference between 12 hours and 8 hours, 2 meals a day or 3 meals a day? i doubt it), but they would also have to wait the decade to accomplish this. I couldn't follow the binary system for 10 seconds much less 10 years.
or ...
You can have 100 prisoners twist a lightbulb either halfway or one full turn, leave the counting up to the smartest guy (the one that has an IQ over 70) and then trust that they will be able to determine given ample time whether or not a lightbulb is in fact twisted or not by ... like twisting it to test.
Since I want to be totally scientific and mathematical, could someone please spend 8 years writing a C++ or other program to determine the statistical probability that a group of 100 people who perfectly understand binary will fail to understand the concept of twisting a lightbulb?
Okay, okay, I apologize for the sarcasm, because I think all answers that fit the riddle are correct ... it's just a matter of whether you want to go a certain route or not. On Willywu's island of death you can either work your butt off and then still burn to death (possibly) or just beat the riddle and die and go to heaven the winner. In the poison drinks one you can either worry about prisoners and algorithms or you can just give the wine in droplets (mixed in water) to farm animals and then you beat the riddle and everyone lives to toast (and the animal that dies can be thrown into a river somewhere). And in this puzzle you can either refuse to touch anything other than the switch going up or down and keep those poor people in jail until they are old men, or you can leave obvious clues and hope the guard just doesn't notice or mind, or you can do it my way and get out fairly quickly without anyone having to be intelligent to do it.
It's all up to how you look at it.
|
|
IP Logged |
|
|
|
godskook
Guest
|
|
Re: 100 prisoners & a light bulb
« Reply #220 on: Feb 10th, 2004, 8:38am » |
|
Since the riddle states explicitly that toggling the bulb is legal, my suggestion is to have a second indicator, i.e. the bulb. The states of the bulb are (Tight, snug, loose, broken). Although this adds to the efficiency of any solution, I should note that these may not be legal.
Tight and loose are legal as they are both easy to tell
snug is suspect because the exact definition may vary among the prisoners.
broken is doubtful because a replacement bulb would be required and that was not given in the problem
this adds to the speed of the solution by changing the numbers the room can hold from (0 to 1) to (0 to either 3,5, or 7) I don't know probability so I can't say how much time is saved by this idea, but I do know it is legal.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 prisoners & a light bulb
« Reply #221 on: Feb 10th, 2004, 9:35am » |
|
There is a solution for 100 days, but the prisoners need to be very dedicated.. Probably members of a cult as well..
All that's needed is that they kill themselves the same day they are led into the room. The last survivor can then go free on day 100. (That's assuming, of course, the guard doesn't feel inclined to drag around dead bodies)
|
| « Last Edit: Feb 10th, 2004, 9:36am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
snaily
Newbie
Posts: 5
|
|
Re: 100 prisoners & a light bulb
« Reply #222 on: Feb 10th, 2004, 10:28am » |
|
Bizarre solutions that maybe we'd be better off if I didn't post (or words to that effect):
The first prisoner could kill the guard and steal his clothes (then maybe have a fashion show ... i mean release the others)
You could devise a really great plan then whisper to one guy, on your 4th trip just say "we've all been here" and cross your fingers, but don't tell anyone I said that
After a person goes to the room have them refuse to go from then on, they can tell the guard, ahh, just pick someone else today, I'm enjoying isolation ... when a person gets taken there like 27 times in a row, they can assume they are the last
They could just spend their lives in a regular jail and not agree to play the game, besides they probably deserve to be in there anyway
They could ask the guard how the Boston Red Sox are doing and when the guard says, "They won the World Series" they'll know that God is once again granting miracles and it's safe to announce they've all been in the room
The walls are soundproof but not smellproof, so when they get taken to the living room they can "fart" in the direction of the last cell on the way and when that guy smells 99 farts they are done
Or they could just tunnel out like in Shawshank Redemption, but they would need big posters and maybe some good rocks to polish
|
|
IP Logged |
|
|
|
EB
Guest
|
|
Re: 100 prisoners & a light bulb (THE ANSWER)
« Reply #223 on: Feb 20th, 2004, 10:37am » |
|
Though i have not read through everyones post. the answer in my mind is quite simple...after 100 days either every prisoner has been to the living room or not. The very first prisoner to enter the room turns the light off (if it isnt already). Everyone that enters the living room for the first time leaves the bulb as it is, without touching the bulb. If a prisoner enters a second time within a 100 day period, they turn it on. If at the end of 100 days the bulb is off, every prisoner has been in the living room only once. If the bulb is on, that means someone has visited twice, thus leaving a prisoner out of the equation...TA DA
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #224 on: Feb 20th, 2004, 4:05pm » |
|
EB: your solution first appears (extended to repeat indefinitely) in the fifth post on the first page.
The current thrust of serious solution effort is going into a scheme based on the idea that a designated counter turns the light off at every opportunity, and everyone else turns the light on the first time they get the chance. The family of schemes has been formalised (by Rezyk) something like: each prisoner starts with an inventory. Each day, the light can carry a set package (varies between days), and the prisoner in the room can generate or discard certain items depending on his current inventory. When the prisoner enters the room each day: 1) if the light is on, he turns it off, and adds the previous day's package to his inventory; 2) he consults his current inventory to determine what items to create/destroy and whether to claim victory; 3) he decides, based on his new inventory, whether to turn the light on; 4) if he turns the light on, he removes the day's package from his inventory.
The current best solution (posted by Gypo) claims an expected time of just under 3500 days (around 9.5 years) and uses an initial 40-day stage to create and assign 10 badges and a crown (everyone starts with a token) before going through alternating stages of a) prisoners with badges try to collect single tokens up to 10 per badge (and those with no badge try to get rid of them) and b) the prisoner with a crown tries to collect tokens in 10s (each batch of 10 accompanied by a badge), while any prisoner with a badge and no crown tries to pass 10 tokens and a badge. The assignment of badges and crown works by generating a badge every four days (along with a crown the first day), and passing the badge and n(mod 4) tokens on day n until the day before the next badge is generated, or someone can't pass the required number of tokens - at which point, if the person didn't have a badge before, he keeps the badge and associated tokens, otherwise he passes the spare badge and the required number of tokens, generating token - antitoken pairs to make up the number (antitokens mutually annihilate with tokens given the chance - and they must get the chance in order for the prisoner's previous badge(s) to get passed). On the day the new badge gets created, if the previous badge is still unassigned, it and its tokens get picked up by that day's prisoner regardless of what he had previously. At least, I think that's how it's supposed to work... The subsequent stages were run for 2000 and 1500 days respectively the first time around, and then for 300 days each to try and pick up the stragglers. There is probably room for improvement there, if not in the initial badge/crown assignment process.
Other serious suggestions (that I can recall) are:
Each prisoner is assigned a day number (mod 100) and you leave/turn the light on on day n when you know that prisoner n has been in at some point. Sooner or later, someone will have found the light on on every day (mod 100) (except possibly the day following his own number) and know that everyone has been in. Refining this to assigning various sets of prisoners to various days and asserting that the entire set has been in has been proposed but not explored in much detail.
A generalisation that catches both the above and the token counting methods (but hasn't been suggested) is that of assigning a subset of the prisoners and a threshhold value to each day. If you know that at least as many of the day's subset as the day's threshhold value have been in, then turn/leave the light on, otherwise, turn/leave it off. By setting the threshhold to the size of the subset, you have the immediately above method; setting the subset to all 100 prisoners throughout gives the token counting method. The immediate drawback with a true hybrid method is that it becomes much harder to make explicit what each prisoner knows.
Finally, for completeness: run in cycles of 100 days, starting each cycle with the light on. Any prisoner who enters twice in a given cycle ensures the light is off when he leaves. If the light is on at the end of a cycle, then release is claimed. A trivial improvement is to start each new cycle on the last day of the previous cycle - using 100 day cycles, the bulb is meaningless to whoever goes in on day 101 - he already knows they failed, but it still doesn't come close to the naive token collecting method. Using this method for one cycle has been suggested as a means of dynamically assigning a counter for the token counting method, but it quickly became apparent that, although this uniquely offers a 100 day best case release time, it has a probability of working out to the best case less than one time in 1060 - to a very rough lower bound. Using a shorter selection period (first person in twice turns the light off and gets d tokens - at the end of the period, if the light's still on, the last person in accepts the n tokens accumulated) of around 30 days gives a shorter expected time, but still loses out to the various multi-stage methods. It might be worth taking the less than 100 day performance hit to try that, and then start a more conventional token collecting method, modified slightly to account for some tokens already being accumulated, on day 100, but that's a matter of collective preference for the prisoners, and if they were in a mood to gamble, then the optimum strategy is probably to wait 2 years then claim regardless...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print