Author |
Topic: Communicating on a Grid of Bits (Read 577 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Communicating on a Grid of Bits
« on: May 18th, 2007, 1:24am » |
 Quote  Modify
|
Alice is given a m x n checkerboard, where m and n are both powers of 2. Each square on the board is already filled with either a 1 or a 0, according to some pattern previously unknown to Alice.
Alice is required to flip exactly one bit on this board of bits, and then send the board to Bob. However, Bob is unaware of what bit pattern was on the board prior to Alice's modification.
Question: How many bits of information can Alice send to Bob? In other words, what is the maximum number of distinguishable messages that Alice can send to Bob?
Source: Paul Cuff; Thomas Cover
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Communicating on a Grid of Bits
« Reply #1 on: May 18th, 2007, 3:13am » |
Quote Modify
|
Well, it's easy to get 1 bit. But I presume the best will be more in the range of log(n*m). Haven't a clue as to how yet though.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Communicating on a Grid of Bits
« Reply #2 on: May 18th, 2007, 3:53am » |
Quote Modify
|
How do you get 1 bit on a 1x1 board?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Communicating on a Grid of Bits
« Reply #3 on: May 18th, 2007, 7:21am » |
Quote Modify
|
I can see a simple way to get 2 bits (with m,n > 1).
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Communicating on a Grid of Bits
« Reply #5 on: May 19th, 2007, 9:30am » |
Quote Modify
|
By flipping one bit? Sending to Bob once?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Communicating on a Grid of Bits
« Reply #6 on: May 19th, 2007, 1:17pm » |
Quote Modify
|
I can get two bits accorss when I have 4 (random) bits; you can divide them in 4 equivalence classes
e.g
0000,0001,1111,1110
0010,0011,1101,1100
0100,0101,1011,1010
1000,1001,0111,0110
You can either stay in the same class (flipping the last bit), or go to any of the other classes by choosing one of the first three bits to flip.
I imagine something similar may work for higher numbers of bits. However I don't see how a rectangular board helps.
on May 18th, 2007, 3:53am, Barukh wrote:| How do you get 1 bit on a 1x1 board? |
|
Not, admittedly.
on May 19th, 2007, 7:23am, william wu wrote:| Turns out we can get on the order of log(mn) bits. |
|
Hah, I guessed correctly then. Now if only I could find a practical means to do it. (Or a provable means at least)
|
| « Last Edit: May 19th, 2007, 1:20pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Communicating on a Grid of Bits
« Reply #7 on: May 20th, 2007, 7:53am » |
Quote Modify
|
One way:
Let m=2i, n=2j
Your aim is to encode an (i+j)-bit message, C.
Each cell in the grid has binary co-ordinates, given by a number with i bits, x, and a number with j bits, y.
To decode the message in the grid, for the k'th bit of the message, when k<i set the bit to 1 if the sum of the contents of all cells with the k'th bit of the x co-ordinate 1 is odd; 0 if the sum is even. Similarly, if k>i, set the bit to 1 if the sum of the contents of all cells with the (k-i)'th bit of the y co-ordinate 1 is odd; 0 if the sum is even.
To encode the message C into a grid currently encoding the message D, find P=C XOR D, and treat P as co-ordinates by taking the first i bits as the x co-ordinate, and the remaining j bits as the y co-ordinate, and flip that cell's contents.
It's clear that this is the maximum amount of information that can be sent since you only have 2i+j possible actions, so you can't have more than 2i+j different messages.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Communicating on a Grid of Bits
« Reply #8 on: May 20th, 2007, 11:56am » |
Quote Modify
|
In short: Hamming code.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Communicating on a Grid of Bits
« Reply #9 on: May 20th, 2007, 11:59am » |
Quote Modify
|
on May 18th, 2007, 3:53am, Barukh wrote:| How do you get 1 bit on a 1x1 board? |
|
You can not. log2(m·n) is 0 for m=n=1.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Communicating on a Grid of Bits
« Reply #10 on: May 21st, 2007, 4:24am » |
Quote Modify
|
rmsgrey, your solution looks very intriguing. I feel it should be correct! 
However, I don't quite get the decoding process.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Communicating on a Grid of Bits
« Reply #11 on: May 21st, 2007, 5:00am » |
Quote Modify
|
Decoding to D:
D = XOR k=0..mn (bit(k)·k)
Encoding C
compute D as above
flip bit #(C xor D)
[oops, corrected! Thanks, rmsgrey]
|
| « Last Edit: May 22nd, 2007, 2:40am by Grimbal » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Communicating on a Grid of Bits
« Reply #12 on: May 21st, 2007, 11:32am » |
Quote Modify
|
on May 21st, 2007, 5:00am, Grimbal wrote:Decoding to D:
D = XOR k=0..i+j (bit(k)·k)
|
|
Not quite. Taking bit(P) to be the bit at point P in the grid
D = XOR P=0...mn (bit(P)*P)
In other words, XOR together the co-ordinates of every '1' in the grid.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Communicating on a Grid of Bits
« Reply #13 on: May 21st, 2007, 1:04pm » |
Quote Modify
|
(Sounds familiar.)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print