Puzzle #6 – The Spy – (A real tough one…)June 22, 2007
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?
- 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.