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.
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.
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.
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.
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.
Who is they???
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.
> 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.
"They" cannot possibly be referring to the group---"they" is referring to each person individually. If it's referring to the others as a group, it's not a solution to the puzzle.
And yet, you found it understandable.
In contrast, F was really singular.
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?
> consistent
If that was a consistent feature, or better to say regular, there would be the -s inflexion on the verb, that the singular third person requires.
> well-understood
What does that even mean? In the referred article, were, as I said, at least two counts against the particular usage in the GP.
> How would you ...
What does it matter? Are you saying there is no other way? Why don't you give it a try yourself, it's not hard. For starters, just try replacing "they" with "F".
Lol. It does matter because you are bitching about using they when you don't even say what on earth are we supposed to say instead.
Replace they with the name? "If the light is on when Franklin gets to the room, Franklin turns the light off, and Franklin increments his or her counter." Yeah sounds perfectly natural. Pronouns are for losers.
Note that the above sentence is written in the objective way that I mentioned before. There is no way a third person singular gendered pronoun could creep in there, even if I was talking about you in the third person.
Unless Franklin was a transfinite gender fluid with multiple personalities, the use of they would be wrong there, according to the article you linked.
Nice talking to you, thanks for the link.
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?
(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.
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.
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).
So, if you wait a finite amount of time (in this case a "few" billion years") it's possible that the visiting condition might not yet be satisfied.
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.
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.