6 ms·
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. I
by 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 agoThat's way more than one bit of state!
- kd0amg 10y agoSure, but the extra is all local state. It still only uses one bit of shared state.
- rntz 10y agoThis 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 agoUgh. This gives me a headache.
- jon_richards 10y agoI'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.
- thomasahle 10y agoVery nice solution. I wonder if it can be made not rely on randomness at all. The 'standard' solution just required that every prisoner would be taken to the room infinitely many times. As long as this was the case, the warden could try any devious sequence they liked.
- jon_richards 10y agoInteresting question. Haven't solved it yet, but it did give me an idea for an optimization. If the prisoner stores c_max, they can decide to only ever turn off the light (until c=0) if c < c_max - 1. This is because there is at least 1 other prisoner still turning on the light (they could turn off the light they turned on to reach c = c_max - 1, but only get lower if someone else turns on the light for them). Unfortunately an adversarial sequence still hangs progress, as prisoners can be juggled between c_max and c_max-1.
- posterboy 10y ago> If the light is on when F gets to the room, they turn the light off, and they increment their counter. Who is they???
- andrepd 10y agohttps://en.wikipedia.org/wiki/Singular_they https://en.wikipedia.org/wiki/Singular_they
- posterboy 10y agoGood grief. If you want to write objective, do so, and ommit personal pronouns all together, but don't employ this archaic, confusing grammatical quirk. I'd like to point out to you, ekke's comment was much better understandable and shorter. Edit: Did you even read what you linked? > One explanation given for some uses of they referring to a singular antecedent is notional agreement, when the antecedent is seen as semantically plural F was definitely singular. > Distributive constructions apply a single idea to multiple members of a group. They are typically marked in English by words like each, every and any. That is indeed something I often wondered about, sadly that part is inconclusive. > Referential and non-referential anaphors I didn't even try to read. That looks like it should be it's own article. > On the other hand, when the pronoun they was used to refer to known individuals ("referential antecedents, for which the gender was presumably known", e.g my nurse, that truck driver, a runner I knew), reading was slowed when compared with use of a gendered pronoun consistent with the "stereotypic gender" (e.g. he for a specific truck driver). You might ommit personal pronouns, as I said, or use 'it' on the object of the sentence using passive verbs.
- andrepd 10y agoYou seem to be very angry with a feature of English grammar. Using they/them/their is a perfectly reasonable, consistent and well-understood way to refer in the third person to someone of unknown gender. How would you rewrite the sentence "If the light is on when F gets to the room, they turn the light off, and they increment their counter." without using they?
- Tloewald 10y agoWhy does each person need to enter the room twice? F is allowed to turn the light off, each other person can only turn the light on ONCE. Every time F enters and the light is ON he turns it off and increments his counter. When F's count gets to 100 they go free (99 turned it on ONCE and there was at most one false positive) and, obviously, F has entered at least 100 times.
- aiiane 10y agoIf the initial state of the light is known to F then you only need once per person. However if the initial state of the light is unknown to F then your proposal would deadlock at 99 wherever the light starts off, because it will only ever be turned on 99 times, so 100 will never be reached. The twice entry solution avoids this issue because if the light starts on then the most that 98 people will turn it on is 196 times, for a total of 197 "on" count, with 198 guaranteeing 99 people involved, but if the light starts off the 99 people will turn it on 198 times as well.
- deleted 10y ago[deleted]
- Tloewald 10y agoThe 198 solution has the same problem. F cannot tell if the light is on because it was originally on, or G preceded F and the light started off. You're always going to be susceptible to off-by-one errors.