Prison synchronization

[•Cosmin]

http://infoarena.ro/blog/prison-synchronization

[•unsilviu]

 @Silviu sounds good but let's not spoil it yet.

[•raduberinde]

Adapting silviu's solution for the unknown initial switch state: each prisoner (except the designated) turns the switch on-to-off the first _two_ times they see it "on". The designated prisoner waits until she has counted 2(P-1)-1 on-to-off transitions and then declares everyone has been in the room. The idea is that if the switch is on in the beginning, whoever goes in first will turn it off, and we have "lost" one in the count. But that's ok, since 2P-3 counts are (in all cases) sufficient for us to know for sure all other P-1 prisoners were in the room at least once.

[•claudiumihail]

Here's my idea for the case where the switch's state is initially known (off):

- The prisoners nominate one prisoner that will declare that all of them have visited the switch room
- Every prisoner except the nominated one follows these rules, when entering the switch room:
       a) If the prisoner has ever turned the switch off-to-on before he leaves the switch unchanged (in whatever state it was when he entered the room)
       b) If the switch is on, the prisoner leaves it unchanged.
       c) If the switch is off and the prisoner has never turned it off-to-on, the he turns it on and leaves.
- When the nominated enters the room he checks if the switch is off. If it is he does nothing and leaves. If it is on he turns it off and leaves. When the nominated prisoner has counted P-1 times that the switch was found in an on state he can declare that all prisoners have been to the switch room.

My idea is that each prisoner only turns the switch on once and only the nominated prisoner can switch it off.Thus the nominated prisoner can always be sure that when he finds the switch in an on state it was turned on by a different prisoner than the others before.

[•Cosmin]

You guys were fast .

[•rgrig]

I remember solving this problem during a pub crawl in Budapest in 2008. While somewhat drunk and with many hints it took me ~1h to solve the first part. Then Michal, who was posing the problem, said "what about if you don't know the inital state of the switch" and I immediately answered "ah, they just do it twice". IIRC, he looked at me a bit puzzled and said, "that's weird, it took me more time to solve the second half than the first."