Light starts off. All prisoners are assigned the number 1.
Days go in a 20 day cycle. Days are numbered 1-20. It starts over day 21.
Days 1-19:
If light is off –
If your number is 0, add the number of the previous day. Leave the light on.
If your number is less than 5, subtract one from your number. Leave light off.
If your number is greater than 5, add the previous day number to your number. Leave light on.
If light is on –
If your number is 0, leave it on.
If your number is less than the day in the cycle, keep your number and leave it on.
If your number is greater than the day in the cycle, subtract the day from your number, turn the light off.
On Day 20:
If light is off: add 20 to your number. Leave light off.
If light is on: keep your number, leave light off.
If your number is greater than 50, always leave the light on and never subtract.
If your number is 100, make your assertion.
In English:
Basically, if you leave the light on you are communicating “all the previous days in the cycle are accounted for.” Likewise, if you leave the light off, you are saying “count me and all the days before me.”
At all time there will be 100 “points” totaled. These points are stored either in the day number or by each prisoner. Initially, 1 point is stored by each prisoner. On day 1, he transfers his point from himself to the day (now day = 1 and prisoner = 0). On day 2, supposedly the same thing happens (day=2, another prisoner = 0). Suppose the first prisoner re-enters the room – he assigns himself the previous day (2) and turns the light on (if light is on, the ‘day’ value is 0, if light is off, the ‘day’ value is the day number.) Hooray! We’ve just transferred a point to another prisoner. The goal is to get one guy all 100 points.
Now let’s jump ahead and suppose that 10 prisoners have 10 points each. On day one of a cycle, some poor sap with 0 will walk in and turn the light on, keeping 0 (day 1 – 1) as his number. On day five, a prisoner with 10 walks in. He turns the light off and subtracts 5 from his number. The next day, another prisoner with 10 walks in and sees the light off, and adds 5 to his number. Hooray! We’re still adding up points!
The PROBLEM is, that this algorithm has a distributing effect on the points. That is, the prisoners without points will outnumber the prisoners with points, and this algorithm will favor distributing the points evenly rather than consolidating them. Since the prisoners don’t know who has how many points, they have to give freely; I have not worked out a solution to this problem. I did add in two “valves” of sorts, at 5 and 50, to favor the consolidation rather than distribution of points. That is, once you reach a critical level of points, there are inhibitions to distributing them.
The other problem is, this will work *eventually*. It will take a really long time, and the prisoners would be better off waiting 5 years and taking their chances. That is statistically more advantageous than waiting for my algorithm to get them out; no one would live long enough. In the end, the guy with 1 point would have to go in on day 1 of the cycle and then Mr. 99 would have to follow (which is a 1 in 10,000 chance every 20 days…200,000 days…) and that’s just after we’ve gotten to that point.
I read some more and will look into the solution of changing the arbitrary count. However, two caveats: 1 - it's just less elegant. In a situation like this, it's obviously practical, but I like to find a single recursive solution. 2 - it get's into practical math. If you are going to change the default count number, you have to be assured that everyone is on board. You have to decide ahead of time when to change the count, so you get into probabilities. You can be pretty sure, but you've left the realm of logical solutions. There's always the possibility that the universe will screw you, so you haven't really solved the riddle. Maybe you've found a way around this... my solution doesn't guarantee a solution, but you ARE guaranteed to know when you have or haven't.
I’m enjoying this; I’ll be thinking. It’s comforting to know that other teams of people haven’t found a good solution either, so I don’t have to feel bad giving up eventually.
Does someone want to put out a normal riddle to keep this going?