The Hardest Prisoner Problem Ever (Part 2)
Do not attempt this problem before solving
The Hardest Prisoner Problem (Part 1)
.
This problem is the same as that one but you don't know the starting state of the switch . How much longer does it take before a prisoner knows that all of the other prisoners have been in the room?
Note that you will need to modify your algorithm slightly.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Strategy when initial state of switch is known ---
One Counter strategy--
Appoint one of the prisoners as the Counter. Everyone knows the initial state of switch is "off".
The rule for each prisoner who is not the Counter is this ---
If the switch is in the OFF position and the prisoner has never switched it ON before, then he must flip it ON. He will only do this once. If he has flipped the switch before, he won't do anything.
If the switch is in ON position, he does nothing.
The rule for the Counter is ---
If the switch is OFF, he will do nothing
If the switch is ON, he will switch it OFF and add one to his count.
When the Counter flips switch OFF 5 times, (once for every prisoner other than himself) he knows every prisoner has visited at least once and pushes the button.
Strategy when initial state of switch is unknown --- Problem here is that if the Counter happens to be the first one in the room and the switch was ON, he will switch it OFF and think that someone has been in the room before him. He might then end his count of 5 before the last prisoner has been to the room.
So the modification to the strategy is that every prisoner (except the Counter) will have to flip the switch ON twice. The Counter will know everyone has been in the room once he flips the switch OFF 10 times.