The New Sudoku Players' Forum

[udosuk]

The warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.

"In the prison is a switch room, which contains two light switches labeled 1 and 2, each of which can be in either up or the down position. I am not telling you their present positions. The switches are not connected to anything.

"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none either. Then he'll be led back to his cell.

"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.

"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'We have all visited the switch room.' and be 100% sure.

"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators. You will be carefully monitored, and any attempt to break any of these rules will result in instant death to all of you"

What is the strategy they come up with so that they can be free?

[RW]

This is complicated and would take a long time, but it works:

Bob, a murderer with a lightbulb-tattoo on his left shoulder, appoints himself the "switchmaster". As the switchmaster he is the only person who is allowed to set switch number 2 to 'off'-position. The other prisoners are allowed to set switch number two to 'on'-position once each. If they have already done that, or the switch is already in on-position, they must only touch switch number 1. "If you fail to follow these instruction I'll [RW: I shall not write down this part, pappocom would probably ban me from this forum for writing such obscure things]!!!", says Bob with a face that clearly indicates that he isn't joking.

When Bob enters the room, if number 2 is 'on' he sets it to 'off', otherwise he adjusts switch number 1. Before Bob became a murderer he did attend a few years of public school, so he is familiar with the basic maths of counting to 23. When he has set switch 2 to 'off' 23 times he can be sure that everybody has been in the room already (the switch could have been 'on' initially + the 22 other inmates). He then tells the warden that they have all been there, they are all released and get really really drunk! What happens then would easily make a great Bulwer-Lytton-candidate novel!

RW

[emm]

These prisoners all had small sharp blades, which they secreted somewhere in their lower torsos, and used them to make a notch on the wall when they first went to use the switch and so could tell when they all had.

Don’t ban me for obscurity
I’m being vague deliberately
Avoiding a salacity
That somebody won’t want to see
‘Cos if I make obscenities
I get the Sword of Damocles

[udosuk]

This is complicated and would take a long time, but it works...

Michael, who deliberately got himself into the prison to rescue his wrongfully accused brother, was the first one to be lead to the room, with switch number 2 initially in the off-position... Having other plans in mind, he gladly complied with Bob's scheme and flipped that switch on and vowed to never touch it again. Bob was the 2nd one to be brought in. Seeing switch 2 in an 'on'-position, he gladly set it back to 'off' and counted 'one'...

2 months had passed, and everyone of the 23 prisoners were brought in at least once... Other than Bob & Michael, all remaining 21 (including Michael's brother Lincoln) had flipped switch 2 'on' once, with Bob going in between every visit by them, thus he had flipped switch 2 'off' 21 more times (so he counted 22 in total)... And he's eagerly looking forward to the 23rd occasion which would mean freedom for all...

However, all 23 prisoners would in fact never touch switch 2 again, so the 23rd switching would never come, and all of them were doomed to stay rotten in the cells forever... That's unless Michael and Lincoln could pull off their prison breaking plan...

Anyone else got a better plan than Bob the switchmaster? ( - the tattoo on Bob's left shoulder?)

PS: As for emm's answer, let's just say that particular prison is famous for their thorough body cavity search...

[MCC]

Ingenious as RW's plan is, there are so many things that could go wrong, and that's besides human nature. Bob's threats will come to naught since they are all in isolation and it will only take one prisoner to take umbrage at Bob's remakes to diliberately turn #2 switch off two or more times. So when Bob announces that they have all visited the switch room once he'll be wrong and thrown to the alligators.

I think that the switches are a red herring and the answer lies in probabilities.

"But, given enough time, everyone will eventually visit the switch room as many times as everyone else.

What is the probability of 23 prisoners visiting the switch room at least once given the randomness of each prisoner's visit

Senario:
What if 22 prisoners are each taken to the switch room x times over a given period and a single prisoner never visits the switch room at all, but so as to make sure each prisoner visits the switch room the same number of times, the last x visits are by the single prisoner only.
How can we ever be sure that the single prisoner has ever started his visits We can't, so it looks like all the prisoners will never be released.


MCC

[udosuk]

Ingenious as RW's plan is, there are so many things that could go wrong, and that's besides human nature. Bob's threats will come to naught since they are all in isolation and it will only take one prisoner to take umbrage at Bob's remakes to diliberately turn #2 switch off two or more times. So when Bob announces that they have all visited the switch room once he'll be wrong and thrown to the alligators.

If Bob is wrong then all prisoners will get thrown to the alligators, so they better listen to Bob and cooperate... (Let's assume none of them wants to die...) We should also assume all prisoners are intellectual criminals who act with a perfectly logical mind... (Like that's ever gonna be true in reality...)

I think that the switches are a red herring and the answer lies in probabilities.

The switches play an important part in the solution (as it's the only legal way the prisoners "communicate" with each other)... The probabilies affect how long the prisoners need to make the decision, but the puzzle just requires a plan that allows someone among the prisoners to know that all of them have visited the room if that indeed happens... It could be like 10, 20 years later... But RW's plan doesn't work because in case of the scenario I stated above then all of them are doomed to stay in prison forever because everyone has visited the room but they have no way to know that...

"But, given enough time, everyone will eventually visit the switch room as many times as everyone else.

What is the probability of 23 prisoners visiting the switch room at least once given the randomness of each prisoner's visit

Senario:
What if 22 prisoners are each taken to the switch room x times over a given period and a single prisoner never visits the switch room at all, but so as to make sure each prisoner visits the switch room the same number of times, the last x visits are by the single prisoner only.
How can we ever be sure that the single prisoner has ever started his visits We can't, so it looks like all the prisoners will never be released.

Once the last x visits are made by the last (23rd) prisoner, the warden is obliged to bring everyone in again... In that case Bob the switchmaster would visit the room again and gets his chance to assess the situation and decides to make the claim or not...

I should mention that drastic events like a prisoner dies (or escapes from the prison), or a missile or nuclear bomb hits the place and annihilate everybody should be ignored... Let's assume everyone in the story will live forever (with the new technology told by emm)...

[udosuk]

But, given enough time, everyone will eventually visit the switch room as many times as everyone else.

This is just a general conclusion from the random selection of the prisoners to the switch room... You can all just assume the warden has a pack of the cards with the name of the 23 prisoners and just draw one every time to determine which one be brought to the room...

The probability that one of them doesn't get to room in the first 100 times
= (1-1/23)^100 = 1/85 (approx.)

The probability that one of them doesn't get to room in the first 1000 times
= (1-1/23)^1000 = 1/(2x10^19) (approx.)

An analogy is to throw a fair dice... For the first 20 times it's possible to have 10 occurences of 4s and no occurences of 1s... But if you throw it 6000 times then it's expected for each number to occur approximately 1000 times... I couldn't recall the name of this theory...

[JPF]

I couldn't recall the name of this theory...

The law of large numbers ?

JPF

[udosuk]

That's the one... Thanks JPF...

Another related concept is the law of averages...

[emm]

Bob was the 2nd one to be brought in. Seeing switch 2 in an 'on'-position, he gladly set it back to 'off' and counted 'one'.

The problem is Bob not knowing the starting position of the switches. He would only count 'one' if he assumed switch#2 was 'on' to begin with and he was the first switcher. If he assumes it had been 'off' then he would have counted 'two' = the 1st guy + himself and RW's theory would have worked.

The thing is for Bob to know the starting position of the switches.

They agree to put switch#2 to ‘off’ or leave it that way if it is already. Then they will all leave #2 alone until Bob gets there and Bob will be the first to put it ‘on’. Then whenever they find it ‘on’ they know Bob has been and they will switch it ‘off’ on one subsequent visit only – then Bob can count the other 22 of them.

[udosuk]

They agree to put switch#2 to ‘off’ or leave it that way if it is already. Then they will all leave #2 alone until Bob gets there and Bob will be the first to put it ‘on’. Then whenever they find it ‘on’ they know Bob has been and they will switch it ‘off’ on one subsequent visit only – then Bob can count the other 22 of them.

The problem is that there is no way for the rest of the 22 to know if Bob has visited the room for the first time or not! If they see #2 'on' it could be done by Bob or it could be like that initially...

[emm]

True - this will not work if the first switcher is not Bob and the switch is on. So what they’re going to have to do is go through the whole thing twice – if he waits until they all switch it off twice, then they should be covered … I think.

[udosuk]

Ah madam... Although you didn't write a detailed plan like RW did... It seems you have essentially found the correct answer... So well done! This is what the "official solution" should look like:

Elect a spokesman.

Each prisoner other than the spokesman maintains a counter with initial value 0. When he enters the switch room, if switch "1" is "off" and his counter is 0 or 1, then he switches "1" to "on" and increments his counter. Otherwise (switch "1" is already "on" or his counter is 2) he switches "2".

The spokesman also has a counter with initial value 0. When he enters the switch room, if switch "1" is "on", he switches "1" to "off" and increments his counter. Otherwise (switch "1" is already "off") he switches "2". When the spokesman's counter reaches 44, he declares to the warden "We have all visited the switch room."

He is safe in making this declaration: among the 44 times that the switch had been "on", at most once was because the switch might have started out in the "on" position at the beginning of time. At most two were due to each prisoner (other than the spokesman himself) turning it on. If not everyone had visited the switch room, then it could have been turned "on" at most 2*21=42 times, and his counter would not exceed 42+1=43.

Further, given enough time, each prisoner will have two opportunities to turn "on" the switch, so that the spokesman's counter will eventually reach or exceed 44.

Switch "2" is only used so that the prisoner has something to flip when the protocol says he should not flip switch "1".

The non-spokeman prisoners turn the switch on twice instead of just once, because of the uncertainty about its initial position.

Perhaps someone could suggest a more efficient solution, making better use of both switches?

[MCC]

They could agree to wait a period of time, say 100 days or 200 days or 300 days, to give Bob a chance to set the position of switch #2, then after the agreed time period the prisoners can then start using switch #2.
They only need to switch #2 on the once.
Then after switch #2 has been turn on 22 times Bob can then declare that they have all visited the switch room


Scenario 2:
The warden is a right bar-steward and on Bob's first visit to the switch room he looked upon the light switches his heart fell He knew they would never be let out.

Why


MCC

[udosuk]

They could agree to wait a period of time, say 100 days or 200 days or 300 days, to give Bob a chance to set the position of switch #2, then after the agreed time period the prisoners can then start using switch #2.
They only need to switch #2 on the once.
Then after switch #2 has been turn on 22 times Bob can then declare that they have all visited the switch room...

Problem is there is still a possibility (no matter how small) that during that agreed period of time, Bob is never drawed to enter the room... The puzzle requires a 100% watertight scheme that couldn't go wrong (e.g. wrong claim, neverending loop)...

Scenario 2:
The warden is a right bar-steward and on Bob's first visit to the switch room he looked upon the light switches his heart fell He knew they would never be let out.

Why

Turns out MCC is also a right bar-steward and on my first glimpse of this post I looked upon the above paragraph my heart fell I knew I could never answer this...

Why