|
Here's the answer that ive got
As before, the prisoners choose an 'announcer' among them.
Then they agree on the following procedure:
- each prisoner keeps a counter, which is initially 1.
- the bulb has a value assosiated with it, which is
- 0 for night number 0
- 1 for nights number 1... 800
- 2 for nights number 801...1600
- 4 for nights number 1601...2400
- 8 for nights number 2401...4540
- 2 for nights number 4541...5340
- 1 otherwise.
(day 1 shall be the day when the first prisoner enters
the room; the night number n shall be between the days
n and n+1).
- now, when a prisoner enters the room, he does the following:
- check if the bulb burns and add the value of bulb (for the previous
night) to their counter if that's the case.
- if the counter is 100 (this usually only happens for the
'announcer'), announce that every prisoner has been to the
room.
- for days 1..2400, if the binary representation of the counter
contains 1 in the digit corresponding to the value of the
bulb for the next night, switch on the bulb, switch it off otherwise.
- for days 2401 and the following days, if their counter is greater or
equal to the value of the bulb for the next night, switch on
the bulb, and switch it off otherwise.
- the 'announcer' switches the bulb off for days 801 and all following days.
- if the bulb is burning, reduce their counter by the value of the
bulb for the next night.
The idea here is to calculate the sum (which is known from the beginning)
of all the counters of the prisoners to a single prisoner (usually the
'announcer'). The sum
[value of bulb if it's burning] + counters of all prisoners
remains constant throughout the process, and all counters of the
prisoners remain non-negative. This means that if the counter
ever reaches 100 for a prisoner, all other prisoners have to
have been to the living room.
The speedup results from the fact that the chance that after the first
800 days, every prisoner's count is either 0 or 2, and that after the
first 1600 days every prisoner's count is either 0 or 4, and that after
the first 2400 days, every prisoner's count is either 0 or 8 except for
the 'announcer', and that after at most 4540 days, the 'announcer''s
count reaches 100 is pretty high.
Computer simulation of 500,000 runs gives:
average standard min max
deviation
3948.319 628.189 2850 10000
The parameters in the procedure were hand-tuned; so there
is no reason to believe that they're optimal.
Btw, for those who're interested:
A method which requires 4.2 Mio days on average is the following:
- assign each prisoner a number 0..99.
- again, each prisoner keeps a counter which is initially 0 though
(and serves a different purpose than the counter above)
- on each day, the prisoner entering the room does the following:
- let n be the day number, minus 1, modulo 100.
- if the bulb is off and n equals their number, set their counter
to n+1. announce that everyone has been to the room if
their number is 99.
- else, if the bulb is off and n is greater than our counter, set our
counter to n.
- switch on the bulb if our counter is less than or equal to n; switch
it off otherwise.
The problem here is, that to increase the maximum counter by one,
someone who knows the current maximum counter must enter the room
on a day with n=counter-1, and, on the following day, the prisoner
with the number equal to the current maximum counter must enter the
room.
__________________
|