Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

It should be 43 instead of 44, right?


No, then he could have only counted 21 prisoners (43 = 1 initial + 21 * 2). The system will "stabilize" at either 44 or 45 "offs", depending on the initial state.


The answer explains this. The number should be (p - 1) x 2 where p is the number of prisoners. (23-1) = 22 * 2 = 44


But would it not be sufficient to count p?

If switch A starts out in the ON position it would equal one 'fake' prisoner. If the counter just counts one extra (which equals p - 1 (himself) + 1 (fake prisoner) = p) it should be enough, no?


The issue is that the counter doesn't know the state of the first switch at the start. If it's on at the start, then sure your solution will work. But if it's off at the start and they all agree to only flip on the switch once, then the counter will sit around forever waiting for p flips, when only p - 1 will ever happen. They need a solution that will work no matter what state the switch is in at the start.




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

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

Search: