Friday puzzle -- Prisoner puzzle

There goes my morning

Won't be able to concentrate on real work until I figure this one out.

OK. Back to work

Figuring out how to count was not too difficult. Figuring out when to start counting was a little trickier.

In any case, they won't be getting out of jail anytime soon.

Re: OK. Back to work

I'm impressed. I saw no way to solve this one, so had to look at the answer.

We'll leave this one unanswered for a while to see if others want to try, but then we need to compare notes; It sounds like you have a different (but almost certainly equivalent) solution.

Figuring out how to count was not too difficult. Figuring out when to start counting was a little trickier.

Or how high to count in the solution I have seen.

In any case, they won't be getting out of jail anytime soon.

Depends on how often the warden takes one of them to the room, of course. But it is interesting that anyone with a probabilistic sense will conclude that it is almost certain that everyone has been in the room, long before absolute certainty is attained.

Re: OK. Back to work

>> I'm impressed. I saw no way to solve this one, so had to look at the answer.

In many ways, this problem is much like most of my projects: i.e. 'make this vital system work reliably with minimal and sometimes unreliable information'. The main difference is that I knew there must be an answer to this one.

>> Or how high to count in the solution I have seen.

Hmmmm. I hadn't even considered a need to count beyond 23. As you say, we need to compare notes.

>> But it is interesting that anyone with a probabilistic sense will conclude that it is almost certain that everyone has been in the room, long before absolute certainty is attained.

The random starting state and random selection order really compounds the problem. You end up consuming a substantial chunk of your already limited communications bandwidth to overcome it.

A solution

At first glance, this looks like an application for a basic latched event counter, but the combination of random initial state and random selection adds a devious twist. Before we can have prisoners communicate visit events, we first have to communicate to the prisoners that the counter is 'active'. Unlike the visit events which are only communicated once per prisoner, the 'counter is active' information needs to be communicated on a regular basis to make sure that all prisoners eventually see it, regardless of when they are selected for a trip to the switch room.

The "must flip one switch" rule means that we only have one switch available for communication. The second switch is used for when there is no information to communicate, but you still have to flip a switch. In this solution, switch 1 will be used for all communication.

The prisoners elect one prisoner to be the 'Counter'. All of the other prisoners must follow these rules:

* On any visit to the switch room:

IF - you have not touched switch 1 before

AND IF - you have previously seen switch 1 in the OFF position,

AND IF - switch 1 is ON

flip switch 1 OFF.

Otherwise, flip switch 2 (because the Warden says, you have to flip something)

The 'Counter' follows a different set of rules:

* On the first visit to the switch room, make sure that switch 1 is OFF. (If it is already OFF, flip switch 2.)

* On the second visit to the switch room, flip switch 1 to ON and start your count at 1. (if it is already on, somebody screwed up!)

* On the third and subsequent visits:

IF switch 1 is ON, flip it OFF.

IF switch 1 is OFF, flip it to ON. IF you did not turn it OFF the last time you were there, increment your count.

If you are graphically oriented as I am, the state diagrams below may be easier to follow.

With this strategy, each prisoner (other than the counter) should eventually touch switch 1 ONLY ONCE to turn it OFF. After counting himself, the counter counts how many times somebody other than himself turned it OFF. When the count gets to 23, everyone has been to the switch room.

Because of the random selection of prisoners for trips to the switch room, the counter needs to regularly toggle the state of switch 1 to ensure that all prisoners will eventually see at least one OFF to ON transition. This is the 'counter is active' comunication.

In the best possible case, every prisoner will need to visit the switch room at least twice and the counter a minimum of 24 times. The typical case with a random distribution is likely to require many many more visits.

Re: A solution

I can see just one problem with this. The warden only stated that all prisoners would visit the room at least once. It would be possible that he would only take the "counter" to the room one time, in which case they would never get out. He could take all of the prisoners one time, then take the same one every day from then on from the rules as stated.

Good point

The solution assumes a that the warden is using the word 'random' in the statistical sense. Even so, there is a non-zero chance of the solution taking an infinitely long time.

Another solution

Sorry for the delay in getting back -- been out of pocket this weekend.

Bill's solution looks to me to work. And yes, this method is not absolute, but it supplies an solution that is arbitrarily close to 100%, depending on how long you wait. The solution I saw posted for this is equivalent:

Choose a counter.

For everyone except the counter, if switch one is off, and if you have not already turned it on twice, turn #1 on, else flip #2

For the counter, if switch one is on, turn it off, else flip #2.

When the counter has flipped switch one off 44 times, announce that everyone has visited.

If the switch was originally in the off position, it means everyone has visited at least twice when he gets to 44. If the switch was originally on, the 21 of the other prisoners have been in at least twice, while on has been in at least once.

PS

I said, as if a statement of fact, that this method was equivalent to Bill's. That would have been more accurately stated as "it seems to me that this is probably equivalent to Bill's solution". I don't know, but that is my gut feel.

Interesting

I like that solution better. If nothing else, the rules are simpler.

Equivalence

I think it could be proved that they both would complete (assuming a statistical definition of randomness and given an infinite amount of time).

As for efficiency, aside from boundary conditions and pathological cases, they should work out to be about the same.

In my solution, 50% of the communication bandwidth is not available for communicating counting information (the "idle" state in the counter's state diagram). In your solution, all intervals between counter visits are open for communicating counting information - but the effective data rate is halved (because each prisoner needs to report twice.)

In other words, there is twice the opportunity to communicate half as much data.