Keith Devens .com

Hi All,

i have made a layman explainations for the 3 solutions. I also made an improvement to solution 2.

{{Solution 1}}

=============

I give u another analogy.

Let's take away the light bulb.

Let 100 men all have IC card or even a piece of white paper. Let there be a collector (counter).

For the collector, he has his own IC.

For the rest, they step into the room, if the room is empty, he leave his IC there. Once he had done so, his role is done. If he is lead to the room again after submitting the IC to the room, he do nothing, his role is over. If the room is not empty (some1 left his IC there), he does nothing, till he gets a chance to "submit" his IC. The collector (if he is choosen) is incharge of collecting the Ics everytime he steps into the room.

That way, upon collecting every1's IC, he would confirm every1 had been there at least 1.

That's for the 1st solution. The only issue is that the probability of getting choosen for the collector is 1/100. That means, he might get selected ~3x per year on the worst case. If the extreme case happen, that will take him 100/3 = 33.3 years to collect everyone's IC. That's how I estimated the time for the probability.

{{Solution 2}}

=============

the 1st guy who enter the room 2x will switch in the bulb that indicates that the game is only between (100 - n) persons, as he is the nth person. The 1st few person (< 100) who has not seen the light on will auto know that they will not touch the light bulb anymore.

The prisoners after him (< 100 days) who all seen the light ON, will turn on the light as accordingly to indicate their presence after that 100 days.

Eg. An extreme eg.

On 97th day, the prisoner who enter the room, discover that the light is OFF, ie. He is the 1st person who enter the room 2x. Hence, 97 person had enter the room. Now he switch on the bulb, the rest of the 3 person who sees the light/ never been to the room within that 100 days, knows that they have to be accounted.

On the 100th day, if the person who enter the room is there > 1, should switch off the light. The collector when return to the room will know that at least 0 person have been "notified" (eg. Worst case, the person who entered the room has enter before the 97 days). After the 100 days, the prisoners who had not entered the room will switch the light ON. The collector will need only 3 counts this round.

But this heightened the possibilities, as less pple need to play the game now, though the number of pple getting randomly invited to that room is still the same. [principle : The key thing is to lessen the pple playing with the switch, note that the light bulb is the channel for 2 pple to communicate. Lower the queue of pple reaching out to the counter (collector), lowers the traffic of communication, lessen the obstruction of communication. ]

<Improvement to Solution 2 for prisoners' riddle>

Instead of getting the 1st guy who enter the room 2x to be the counter, the guy on the next day should be the counter.

The reason is becos if the next guy happens to be 1st entering the room, we can eliminate n person from the game, instead of (n-1) person. In this case, the job of the counter from solution 2 is passed on to the person on the next day (n + 1)th day. Though there is no difference, if the person had been there > 1x too, but the possibility of this improvement will not obstruct the communication of the n pple who have not been to the room yet.

{{Solution 3}}

=============

Solution 3 is a 3-layer tree of hierarchy.

There's 1 master counter, and some sub-counters, followed by "drones" (pple who juz get counted).

The cycle of count is divided by 2 stage:
[1] Sub-counters accounting the drones.
[2] Master counter accounting the sub-counters.

The cycle repeats until the master counter accounts the sub-counters fully.

Eg. The master counter divides the hierachy by his 9 subcounter accounting for 90 drones (ie. 1 subleader to 10 men -> that adds up to 99 men + himself = 100 ).

Then he designates 2 cyclical time frames [let's name them timeframe A and B].

1st 2 years (365 days x 2)[timeframe A]: the subleaders will enter the room and start switching off the light bulb, which the drones turn on when they get a chance to when they enter the room.

The 3rd year[timeframe B]: the subleaders who had switch OFF 10x have the right to turn the lamp ON. The master will switch OFF and acknowledge he accounted for 11 men (for everytime he switched it off).

The cycle repeats until the master counter accounts for 9x of the bulb switching ON during his year [time B].

This is also a way to breakdown and minimise com-traffic collision when pple are trying to communicate using the binary light bulb communication.

the improvement on solution 2 is not correct, because if the new counter keeps the light on, another person after him can also think he is the counter. Would he turn the light off then there will be someone who enters the room for the second time and puts on the light and the one after him also think that he is the counter. So you probably end up with more than 1 counter and they will never reach anyone the count of 100.

There is a problem with solution #3 as well.

Due to the random nature of the problem, any solution that relies on a timeframe is inherently flawed, because the same person could be repeatedly randomly picked over and over for the entire timeframe.

Using solution #3, it is possible for only 10 people to have been in the room before the master counter declares that all have been in: a cycle of the same 9 drones and the master counter enter the room over and over again. Eventually, the master counter will have counted all those 9, and thinking that they were the sub-counters, declare everyone had been in the room.

Solution 3 does work. During period #1 (say 500 days), only drones turn on the light and only sub-counters turn it off. When a subcounter gets to ten, he stops counting and will no longer turn off the light. During period #2 (again say 500 days), only sub-counters turn on the light (and only if they have counted ten drones). In this period only the mastercounter can turn off the light. When he counts nine, he calls the warden. If he has not reached nine on day 1000, a new cycle #1 will start on day 1001.

Here is my Solution. I used MS Excel. You must enable macros for it to work.

http://tinyurl.com/2smwyy

Enjoy,
Dan