Trivia

Subject:
Deterministic solution

Alex Y
Pick one prisoner as the counter. We'll choose #1.

#1's job is to turn on the light if it is off, and count how many times he has to turn on the light.

Every other prisoner is to turn off the light the first time they enter the room and see that the light is on. if the light is off, or if he has turned off the light on a previous turn, he does not use the switch.

Each time #1 turns on the light, he is counting one distinct prisoner who has turned off the light (except the first time, when he is counting himself). So once he has turned on the light 100 times, he knows all the prisoners have been into the room.

The practical problem, which makes David's solution far more attractive, is that #1 will be chosen on average every 100 tries, and #1 needs to be chosen 100 times, and some of those times the light will still be on. So he has to be chosen more than 100 times before he turns on the light 100 times. That means at least 10,000 tries, and with some tries not needing to turn on the light, that would probably be 30+ years, during which surely some prisoner would take to his grave the information about whether he had turned off the light. Even with 15 minute intervals, that would be 3+ months. I'd be more than willing to take at 0.0003% chance on David's solution after 3 weeks.

© 1998 - 2017 by Ellis Walentine. All rights reserved.
No parts of this web site may be reproduced in any form or by
any means without the written permission of the publisher.

WOODCENTRAL, P.O. BOX 493, SPRINGTOWN, PA 18081