Puzzle #6 - The Spy - (A real tough one…)

This one I heard a while back and saw that a version of it also appears in Peter Winkler’s excellent book Mathematical Puzzles - A Connoisseur’s Collection. Here is the version that appears in the book:

A spy in an enemy country wants to transmit information back to his home country.
The spy wants to utilize the enemy country’s daily morning radio transmission of 15-bits (which is also received in his home country). The spy is able to infiltrate the radio station 5 minutes before transmission time, analyze the transmission that is about to go on air, and can either leave as it is, or flip a single bit somewhere in the transmission (a flip of more than one bit would make the original transmission too corrupt).

how much information can the spy transmit to his operators?

remember:

• The transmission is most likely a different set of 15-bits each day but can also repeat the last day’s transmission. Best, assume it is random
• The spy is allowed to change a maximum of 1 bit in any position
• The spy has agreed on an algorithm/strategy with his operators before he was sent to the enemy country
• No other information or communication is available. the communication is strictly one way
• The spy sees for the first time the intended daily transmission 5 minutes before it goes on the air, he does not hold a list of all future transmissions
• The information on the other end should be extracted in a deterministic way

I believe this one is too tough for an interview question - it took me well over an hour to come up with a solution (well, that actually doesn’t say much…). Anyways, this is definitely one of my favorite puzzles.