Author |
Topic: Spy transmission 15bit (Read 515 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Spy transmission 15bit
« on: Nov 24th, 2005, 4:41pm » |
 Quote  Modify
|
Alice, as usual, wants to send a message to Bob.
This time Alice is a spy in an enemy transmission tower, which sends out exactly 15 bits each day. Alice sees the whole message before it is sent, and is capable of then flipping at most one bit. How much information can she send to Bob?
(Of course they discuss their scheme ahead of time, but without any knowledge of the enemy's bits other than that there are 15 of them.)
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Spy transmission 15bit
« Reply #1 on: Nov 24th, 2005, 7:32pm » |
Quote Modify
|
I could be wrong, but if they don't know anything about the 15 bits before hand, it seems to me that she can send only one bit per day, by having him count even bit parity as 0, and odd bit parity as 1.
Of course, whatever the scheme is, it is going to have to take days to transmit any useful information. She had better hope no one notices that the messages they are trying to send (which must be important for them to have set up this weird transmitter in the first place) are being screwed up by her.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Spy transmission 15bit
« Reply #2 on: Nov 24th, 2005, 10:45pm » |
Quote Modify
|
She can do much better than that...
And as for why they wouldn't notice what she's doing, well, that's just part of the puzzle 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Spy transmission 15bit
« Reply #3 on: Nov 25th, 2005, 12:54am » |
Quote Modify
|
I can see how she could send log23 bits. But that's not a lot more
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Spy transmission 15bit
« Reply #4 on: Nov 26th, 2005, 7:06am » |
Quote Modify
|
Just with 3 bits she could transmit 2:
| hidden: |
The receiver computes
abc --> a^b, a^c (^ = xor)
Alice first checks a^b and a^c. If one of the 2 bits is wrong, Alice can change b or c. If both are wrong, Alice can change a.
|
|
|
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Spy transmission 15bit
« Reply #5 on: Nov 26th, 2005, 7:20am » |
Quote Modify
|
To continue Grimbal's idea:
With 7 bits, transmitting 3 bits is possible:
Receiving calculates:
A=a^b^c^d
B=b^d^e^f
C=c^d^e^g
Alice check the 3 values:
all ok: change nothing
A wrong: change a
B wrong: change f
C wrong: change g
A,B wrong: change b
A,C wrong: change c
B,C wrong: change e
A,B,C wrong: change d
This way, with 15 bits, 4 bit may be transmitted:
A=xor(a,e,f,g,k,l,m,o)
B=xor(b,e,h,i,k,l,n,o)
C=xor(c,f,h,j,k,m,n,o)
D=xor(d,g,i,j,l,m,n,o)
|
| « Last Edit: Nov 26th, 2005, 7:27am by BNC » |
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Spy transmission 15bit
« Reply #6 on: Nov 26th, 2005, 7:34am » |
Quote Modify
|
And here is the solution:
| hidden: |
You have a 15-bit preexisting message P.
You have a 4-bit message M to pass.
Number the 15 bits of P from 1 to 15, express the numbers in binary.
Compute A = the xor of the numbers of the bits that are set in P. P' = P.
If A = M, you don't need to change anything.
If not, B=A^M is a number from 1 to 15. Change bit #B in P giving P'.
Send P'.
The receiver gets P'.
He computes A' = xor of the numbers of the bits that are set in P'.
If no bit was changed, A' = M.
If one was, by construction, A' differs from A in that the bits of B were inverted once more or once left.
A' = A^B = A^(A^M) = M.
So, computing A' yields the message M.
|
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Spy transmission 15bit
« Reply #7 on: Nov 26th, 2005, 7:35am » |
Quote Modify
|
As you see, I was about to say that.... 
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Spy transmission 15bit
« Reply #8 on: Nov 26th, 2005, 7:36am » |
Quote Modify
|
.. which is obviously the optimum, as by tweeking at most one bit out of a stream of 2n-1 bits, one can not send more than n bits of information.
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Spy transmission 15bit
« Reply #9 on: Nov 26th, 2005, 1:01pm » |
Quote Modify
|
Yes, exactly. And the reason the enemy won't notice is because they're using a (15,11) hamming code, which detects and corrects single-bit errors. They're only sending 11 bits of information, and Alice manages to use the other 4 bits for herself 
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Spy transmission 15bit
« Reply #10 on: Nov 26th, 2005, 1:26pm » |
Quote Modify
|
Nice problem Eigenray!
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Spy transmission 15bit
« Reply #11 on: Nov 29th, 2005, 5:31am » |
Quote Modify
|
on Nov 26th, 2005, 1:01pm, Eigenray wrote:| Yes, exactly. And the reason the enemy won't notice is because they're using a (15,11) hamming code, which detects and corrects single-bit errors. They're only sending 11 bits of information, and Alice manages to use the other 4 bits for herself |
|
I guessed so. And if you know you start with a correct hamming code, you can just reverse the bit you want and detect the changed bit at the receiving side.
|
|
IP Logged |
|
|
|
Joe Fendel
Junior Member
Posts: 68
|
|
Re: Spy transmission 15bit
« Reply #12 on: Nov 29th, 2005, 7:44am » |
Quote Modify
|
So if the transmission is 5 bits, and Alice can flip 2 of them, how can she send a 4-bit message?
(I think this is actually easier than the original problem.)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print