2

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?

Details:

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.

Extra credit:

  • 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.

It may be helpful to write a program to check for possible off-by-one errors and the like. Generators in, for example, Python and JavaScript are your friend.

dram
  • 168
  • 9
  • The answer is at least in these puzzles, and those use more prisoners and less lightbulbs: https://puzzling.stackexchange.com/questions/394/variation-of-100-prisoners-light-problem https://puzzling.stackexchange.com/questions/25038/23-clones-and-two-lightbulbs

    Looking for other dupes.

     – PL457 Jun 01 '18 at 15:44
  • Do we know the initial state of the lights? (Hint: if we do, then one light will be enough for arbitrarily many "users") – Bass Jun 01 '18 at 15:44
  • @Bass: Oh we don't. That's what I forgot to mention, sorry. – dram Jun 01 '18 at 15:46
  • @PL457: the solution to this is a non-probablistic one. 'However, a plan that fails sometimes, even with arbitrary low probability, is not acceptable.' The extra credits are probably fun :). – dram Jun 01 '18 at 15:48
  • @Bass how would one light be enough if you know the initial state? – Nank Jun 01 '18 at 15:52
  • @Nank, that's a good puzzle, isn't it? One of the classics, even, and asked here several times, too, I think. (Also, there is a pretty simple modification that lets you do it with one bulb even if you don't know the initial state.) – Bass Jun 01 '18 at 15:59
  • @PL457 duh, duped. Do you think I can change it into the chatroom variant and un-dupe it? – dram Jun 01 '18 at 16:01
  • I'm slightly confused, is it possible for one person to go in more than once before everyone else has gone in at least once? – Sam Harrington Jun 01 '18 at 16:24
  • @SamHarrington, sure, the order can be almost random, and it’s still doable with one light. (The order cannot be completely random, since then there would be a non-zero chance of someone never visiting the room given any finite time, and no strategy can cope with that.) – Bass Jun 01 '18 at 16:37
  • @dram I suggest asking the "chatroom" variant as a separate question, as it is interesting in its own right. Think carefully about how to word it so the goal is unambiguous. Also, be sure to state that you do not know what the answer is so people don't mistake your question for a challenge puzzle. – Mike Earnest Jun 01 '18 at 17:20
  • @Mike Earnest thanks. I do know what the answer is, though, so I guess yup, challenge. – dram Jun 01 '18 at 23:13

0 Answers0