[Guest]

Hi gang.

This is a variation on the lightbulb escape problem posted in:

http://brainden.com/forum/index.php?showtopic=4004

A group of 7 prisoners are captured, and taken before the warden. Being the sporting type, he proposes a game by which they may all escape. Being also the sadistic type, the consequences of them losing is that they will all be executed.

"First, you must choose a prisoner to serve as your representative. Afterward, you will all be taken to individual cells, including your representative.

Then, for the next seven weeks, we will play the following game.

For the first six days of each week, I will select a single prisoner at random each day, excluding your representative, and bring him from his cell into a room. The choice is completely random, so the same prisoner may be brought to the room zero, one or multiple times during the six days. In this room are two on / off switches labelled A and B, one and only one of which MUST be chosen and toggled by the prisoner. Then, the prisoner will be taken back to his cell. The prisoner may not leave notes, belongings, etc in the room, nor modify the room in any way besides manipulating a switch.

On the last day of each week, your representative will be brought into the same room, where he must also choose and toggle one and only one of the switches. Afterwards he too will be brought back to his cell. The same rules prohibitting modifications to the room apply to the representative; only one of the switches may be manipulated.

Neither the prisoners nor their representative may communicate in any way with each other while in their cells or in transit to or from them. Any attempt to do so will result in you all being executed.

This will continue for seven weeks. On the first day of the following week, your representative will be brought before me and asked whether all his fellow prisoners have visited the room at least once during the previous seven weeks. If he answers correctly, you will all be set free. If he answers incorrectly, you will all be shot."

The prisoners are given a day to select their representative and plan their strategy. What strategy should they employ to ensure that they are all set free ? They may safely assume both switches are off before the game begins, and that the warden will not swap the labels or otherwise manipulate the switches during the game.

NOTE: unlike the original problem, every prisoner brought to the room MUST press one of the switches.

Edited August 16, 2008 by ShawnInToronto

[Guest]

The representative would tell each prisoner that the first one to enter will hit switch 1. (assuming they are both off as you stated) When the next prisoners come in, if switch 1 is up, then leave it and just toggle switch 2. The next day, the first prisoner (unless it was the first the day before) will toggle switch 1. They rest leave it alone. So the basic strategy is if you have never toggled switch 1 to on, do it IF it is off. When the representative comes in at the end of each day, he can just create a count in his head of how many times the first switch has been toggled on. If there is 1 prisoner at the end of the 7 weeks that has not been in the room, there will have only been 5 times that switch 1 has been toggled on. If the switch is on, the representative will toggle it back off so the next person whos first time who HASNT toggled 1 can.

Edited August 16, 2008 by EyesOfTheDead

[bonanova]

btw topic 892 might be the original link mentioned in the OP.

[Guest]

Nevermind, my first solution won't work

[Guest]

I've come to the conclusion that it is not solvable, here's why. If the switches are set at 0-0, by the 7th day, the switches will only be able to represent 2 states, 0-0 or 11. It really doesn't make a difference that the representative flips a switch because there will be the same issue. Say he flips to 1-0, the only combination by the end of the next week will be 1-0 or 0-1. Therefore week will only give you one of 2 values. Now my original thought was to make the switches equal either an even or odd number of first time prisoners that have entered. 00 = even 11 = odd. But there in lies the problem. Say (using my method) 5 people enter the first week for the first time. The switches end up as 1-1. Those same people, by the governed rules, could be the only ones to enter the following weeks. (Ignoring the representative flipping a switch, because as I said it will only end up the original state after him, or the opposite after 6 flips) So then each other combination would be (by my rules) 0-0, which the rep could interpret as 0, 2, 4, 6. So my conclusion is that you are only going to really be able to get 1 of 2 possible values each week, there's not enough to distinguish whether any NEW prosoners have entered or not.

Edited August 17, 2008 by EyesOfTheDead

[Guest]

Use the top of each switch, the bottom of each switch and the sides of each switch as markers.

Your in prison, right??? So they probably aren't going to think about your hands being dirty. The first time you enter the room you make sure you touch a clean spot to flip a switch (thus 'marking it' with dirt.) If it's NOT your first time in the room you touch a dirty spot (careful not to wipe it clean) On the last day the representative only needs to look for clean spots on the switches. If there are clean 'spots', someone never got to the room. If there are not, everyone got to the room. Like I said, they may call this 'communication, and shoot us all. But it's the best I have right now.

[bonanova]

The problem reduces to finding a 7-bit representation of the combination of weekly events that signals a visit from each of prisoners 1-6.

Here are some observations.

Let R = the representative prisoner.

After 7 weeks, R will have received 7 bits of information.

Proof:

As EOTD points out, on his odd-week visits, R will find A and B the same; and on his even-week visits, different.

Let configurations OFF/OFF and OFF/ON represent 0 and configurations ON/OFF and ON/ON represent 1.

That's one bit of information each week. Seven weeks = seven bits.

The sixth prisoner each week [call him Six] can determine those bits.

Proof:

On the odd weeks, Six sees either ON/OFF or OFF/ON.

With his choice of switch, Six can present to R either ON/ON [1] or OFF/OFF [0].

On the even weeks, Six sees either ON/ON or OFF/OFF.

With his choice of switch, Six can present R either ON/OFF [1] or OFF/ON [0].

In reality, Six also receives one bit of information: switch A is ON [1] or OFF [0].

Note that B provides no additional information: it's determined by A and the odd-ness of the week.

Switch A can carry some limited information:

Here are two possibilities:

1. A can represent the first repeat visit by a prisoner each week:
   If prisoner 1-6 has a repeat visit during a week, and if switch A is off, he turns in on.
   Otherwise he flips switch B.
   If R finds switch A off, then there were no repeats that week.
   R would know that all six of the others visited the room that week.
   R's job would be to ensure A is off after each of his visits.
   That would work say, for whatever / ... / 123456R / ... / whatever
   
   
   
2. A could alternatively signal the first visit of one prisoner that week:
   If prisoner 1-6 visits for the first time, and if A is off, he turns it on.
   Otherwise he flips switch B.
   That would work for 111111R / 222222R / 333333R / 444444R / 555555R / 666666R / ... whatever.
   That is, each prisoner's first visit would have to occur in a different week.
   Again, R would ensure A is off after each of his visits.
   

But note that strategy 1 fails in the cases for which 2 succeeds, and 2 fails where 1 succeeds.

Net:

It seems that we can simply use switch A to carry information; B is there only because the OP says something has to be flipped.

R receives 1 bit of info each week [the status of A].

After R takes note of A each week, he can either

1. ensure A is OFF, or
   
2. flip B.
   

The second alternative forwards the bit of info to next week's visitors, and may be the preferred alternative: each week the strategy could then be different, so long as the prisoners [why wouldn't they know?] know which week it is when they visit.

Take it from there.

[Guest]

The problem reduces to finding a 7-bit representation of the combination of weekly events that signals a visit from each of prisoners 1-6.

Here are some observations.

Let R = the representative prisoner.

After 7 weeks, R will have received 7 bits of information.

Proof:

As EOTD points out, on his odd-week visits, R will find A and B the same; and on his even-week visits, different.

Let configurations OFF/OFF and OFF/ON represent 0 and configurations ON/OFF and ON/ON represent 1.

That's one bit of information each week. Seven weeks = seven bits.

The sixth prisoner each week [call him Six] can determine those bits.

Proof:

On the odd weeks, Six sees either ON/OFF or OFF/ON.

With his choice of switch, Six can present to R either ON/ON [1] or OFF/OFF [0].

On the even weeks, Six sees either ON/ON or OFF/OFF.

With his choice of switch, Six can present R either ON/OFF [1] or OFF/ON [0].

In reality, Six also receives one bit of information: switch A is ON [1] or OFF [0].

Note that B provides no additional information: it's determined by A and the odd-ness of the week.

Switch A can carry some limited information:

Here are two possibilities:

1. A can represent the first repeat visit by a prisoner each week:
   If prisoner 1-6 has a repeat visit during a week, and if switch A is off, he turns in on.
   Otherwise he flips switch B.
   If R finds switch A off, then there were no repeats that week.
   R would know that all six of the others visited the room that week.
   R's job would be to ensure A is off after each of his visits.
   That would work say, for whatever / ... / 123456R / ... / whatever
   
   
   
2. A could alternatively signal the first visit of one prisoner that week:
   If prisoner 1-6 visits for the first time, and if A is off, he turns it on.
   Otherwise he flips switch B.
   That would work for 111111R / 222222R / 333333R / 444444R / 555555R / 666666R / ... whatever.
   That is, each prisoner's first visit would have to occur in a different week.
   Again, R would ensure A is off after each of his visits.
   

But note that strategy 1 fails in the cases for which 2 succeeds, and 2 fails where 1 succeeds.

Net:

It seems that we can simply use switch A to carry information; B is there only because the OP says something has to be flipped.

R receives 1 bit of info each week [the status of A].

After R takes note of A each week, he can either

1. ensure A is OFF, or
   
2. flip B.
   

The second alternative forwards the bit of info to next week's visitors, and may be the preferred alternative: each week the strategy could then be different, so long as the prisoners [why wouldn't they know?] know which week it is when they visit.

Take it from there.

This WAS my line of thinking. But consider that maybe prisoners 1 and 2 are taken the first 2 days of the first week, but then are not taken again for the rest of the seven weeks. Since the rep will obviously think more than 1 or 2 new prisoners entered, there is no way to determine that those 2 people have been there, and that never will again.

[bonanova]

This WAS my line of thinking. But consider that maybe prisoners 1 and 2 are taken the first 2 days of the first week, but then are not taken again for the rest of the seven weeks. Since the rep will obviously think more than 1 or 2 new prisoners entered, there is no way to determine that those 2 people have been there, and that never will again.

Agree totally.

By "take it from there" I meant "finish what I can't finish", not " the rest is easy."

[Guest]

Since the selection is completely random (as stated in the OP), I would be OK with just guessing that each of the 6 people get picked some time during the 40 days. The probability of losing would be less than .5%

[HoustonHokie]

In reality, we only need to track 5 prisoners, not all six. The prisoner who enters on the first day will, by definition, have entered the room for the first time. So that prisoner (call him P1) can always behave in whatever way gets designated for those who are repeating. All that we need to know, then, is if prisoners 2-6 enter the room. Don't know if that helps enough, but it should help some.

[Guest]

If the person has been to the room twice they flick the 2nd switch into the up

position, if it is already up switch the first. If not they flick the

first.

When the rep enters if the 2nd switch is down everyone has been to

the room, if up someone has missed out, proceed to flick it down again (if not switch switch 1) and

restart for the next week?

[Guest]

Taliesin - by "up position" do you mean on or off?

I see you reasoning - that if a prisoner makes two or more visits to the room in the same week, this means that one of the other prisoners has not entered at all that week. However, how does the representative know whether it is the same prisoner or a different prisoner that does not get a chance to enter the room the next week. Some prisoners may only enter the room once in the whole 7 weeks