One day, 10 puzzling.SE users, including you, find yourselves in a horrible prison. Each of you has a deadly collar, presently lethal. It is safe to take off only when all of the 10 collars have been unlocked, or you will all be dead.
A supervisor shows up and tells you about a game that you have to follow to unlock and take off your collars. (As for escaping, that's not important for now.)
For now, you may communicate freely and devise a plan. After the game begins, however, you will each work in isolation.
There is a room with a collar unlocking device and 3 lights with switches. In a random fashion, each of you will be taken into the room. When inside, your collar will unlock, you will be able to see the state of the 3 lights, and you will be able to turn on/off the lights at will.
At some point, one might know that everyone's collar has unlocked, and can take their own off.
Can you devise a plan where everyone can get their collar off surely and safely?
You do not know the state of lights at the beginning.
The 3 lights are your only means of communication, and it's not possible to see them from outside. This basically means only one will be able to receive and send information at a time.
As for unlocking and taking off, you can think it as that you can take off the collar when you're sure everyone has entered the room at least once.
Each person will be taken inside multiple times. You will keep getting taken inside, but the game is considered 'done' when everyone's collar is off.
It is impossible to know, between two entries, whether anyone else has entered, or how many has entered.
'Random' means picking one uniformly randomly each time. However, a plan that fails sometimes, even with arbitrary low probability, is not acceptable. Your goal is to get everyone's collar off in finite entries with probability 1.
Example solution with 2 users and 1 light:
Let's define 'wait until' as 'do nothing in each entry until'.
- User 1: On first entry, get the light off no matter what. Then, wait until seeing the light on. It must be because User 2 turned it on, and it means User 2 has unlocked, so after seeing, turn the light off, and take off collar.
- User 2: Wait until seeing the light off. Then turn it on. Wait until seeing the light off again. It must be User 1 that turned the light off, so take off collar.
- Can you do it with only 2 lights?
- Can you do it with arbitrarily many users and only 2 lights?
- What if you get bored? Can you set up a 'chatroom' with the 3 lights? (A 'hardware bus protocol' that allows sending arbitrarily but finitely long messages in finite time with probability 1.)
- What about a 2-light chatroom?
- I did not come up with this. Do you happen to know the source of the problem? It would be great if someone could tell.