|
So this one is quite tough. If you haven't done my first one, I recommend trying that one out first as it's much easier. I actually was not able to solve this one, but several of the possible answers were revealed to me, and I'm confident I would not have been able to solve it even if I kept trying. 
I don't expect anyone to get a correct answer, but I think it's a nice thinking exercise to try and figure it out. I recommend contributing whatever ideas you have and discussing it with others. If you do get this one on your own, then mad props.
OK so here's the problem.
You have a randomized 8x8 bit matrix, meaning that all entries of the matrix are either 0 or 1 with equal probability. You are required to flip exactly one entry in the matrix from either 0 to 1 or 1 to 0. The only flexibility you get is that you can choose which entry you get to flip. What you want to do with this matrix is communicate messages to your friend by sending this matrix to him.
The problem is, create a protocol such that you can send the maximum number of messages to your friend.
Now the description might have been confusing, so a few clarifications.
1) Your friend does not know the randomized matrix when you send a message, only you do.
2) You have to be able to send any message from any starting matrix.
3) It might be useful first to try and figure out how many possible messages you can send before trying to create the protocol.
To give an example with a simple 1x2 matrix case. Let's suppose we just want to send 2 messages, Hello, and Bye. The protocol I agree upon with my friend is that if the first index is "1", then the message is Hello. If the first index is "0", then the message is Bye.
[1 0], [1 1] = Hello
[0 0], [0 1] = Bye
It's pretty easy to prove with brute force that this protocol works no matter what random matrix we start with. Any matrix in the 1x2 bit matrix space can become either Hello or Bye with 1 bit flip.
|
I think the maximum possible number of messages is 2^64, since the matrix is 8x8 binary.
edit: I had a protocol, but it didn't follow specifications cuz I forgot you could only change one bit.
|
I came up with a brilliant solution it in my head, but then I had to go engage in some violence (I work as a bouncer), and now I've forgotten the whole thing.
|
On January 23 2008 13:01 SonuvBob wrote:
I came up with a brilliant solution it in my head, but then I had to go engage in some violence (I work as a bouncer), and now I've forgotten the whole thing. Yeah, I wrote my answer on a piece of paper, but I had to stop a fight (as a bouncer too), and the paper was missing when I returned.
PS: Do two of the same joke make the joke lame? Or just mine?
|
Canada7170 Posts
I'm still kinda confused by the description. I can't really say where I'm confused, because I'm confused everywhere.
Could you give another example, maybe greater than a 1x2?
|
On January 23 2008 13:07 mikeymoo wrote:
I'm still kinda confused by the description. I can't really say where I'm confused, because I'm confused everywhere.
Could you give another example, maybe greater than a 1x2?
It's sort of like: "if the matrix has a 1 as the first bit, then it's hello, if 0, then it's bye."
then you get a _random_ matrix like this each time:
10101101
01010010
10101010
01010101
10111001
11010010
10110110
and you can only change one thing, since you've agreed with your friend to only pay attention to the first bit then,
10101101
01010010
10101010
01010101
10111001
11010010
10110110
is "hello"
and
00101101
01010010
10101010
01010101
10111001
11010010
10110110
is "bye"
|
Canada7170 Posts
Thank you. I'll sleep on this one and get back.
|
OK let's see if this helps. We'll still work with the 1x2 matrix though.
The matrix is completely random, so it has 4 possibilities.
[0 0]
[0 1]
[1 0]
[1 1]
Now what happens is, you start with one of these matrices, and you switch 1 entry, and then send the result to your friend. Let's suppose the matrix we randomly started with was [0 0].
Now, let's use the protocol I mentioned earlier. If I want to say hello to my friend, I should flip the first bit, and make the matrix [1 0]. If I want to say bye, I should flip the second bit, and make the matrix [0 1].
Let's start with another matrix, [1 0].
To say Hello, I flip the second bit to get [1 1].
To say Bye, I flip the first bit to get [0 0].
Now, this is a very simple protocol that only has 2 messages, and it can trivially be used with bigger matrices, but the hope of course is that we can make a protocol that sends more than 2 messages.
Remember that you always have to flip exactly one bit. Also, you need to be able to send any message from any starting matrix.
If you need more clarification, feel free to ask.
|
United States5262 Posts
I have enough trouble with Evil level Sudoku as it is.
|
Another example (though no more useful) would be to use the parity (whether there's an odd or even number of ones) of the matrix, since you can always change that with a single bit change. That still only gives you two possible messages (even or odd).
Seems like the best max you could possibly get is 64, since there's only 64 choices for a switch.
This reminds me a lot of that prisoner problem.
|
SonuvBob, I think your idea for odd and even parity is slightly flawed, because from a given matrix, you can only get an odd number of ones or only get an even number of ones. I think it's more like, if you have 4n or 4n+1 ones, then it's hello, and if you have 4n+2 or 4n+3 ones, then it's bye.
Your reasoning for the upper bound of 64 I believe is correct.
|
SonuvBob, I think that does put an upper limit on the number of possible messages.
I'm guessing that the actual limit is a binary message. Even with only 2 bits, you have to assign 2 possibilities to mean 1 message.
You can't use parity, because you HAVE to flip one bit every message, so the result is random anyways.
And since the matrix is random, you might end up with n 1s to start with. What do you do if you want to say "bye" then?
Er, I misunderstood? It looks like (# of 1s) mod 4 is what you're proposing... hm.....
|
You could technically use this kind of protocol: "if the first bit is 0, wait for my next message; if the first bit is 1, then count the number of digits until the first instance of '00' "
then just keep generating matrices until you get one that has a an instance of 00 where you want it, and change the first bit to 1. terribly inefficient, but it works 
illustration:
say I wanted to send message number 5. I would keep generating matrices and putting the first bit as 0 until I got something like this:
11011001
01010010
10101010
01010101
10111001
11010010
10110110
then I would change the first bit to 1, and counting from the first bit to the 00, you get 5, meaning message 5.
|
If you can throw away a given matrix and randomly generate a new matrix until you get one you want, you could have 2^64 possible matrices, each with a unique meaning, and keep generating until you get the one you want. I don't think that's the problem we're dealing with.
Using (# of 1s) mod m might be the way to go.
|
Yeah, but you wouldn't be "throwing away" the matrix in my case, you'd still be sending it, it's just that the 0 as the first bit would translate to "wait for my next message" or something.
|
If you're content with using multiple matrices, then you can make every one count by using the first bit as another bit in a string, with a predetermined byte length. Much better average throughput.
|
On January 23 2008 13:46 Slithe wrote:
SonuvBob, I think your idea for odd and even parity is slightly flawed, because from a given matrix, you can only get an odd number of ones or only get an even number of ones. I think it's more like, if you have 4n or 4n+1 ones, then it's hello, and if you have 4n+2 or 4n+3 ones, then it's bye.
Ah yeah, in my head I was thinking of the parity of just one row of the matrix, leaving plenty of ignored bits to pick if you don't want to change the parity. Anyway, either way it's useless other than as just an example, since you only get 2 messages. (Honestly it's not even different from changing just the first bit, but mikey wanted another example :p)
To clarify the problem some more for mikey/zdd/whoever else is reading, you want to maximize the number of possible messages you can relay with one 8x8 matrix. You must be able to do this with any random 8x8 bit matrix.
|
Oh yeah, my protocol is breaking this rule:
2) You have to be able to send any message from any starting matrix
man I'm stumped.
|
You can send at least 4 messages.
If we look at the parity of the first two lines, they will be {(0,0), (0,1), (1,0), (1,1)} for any given matrix.
Now, we can assign signal A = (0,1), signal B = (1,0), signal C = (1,1), and signal D = (0,0).
Also, signal A can be shown as Signal B with the parity of lines 3 and 4 being the same, and vice versa. So, given some matrix M,
x = (# of 1s in first line) mod 2
y = (# of 1s in second line) mod 2
z = (# of 1s in third line) mod 2 == (# of 1s in fourth line) mod 2
Then, the signals A, B, C, and D can be represented as follows:
A = {(0, 1, 0), (1, 0, 1)}
B = {(1, 0, 0), (0, 1, 1)}
C = {(0, 0, 0), (1, 1, 1)}
D = {(1, 1, 0), (0, 0, 1)}
Given any sequence of 3 bits, we can turn them into any of the 4 signals we wish to by flipping just one of these bits. Or if the sequence is one we already want, we can flip something on an ignored line.
I have a feeling that using the remaining 4 lines will be useful, too.
|
Huh, using the fourth line is redundant. We can just use the third line's parity for z.
If we map signals in this fashion, we can send 2^(# of lines) signals! Maybe. I dunno how to go about proving it 
Given any sequence of 4 bits, we can change it into any of 8 signals we wish to by flipping one of these bits, right? Um... let me think more...
Well duh, 2^(# of lines) isn't right, because it breaks down at 2^3. We still only have 4 signals.
|
Heck, using the lines is redundant! You can use the first 3 bits! Screw me, I thought I was being clever.
Now I'm sure there's a way to send more data. I'm gonna lose sleep over this.
|
|
|
Yeah, you can even use the matrix itself without calculating parity like this:
given matrix:
11011001
01010010
10101010
01010101
10111001
11010010
10110110
signal A:
01011001
01010010
10101010
01010101
10111001
11010010
10110110
signal B:
10011001
01010010
10101010
01010101
10111001
11010010
10110110
signal C:
11111001
01010010
10101010
01010101
10111001
11010010
10110110
signal D:
11011001
01010010
10101010
01010101
10111001
11010010
10110110
edit: oh nvm you figured it out already, while I was typing.
|
Okay, how's this scheme: We're making parity useful now.
The signals A, B, C, or D can be found by looking at the first three bits in the first line.
However, we can also send signals A', B', C', and D' by the following method.
If the starting parity of the first line is the same as the parity of the second line, then we will send A, B, C, or D on the SECOND line. These will denote A', B', C', and D', in the resulting state where the parity of the first and second lines are DIFFERENT. A, B, C, and D can still be sent via the first line. Therefore, if the parities of the lines are different, the receiver looks at the second line, and if they are the same, the receiver looks at the first line.
However, in the case that the parities are different to start with, we're going to write in the opposite side of the first case.
Now, we can send 8 different messages!
Err, no, that's wrong. It won't work
I need hint, or the bottle abuser will be getting angry.
|
Woo got it.
Here's a proof that the upper bound is 64:
+ Show Spoiler [Proof upper bound is 64] +
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.
Now here's a protocol that achieves 64.
+ Show Spoiler [Description - might make sense] +
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.
+ Show Spoiler [Description - probably won't mak…] +
... 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).
|
Polemarch, you got that yourself right?
I am so bitterly disappointed at myself and filled with jealousy. Be aware that you have just made a lifelong enemy. >_<
|
oh no, I don't want a lifelong enemy with such an awesome sig, haha. I already pasted that to some other people after seeing some random post of yours.
I did get that myself, but it is tough - spent probably a couple hours working on it. And I did a fair number of math contests before and a couple degrees in CS, so I'm kind of used to this kind of thinking.
|
haha Polemarch that's beautiful... I had a proof but it was totally nonconstructive (based on symmetry in the corresponding graph). I got the 2x2 case constructively but had no idea how to extend it. I'll have to remember that trick of extending the dimensions to preserve symmetry. I suck so much at combinatorics... It is my achilles' heel on math Olympiad competitions
Thanks so much for the proof. Polemarch did you used to do the Olympiads or perhaps the Putnam?
|
By the way if the OP could continue posting things around this difficulty level that would be wonderful. I need some practice with combinatorics.
|
Oh my god Polemarch you got one of the answers that's amazing. Massive respect.
The answer Polemarch got is a geometric approach to the problem using Hypercubes. I've heard two other answers before. One involves something about power sets, it's similar to the Hypercube solution I think. The other one is a very elegant solution that utilizes XOR as part of the answer.
|
Also, I can probably muster up some other problems, but ones of this difficulty may not come by so often.
I'll put up another problem tomorrow, but it won't be that hard.
|
Sounds like you guys would have fun with randomizers and LRS (linear recursive sequence) with bits~
|
haha is slithe doing this for our enjoyment, or is he a math/cs major that posts his homework problems when he gets them, and then harvests the answers the daybefore his hw is due? lol
|
lol if these were my homework problems I'd fail the classes so hard
|
|
|
|
|
|
EPT
