Harder Math/CS Problem - Page 2

Suppose 65 messages were possible. Take any initial starting matrix, then the sender can send at most 64 matrices (by picking one of the 64 entries to switch from the initial one); so at least one of the messages is unsendable, no matter how you assign matrices to messages.

Instead of having an 8x8 matrix with 64 entries, let's have a 2x2 matrix with 4 entries and show how to get easily 4 messages in a generalizable way.

For a matrix M, the decoder calculates the following two functions:
f_0(M) = count if the number of 1's in the first column is even
f_1(M) = count if the number of 1's in the first row is even
Then there's 4 possible messages formed by combining the two possibilities in each of f_0, f_1.

The encoder does the following:

Call the initial matrix the encoder gets N. Say he wants to send the message g_0, g_1. So he calculates f_0(N), f_1(N). Then if he wants to change f_0 (i.e. g_0 is different from f_0(N)), then he needs to make a change in the first column. Similarly, if he wants to change f_1 then he needs to make a change in the first row. He can choose to do this independently for rows and columns, e.g. if he wants to change both f_0 and f_1, he can change the entry in the first row and first column; if he wants to change just f_0, then he can change the entry in the first column, second row. So he can send any two bits this way, no matter what the starting arrangements are.

You can generalize this argument to sending 3 bits (i.e. 8 messages) using the 8 corners of a cube instead of a matrix. To do this, the receiver now looks at the rows, columns, and the towers along the 3rd dimension. (The receiver will now be adding up 4 numbers each time.)

You can also generalize it to sending 6 bits (i.e. 64 messages) using the 64 corners of a 6-dimensional hypercube. This is the same as the 8x8 matrix in the original problem if you rearrange the 64 numbers in the 8x8 matrix.

... but it's a little more rigorous.

Number the entries of the matrix from 0 to 63, and let M(a0, a1, a2, a3, a4, a5) represent the value of the matrix at the entry when you think of a5,a4,a3,a2,a1,a0 as a binary number (a5 * 2^5 + a4 * 2^4 + ... + a0).

The receiver defines 6 functions:
f_0 = parity of the sum of M(a0, a1, a2, a3, a4, a5) where a0 = 1. i.e. sum over a1, a2, a3, a4, a5 in {0, 1} of M(1, a1, a2, a3, a4, a5) mod 2.
and similarly
f_i = parity of the sum of M(a0, a1, a2, a3, a4, a5) where a_i = 1.
Then the receiver decodes the matrix by treating the 6 bits f_0, f_1, ... f_5 as a binary number, so there are 64 possibilities.

The encoder does the following:
Given the initial matrix M, he calculates f_i(M). Then he picks the 6 bits g_0, g_1, ... g_5 for the message he wants to encode. Let S be the subset of {0, 1, 2, 3, 4, 5} of indices i where f_i(M) != g_i. Then he alters M by changing the entry formed by binary number formed by sum_{s in S}{2^s}. e.g. if he wants to change bits #2, 3, then he toggles the entry at (0, 1, 1, 0, 0, 0).