Another Prisoner Problem 2...

[Yoruichi-san]

 

"Well, we're in a pickle.  There are 9 of us in the special cell block, arranged in a circular fashion and facing outward so that we can't see each other.  And worse, they don't want us 'to get too comfortable' so we are reassigned to different cells randomly each day after the morning walk."

 

"You're right, Mr. Fredege. I eavesdropped the another group talking about toilets but we don't have the comfort of having them in our own cells, so that's out.  The lights in my cell have been acting weird lately, but I don't know what that's about..."

 

"It think I might, Phiddler.  I overheard the guards talking, and it seems there is an issue with the wiring...rats or something of the sort, and now when one of us switches on or off the lights in our cell, the lights of the adjacent cells are also switched."

 

"Hmm...good observation K-croc.  I think we may be able to use that, but we'll have to be careful.  We need to avoid messing with the lights when the guards are walking by our cells, which as far as I can tell is at random intervals, so whatever we do has to be independent of time intervals."

 

"Alright, where do we start?"

[Barcallica]

Since the prisoners doesn't appear to be around, 

1. What is the beginning states of the lamps.

2. Can I use off/on then on/off as a signal?

3. How many times can they act a day? (it says they are shuffled each day)

[Yoruichi-san]

Since the prisoners doesn't appear to be around,

1. What is the beginning states of the lamps.

2. Can I use off/on then on/off as a signal?

3. How many times can they act a day? (it says they are shuffled each day)

1.Off

2.Sure

3.No limit, just the starting configuration is unknown.

[plasmid]

It seems unsolvable, so maybe I don't fully understand the question.

How independent of time intervals do things have to be?

For example, if a prisoner sees four flips of the light and waits say five minutes (or any other period of time that you want) without seeing anything, can he safely assume that the string of flips he was watching has ended?

Or do all the prisoners have to lie low at the same time when guards are about: meaning that if a prisoner has to interrupt a string of flips in the middle because of patrolling, then the other prisoners will also not be able to send flips at the same time?

For most solutions I could imagine, unless one of the above answers allows them to give more info than I think they're allowed to give, we end up facing the problem of a prisoner having to wait indefinitely to know if another flip is going to be sent to him or if a string of flips being sent to him has ended.

[Barcallica]

 

Since the prisoners doesn't appear to be around,

1. What is the beginning states of the lamps.

2. Can I use off/on then on/off as a signal?

3. How many times can they act a day? (it says they are shuffled each day)

1.Off

2.Sure

3.No limit, just the starting configuration is unknown.

 

 

(with regard to 2nd answer) Then can't it be solved with similar fashion. Switching once is odd, switching twice is even etc...

Anyway, this is what I was asking with second question.

[plasmid]

If a prisoner sees one flip, how does he ever know that he's only going to see just one flip and not eventually a second one if he waits long enough?

[Barcallica]

If a prisoner sees one flip, how does he ever know that he's only going to see just one flip and not eventually a second one if he waits long enough?

Second flip is immediately after first one that it actually like one action.

I mean Flif,flip is one continuous action there is no time wasted between them. So one could tell if it is flip or flipflip.

Edited August 30, 2014 by Barcallica

[Yoruichi-san]

Sorry for the confusion, I was in a hurry when I was writing this (packing for Paris...as a female, I think that says it all ), and have been in Paris with little reliable internet.  

 

Anyways, Barca is correct, you can assume the instantaneous flipping is distinguishable from leaving the lights on or off, and the prisoners can see a little ways down the hall from their cells so that they'll have a little prior warning to when a guard is coming.  The idea is to minimize the chain of actions so that they run a smaller risk of being caught by a guard.

[bonanova]

I hope you weren't counting on any ... sympathy ... for having to pack ... for Paris. 

[plasmid]

Just to make sure: If a prisoner sees his light getting flipped by someone other than himself, does he have any way to know whether the person flipping the lights is clockwise or counterclockwise from him?

If the answer to the above is no, then are the cells in the cell block distinguishable in any way (like being visibly numbered) such that the prisoners can say "Whoever's in cell #1 should start signaling according to this code, and whoever's in cell #2 should do X but whoever's in cell #9 should do Y"? Or will the prisoners be in cells that have no particular identifying features?

[Yoruichi-san]

Just to make sure: If a prisoner sees his light getting flipped by someone other than himself, does he have any way to know whether the person flipping the lights is clockwise or counterclockwise from him?

If the answer to the above is no, then are the cells in the cell block distinguishable in any way (like being visibly numbered) such that the prisoners can say "Whoever's in cell #1 should start signaling according to this code, and whoever's in cell #2 should do X but whoever's in cell #9 should do Y"? Or will the prisoners be in cells that have no particular identifying features?

 

No.

 

Yes, the cells are distinguishable, i.e. by their position from the entrance to the cell block.

[plasmid]

Ok, that's enough dallying around for now. Time for an answer.

Start by numbering the cells from 1 to 9. The prisoner in cell 1 sends a signal to cell 2 (and 9) encoding prisoner 1's (his own) name and execution number. Cell 9 sees that signal but just sits and waits for now. Cell 2 sends a signal to cell 3 (and 1) encoding the name and execution number for both the prisoner in cell 1 and the prisoner in cell 2 (himself). Cell 3 sends a signal encoding the identities and execution times of prisoners 1-3. This process proceeds up to and including cell 7 sending a message encoding 1-7's name and time.

Cell 8 has seen cells #1-7 name and time, and knows his own name and time, and can figure out 9's by process of elimination, so he knows everything. Cell 9 knows his own ID and time, and also saw #1's ID and time from that very first message, so #8 just needs to send the name and time of, say, cells 3-8 and then #9 will be able to figure out #2 by process of elimination. Cell 9 just needs to tell cell #1 the names and times of cells 4-9 because cell 1 already saw cell 2 sending a message to cell 3 with his name and time. Cell 1 just needs to signal 5-9 to cell 2. Cell 2 just needs to signal 6-9 to cell 3. That follows a similar pattern until cell 5 just needs to signal #9 to cell 6.

So the messages that need to be sent are:

Cell 1: Send cell 1's name and time (1 pair)

Cell 2: Send 1-2's names and times (2 pairs)

Cell 3: Send 1-3's names and times (3 pairs)

...

Cell 6: Send 1-6's names and times (6 pairs)

Cell 7: Send 1-7's names and times (7 pairs)

Cell 8: Send 3-8's names and times (6 pairs)

Cell 9: Send 4-9's names and times (6 pairs)

Cell 1: Send 5-9's names and times (5 pairs)

Cell 2: Send 6-9's names and times (4 pairs)

...

Cell 5: Send cell 9's name and time (1 pair)

In order for a prisoner to send 1 pair of name/time, they need to be able to encode 9x9=81 possibilities -- for example if you make an ordered list of the nine prisoners, then multiply the prisoner's number by 9 and add the order of execution for that prisoner to get a number that will uniquely encode that information. If you need to encode 2 pairs of name/time, that would take (9x8)x(9x8)=5184 possibilities -- if you've already said that Bob will be the 4th one executed, then you can remove Bob from the list of prisoners and 4th from the list of execution times so there are only eight possibilites left. Similar logic applies to sending larger numbers of pairs of information.

The prisoner who has to send the most with this setup is the poor guy in cell 7. He will have to encode a message with up to (9x8x7x6x5x4x3)x(9x8x7x6x5x4x3) ~= 3.3 x 10¹⁰ possibilities.

Since it won't be practically possible to flip a light switch that many times in a row, he should try to find some way of encoding better than just "send X flips in a row". If the prisoners can place gaps in between their flips, so the neghboring prisoners might see something like "X flips, gap, Y flips, gap, Z flips", then a logical way to send the information with minimal propensity for misinterpretation would be to send 14 sets of flips - the first two would be up to nine flips each and encode the name and execution time of cell 1, the next two would be up to eight flips each to encode the name and time of cell 2, etc. Maximum total number of flips by prisoner 7 would be 84.

If minimizing the number of flips is more important than being easily understood, then cell 7 could send a string of consecutive and non-consecutive flips to essentially make a binary number. If two flips are consecutive, record a zero; if they're separated by a gap, record a 1. In that case, in order to send a binary number up to (9x8x7x6x5x4x3)x(9x8x7x6x5x4x3) ~= 3.3 x 10¹⁰, he would have to make log(base2) 3.3 x 10¹⁰ = 35 flips, which is much better than 84.

Using that second method, the number of flips needed to encode each number of pairs would be

1 pair (sent by 2 prisoners): 7

2 pairs (sent by 2 prisoners): 13

3 pairs (sent by 2 prisoners): 18

4 pairs (sent by 2 prisoners): 24

5 pairs (sent by 2 prisoners): 28

6 pairs (sent by 3 prisoners): 32

7 pairs (sent by 1 prisoner): 35

Total number of flips would be 311

Edit: correction to the above.

The very last part, where I was calculating the number of flips needed, wasn't right. What I was calculating as log(base2) X was the number of short/long gaps between flips, so the number of flips would be one greater (there are N-1 gaps between N flips, and the gaps are what conveys the information). So the number of flips to send one pair of information (name and execution time) about a prisoner is actually one greater than each of the values in that last list, and the total number of flips needed for the solution would be 311+14=325

Edited September 9, 2014 by plasmid