Best Answer plasmid, 09 September 2014 - 06:34 AM

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

Spoiler for might not be optimal but is probably a good start

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

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

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

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

^{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

^{10}, he would have to make log(base2) 3.3 x 10^{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.

Spoiler for

Go to the full post
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