Hacker News new | past | comments | ask | show | jobs | submit login

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



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


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




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: