|
A Conditional Protocol |
|
|
|
It is sometimes necessary to communicate information by indirect means, and a surprising amount of information can often be conveyed using a pre-established protocol specifically designed for the given circumstances. As an abstract example, consider the natural numbers from 1 to 28, one of which is to be arbitrarily selected as the "winning" number and made known to us. Then four other numbers are arbitrarily drawn from the list (without replacement) and given to us, and our task is to communicate knowledge of the winning number to someone else simply by sending them our four numbers arranged in some particular order. It's easy to establish a protocol for communicating this information on this basis, because the recipient knows the winning number is not one of the four he receives from us, so there are really only 24 possibilities, which can be arranged in ascending order and placed in one-to-one correspondence with the 24 distinct permutations of the four numbers designated a,b,c,d in ascending order. |
|
|
|
However, suppose the original list of number is increased from 28 to, say, 42. Can we still establish an effective protocol based on sending four numbers in some order? Clearly not, because there are only 24 distinct "messages" we can send for four given message-numbers, whereas there are 38 possible “winning numbers". Hence we can't possibly distinguish each possible result. |
|
|
|
But what if we relax our protocol condition slightly, and permit ourselves to send either all four of the message-numbers in some order or to send just three of the numbers in some order? In this case we can't rule out the possibility of an effective protocol, because the number of distinct answers we can give with a fixed set of four message-numbers is 24 permutations of four plus 6 permutations of three, and there are four distinct ways of choosing three of the four message numbers. Hence we have 24 + 4(6) = 48 distinct messages that we can send based on any four message-numbers. Of course, the distinctness of some of these may not be evident to the recipient, since they may see only three of our four message numbers, but at least we can't automatically rule out a successful protocol. |
|
|
|
One protocol that accomplishes our objective is based on a pre-defined set of 6-element subsets of the original 42 numbers, defined so as to minimize the overlaps between subsets. For example, we can take the 42 columns from the arrays shown below: |
|
|
|
42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 |
|
|
|
1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 |
|
8 9 10 11 12 13 14 9 10 11 12 13 14 8 10 11 12 13 14 8 9 |
|
15 16 17 18 19 20 21 17 18 19 20 21 15 16 19 20 21 15 16 17 18 |
|
22 23 24 25 26 27 28 25 26 27 28 22 23 24 28 22 23 24 25 26 27 |
|
29 30 31 32 33 34 35 33 34 35 29 30 31 32 30 31 32 33 34 35 29 |
|
36 37 38 39 40 41 42 41 42 36 37 38 39 40 39 40 41 42 36 37 38 |
|
|
|
|
|
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 |
|
|
|
1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 |
|
11 12 13 14 8 9 10 12 13 14 8 9 10 11 13 14 8 9 10 11 12 |
|
21 15 16 17 18 19 20 16 17 18 19 20 21 15 18 19 20 21 15 16 17 |
|
24 25 26 27 28 22 23 27 28 22 23 24 25 26 23 24 25 26 27 28 22 |
|
34 35 29 30 31 32 33 31 32 33 34 35 29 30 35 29 30 31 32 33 34 |
|
37 38 39 40 41 42 36 42 36 37 38 39 40 41 40 41 42 36 37 38 39 |
|
|
|
The first array simply lists the numbers 1 through 42 consecutively in horizontal rows. The second array shifts the nth row 1(n-1) places to the right (with wrap-around). The third array shifts the nth row 2(n-1) places to the right, and so on. Each column is associated with a unique number from 1 to 42, noted above it. |
|
|
|
Our transmission protocol is based on four given "message-numbers" which we will call a,b,c,d in ascending order. There is also a single winning number w. We check each of the four possible sets of three message numbers, (a,b,c), (a,b,d), (a,c,d), and (b,c,d) and compute the sum of the three numbers, and subtract 42 if necessary to place the reduced sum in the range from 1 to 42. (We could more easily express this if we made the range 0 to 41 and worked modulo 42). This will necessarily give us four distinct indices, because no two of these triples differ by more than one number, and the basic elements are distinct. |
|
|
|
We then examine the four columns in the above arrays corresponding to those four indices (i.e., the four reduced sums). If the winning number w appears in one of those columns, we then transmit the corresponding triple, with its elements arranged in one of the six permutations to pick out the appropriate number from the indexed column. |
|
|
|
If, on the other hand, the winning number is not in any of the four indexed columns, we will transmit all four message numbers. Of course, these can only be arranged in 24 distinct ways, but these suffice, because we can rule out all the numbers in the four indexed columns, as well as the four message-numbers themselves. If there were no overlap, this would exclude 28 numbers, leaving only 14 to be selected by the 24 permutations. However, there is typically overlap between the numbers in the four indexed columns, and between the column numbers and the message numbers. We can assign the column indices so that no index appears in its own column (to do this in the above arrays we would make the column transpositions (12,13), (20,21), (27,28), (34,35), and (38,39)), but there can still be overlap from one column to another index. |
|
|
|
Nevertheless, we are assured that the fours columns (even without the four given indices) will always cover at least 18 distinct numbers, because every pair of columns shares no more than one number in common, so the most overlap would occur if each of the six pairs of four columns shared a number, thereby reducing the total from 24 down to 24-6 = 18. Hence, from the overall 42 numbers, we are left with no more than 42-18 = 24 possible values of w after excluding those that appear in the four columns that can be indexed by three of the four given message-numbers. These can therefore be arranged in order and placed in unique correspondence with the permutations of the four message numbers. |
|
|
|
At the receiving end, if three numbers are received, we compute the index given by the sum of the three numbers, reduced to the range from 1 to 42, to give us the appropriate column of the table, and then use the ordering of the three received numbers to select the winning number w from that column. If four numbers are received, we first compute the four indices from the sets of three, and eliminate all the numbers from the respective columns, as well as eliminating the four message-numbers themselves. We then arrange the remaining numbers into a list in ascending order, and use the arrangement of the four message numbers to select the winning number w. |
|
|