solution, and another problem
solution:
designate one switch the "odd" switch, and one switch the "even" switch. every time a prisoner makes a visit, he toggles the "odd" switch if this is an odd visit for him (1, 3, 5, ...), and the "even" switch if this is an even visit (2, 4, 6, ...).
each prisoner also keeps a running count of even toggles and odd toggles that he observes (not including when he moves the switch himself). that is, if the odd switch has changed positions since his last visit, he concludes that at least one other person has made an odd visit, and increments his odd visit counter. similarly, if the even switch has changed positions since his last visit, he concludes that at least one other person has made an even visit, and increments his even visit counter. also, since the total number of even visits can never exceed the total number of odd visits, each prisoner also adjusts the odd counter to be the same as the even counter if and only if his even counter is higher.
since the difference between odd visits and even visits for a given prisoner can only ever be 0 or 1, then each prisoner merely has to wait until his personal odd counter exceeds his personal even counter by the number of prisoners excluding himself. it may take a long time, and a ton of visits, but this will eventually happen.
a problem related to this one that is more in keeping with the spirit of this board: how many total visits, on average, should we expect for a correct answer given n prisoners?
good luck
cepstrum
|