|
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.
|
|
|
|
|
|
EPT
