A Procrustean 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 columns in the above arrays corresponding to
those four indices.  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 incides) 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 tat 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 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.