8 ms·

Ah, I love these kind of puzzles! Here's another one, similiar to the first one (Names in Boxes). Apologies for any incorrections in advance. There are 100 pr

by iliis 10y ago

Ah, I love these kind of puzzles! Here's another one, similiar to the first one (Names in Boxes). Apologies for any incorrections in advance. There are 100 prisoners. At random times one prisoner is chosen uniformly at random and led into a room with a single lamp. The prisoner can choose to switch it on or off or leave it as the last visiting prisoner left it. Apart from the state of the lamp he must leave the room unchanged. After visiting the room, each prisoner is asked if every prisoner has visited the room by now. If he answers 'Yes' and indeed everyone has been to the room at least once, then everybody is freed immediately. Otherwise they are all executed ;) He can answer 'I don't know' without any consequences. Apart from the lamp being on or off the prisoners have no way of communication at all, but of course as is customary in such puzzles they can plot a strategy in advance and everybody is a perfect logician. So, to clarify: The goal is for one prisoner to be 100% sure that everybody has been to the room at least once. The "easiest" solution would simply be to wait a few billion years (it's an abstract puzzle, they are all immortal anyways ;). But of course there is a more elegant solution that terminates earlier. Also, as the time for a visit is chosen at random a prisoner has no way of knowing who the previous person in the room was. It might just as well have been himself! As there is some randomness involved, it is theoretically possible that the goal state never happens. Just assume that in the limit everybody will have visited the room infinitely often ;) In other words: Implement synchronization between 100 threads with only one bit of shared memory and completely random scheduling.

dsugarman 10y ago
>The "easiest" solution would simply be to wait a few billion years Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. Of course the probability will get higher and higher that everyone was in the room once if it was completely random but that probability will never be 100%. I know of two legitimate answers to this problem, it took me awhile when I first heard it.
- SilasX 10y ago
  >Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. IIRC, in the original statement of the problem, there's also a stipulation that, for all prisoners, the king/chooser/whatever will visit them an infinite number of times (so at any time it must be true that each prisoner will be visited [again or for the first time] if the game doesn't terminate).
  - thaumasiotes 10y ago
    So? It doesn't have to be true that each prisoner will be visited within any particular time frame.
    - SilasX 10y ago
      The solution only requires that they will eventually be visited; you can keep deferring until they are. There's no specific time frame in which you have to make a guess.
      - thaumasiotes 10y ago
        > There's no specific time frame in which you have to make a guess This is correct. > The solution only requires that they will eventually be visited; you can keep deferring until they are. This is false; you can't "keep deferring until everyone is visited" because you have no way of assessing whether that's happened. As a strategy, it is impossible to implement.
        SilasX 10y ago
        Yes, you can: the designated prisoner waits until the signal has been fipped n+k times where n is the number of prisoners and k is the number of times the guard can intervene. All other prisoners flip it to that state if it isn't already. See the other replies.
        thaumasiotes 10y ago
- iliis 10y ago
  True. I alluded to that further down, as even with the perfect strategy this means that "it is theoretically possible that the goal state never happens", i.e. the probability that the algorithm will terminate will never be 100% (but it terminates with probability 1).
ekke 10y ago
Good one! A naive strategy where they never die, and hopefully stay in prison for slightly less than a few billion years: One prisoner is the light-counter (Mr C). Others follow a simple pattern - if the light is off, and they have never turned it on yet, turn it on. If it is already on, or they have already ever turned it on, do nothing. Mr C enters the room, if the light is on, remembers it, and turns it off. When Mr C has entered the room 99 times with light on, he can say 'Yes' and they are safe. This can be optimized. How?
- evanb 10y ago
  You have to be careful, because if the light starts out on, Mr C could be fooled when only 98 other people have entered the room.
- greendude29 10y ago
  This is essentially the same solution I came up with. I'm not sure it needs to be optimized assuming we can set the starting state and the strategy for every prisoner.
evanb 10y ago
Let F be the only person who is permitted to turn the light oFF. The N be every body else---they will be turning the lights oN. F starts with a counter at 0. If the light is on when F gets to the room, they turn the light off, and they increment their counter. If the light is off when F gets to the room, do nothing. Each N starts with a counter at 2. When any N enters the room, if the light is on, do nothing, but if their counter is more than 0 and the light is off, turn it on and decrement their counter. If the light starts on, F will turn it off once, putting their counter at 1. Then, if their counter gets to 198 = 1 + 197, they will know all 99 N people has been in the room once, (and will be certain all but one have been twice). If the light starts off, some N will turn it on. F's counter gets to 198 when everybody else has been in the room at least twice. If any prisoner is queried, they should answer "I don't know" unless they are F and their counter is at 198.
- TylerE 10y ago
  That's way more than one bit of state!
  - kd0amg 10y ago
    Sure, but the extra is all local state. It still only uses one bit of shared state.
- rntz 10y ago
  This is indeed the standard solution. There is also a more difficult version: Every prisoner is required to have the same strategy (so you cannot pick a unique person F). (Every thread runs the same program, and threads do not have access to a unique thread identifier.)
  - evanb 10y ago
    Ugh. This gives me a headache.
  - jon_richards 10y ago
    I'll just solve this assuming the light starts off, because otherwise I have a feeling it will get miserable to think through. Every prisoner starts at c=1. If light is on, turn it off and decrement c. If the light is off, turn it on and increment c. It c hits 0, always do nothing. If c=101, everyone has been to the room. Everyone wants to turn off 1 more light than they turn on, but that means one person has to turn on the light 99 more times than they turn it off (and then they have to see it off, indicating the 99th person has reached c=0, and turn it on for themself to reach c=101). Edit: Thinking back through, I think just starting at c=2 and waiting for c=200 works for an uncertain initial state of the light. Edit 2: One of the problems with this method is that you are essentially waiting for the nature of random distributions to select people unevenly to get people to hit c=0 and be "removed". At higher average c (excluding 0s), this may take a while. It can probably be made faster by having a chance to not turn on the light at low c and not turn off the light at high c, but I wouldn't be surprised if that doesn't actually end up being faster. At the very minimum a prisoner could stop lowering c once it got above the 50% mark.
justinpombrio 10y ago
Here's a much harder variation. There are three changes: (1) No prisoner is distinguishable from any other. In other words, they must all have the same strategy. (2) The prisoners are all given coins, so that they can make random decisions. (3) The goal is now to find a strategy that will eventually halt with probability 1 (in other words, how long it takes can depend on the coin flips, but any run that takes infinite time must happen only with probability 0). However, the prisoners are not allowed to take chances when answering "yes"; they can only say "yes" if they are certain that every prisoner has visited the room. It has a very elegant solution.

by iliis 10y ago

dsugarman 10y ago

>The "easiest" solution would simply be to wait a few billion years Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. Of course the probability will get higher and higher that everyone was in the room once if it was completely random but that probability will never be 100%. I know of two legitimate answers to this problem, it took me awhile when I first heard it.

SilasX 10y ago
>Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. IIRC, in the original statement of the problem, there's also a stipulation that, for all prisoners, the king/chooser/whatever will visit them an infinite number of times (so at any time it must be true that each prisoner will be visited [again or for the first time] if the game doesn't terminate).
- thaumasiotes 10y ago
  So? It doesn't have to be true that each prisoner will be visited within any particular time frame.
  - SilasX 10y ago
    The solution only requires that they will eventually be visited; you can keep deferring until they are. There's no specific time frame in which you have to make a guess.
    - thaumasiotes 10y ago
      > There's no specific time frame in which you have to make a guess This is correct. > The solution only requires that they will eventually be visited; you can keep deferring until they are. This is false; you can't "keep deferring until everyone is visited" because you have no way of assessing whether that's happened. As a strategy, it is impossible to implement.
      - SilasX 10y ago
        Yes, you can: the designated prisoner waits until the signal has been fipped n+k times where n is the number of prisoners and k is the number of times the guard can intervene. All other prisoners flip it to that state if it isn't already. See the other replies.
        thaumasiotes 10y ago
iliis 10y ago
True. I alluded to that further down, as even with the perfect strategy this means that "it is theoretically possible that the goal state never happens", i.e. the probability that the algorithm will terminate will never be 100% (but it terminates with probability 1).

ekke 10y ago

Good one! A naive strategy where they never die, and hopefully stay in prison for slightly less than a few billion years: One prisoner is the light-counter (Mr C). Others follow a simple pattern - if the light is off, and they have never turned it on yet, turn it on. If it is already on, or they have already ever turned it on, do nothing. Mr C enters the room, if the light is on, remembers it, and turns it off. When Mr C has entered the room 99 times with light on, he can say 'Yes' and they are safe. This can be optimized. How?

evanb 10y ago
You have to be careful, because if the light starts out on, Mr C could be fooled when only 98 other people have entered the room.
greendude29 10y ago
This is essentially the same solution I came up with. I'm not sure it needs to be optimized assuming we can set the starting state and the strategy for every prisoner.

evanb 10y ago

Let F be the only person who is permitted to turn the light oFF. The N be every body else---they will be turning the lights oN. F starts with a counter at 0. If the light is on when F gets to the room, they turn the light off, and they increment their counter. If the light is off when F gets to the room, do nothing. Each N starts with a counter at 2. When any N enters the room, if the light is on, do nothing, but if their counter is more than 0 and the light is off, turn it on and decrement their counter. If the light starts on, F will turn it off once, putting their counter at 1. Then, if their counter gets to 198 = 1 + 197, they will know all 99 N people has been in the room once, (and will be certain all but one have been twice). If the light starts off, some N will turn it on. F's counter gets to 198 when everybody else has been in the room at least twice. If any prisoner is queried, they should answer "I don't know" unless they are F and their counter is at 198.

TylerE 10y ago
That's way more than one bit of state!
- kd0amg 10y ago
  Sure, but the extra is all local state. It still only uses one bit of shared state.
rntz 10y ago
This is indeed the standard solution. There is also a more difficult version: Every prisoner is required to have the same strategy (so you cannot pick a unique person F). (Every thread runs the same program, and threads do not have access to a unique thread identifier.)
- evanb 10y ago
  Ugh. This gives me a headache.
- jon_richards 10y ago
  I'll just solve this assuming the light starts off, because otherwise I have a feeling it will get miserable to think through. Every prisoner starts at c=1. If light is on, turn it off and decrement c. If the light is off, turn it on and increment c. It c hits 0, always do nothing. If c=101, everyone has been to the room. Everyone wants to turn off 1 more light than they turn on, but that means one person has to turn on the light 99 more times than they turn it off (and then they have to see it off, indicating the 99th person has reached c=0, and turn it on for themself to reach c=101). Edit: Thinking back through, I think just starting at c=2 and waiting for c=200 works for an uncertain initial state of the light. Edit 2: One of the problems with this method is that you are essentially waiting for the nature of random distributions to select people unevenly to get people to hit c=0 and be "removed". At higher average c (excluding 0s), this may take a while. It can probably be made faster by having a chance to not turn on the light at low c and not turn off the light at high c, but I wouldn't be surprised if that doesn't actually end up being faster. At the very minimum a prisoner could stop lowering c once it got above the 50% mark.

justinpombrio 10y ago

Here's a much harder variation. There are three changes: (1) No prisoner is distinguishable from any other. In other words, they must all have the same strategy. (2) The prisoners are all given coins, so that they can make random decisions. (3) The goal is now to find a strategy that will eventually halt with probability 1 (in other words, how long it takes can depend on the coin flips, but any run that takes infinite time must happen only with probability 0). However, the prisoners are not allowed to take chances when answering "yes"; they can only say "yes" if they are certain that every prisoner has visited the room. It has a very elegant solution.