h1

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?

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.

Advertisements

15 comments

  1. Say if Spy and his country agreed for gray code sequence. For gray encoding, only one bit needs to be toggled in particular position (depending on previous sequence)- the receiving country will look for that particular bit position which is suppose to be changed on that day/Sequence.
    Say if a bit that suppose to be toggled is already holding the expected value on a day, the spy transmitts it unchanged, but the receiver will still get correct sequence.
    Taking this concept, spy can also leave holes (sequence not meeting) to indicate no-information on a particular day(by corrupting/leaving that particular bit in a way not to meet sequence). In the same lines, conveying few more deterministic information is possible.


  2. Maybe I didn’t understand what you mean. Remember the transmission is each day different and unknown to the operators or the spy. The spy itself is only able to see the upcoming (original) transmission 5 minutes before it goes on the air.
    Maybe you could show with a detailed example, or just email me.


  3. Let us take only first 4 bits of the transmission used by the spy(Later we can draw same logic for 15 bits, and can be extended for more than one set a day too!). the gray sequence would be 0000,0001,0011,0010, 0110,111 …. so on.
    first two days(both operators and spy knows which day they start their operation)operators monitor bit number zero.
    Say on first day the Actual 4 bits are 0001. Now the spy modifies the 0th bit, so the bits that go on air will be: 0000 (all zeros), so the zeroth bit matches the gray sequence(zeroth bit). As per agreed sequence in gray code the zeroth bit must be 1 on second day.Say Next day the actual bits are 1111, now spy leaves the sequence as it is, but the zeroth bit has actually matched the next change in the gray sequence.
    Third day the position that will be monitored by operators is bit number 1. Say the actual bits on that day is, 1001. Spy will modify bit number one. the bits go on air will be 1011. By this way only one bit needs to be modified(or left alone) to match a deterministic sequence of gray code.


  4. This still doesn’t show how many different unique symbols of information can be transmitted. To me, your system looks equivalent to just monitoring the first bit and either flipping it or not. What extra information can you convey to the operators by monitoring a different bit each day? It still looks like you transfer 2 symbols per day, or one bit.
    A lot more of info can be transferred but maybe I didn’t fully get your method…


  5. Another variant, though similar to the grey code approach.

    The spy and his operator prearrange an arbitrary choice of two bits out of the 15. Say bit 3 and bit 11.

    Each day the spy transmits one bit of information. If his bit is 0, he arranges for bits 3 and 11 of the transmission to be identical. They might already be identical, but if not, he flips one of those two bits (doesn’t matter which) to make them identical.

    If his bit is 1, he arranges bits 3 and 11 of the transmission to be different. As before, they might already be different, in which case he does nothing. But if bits 3 and 11 were the same, he flips one of them (doesn’t matter which).

    This occurred to me immediately upon reading the problem. I have tried to come up with a way for the spy to transfer more than one bit per day, but I haven’t come up with one yet, and am not sure that it is possible.

    Another variant: the spy transmits his bit by making the parity of the 15-bit word odd or even. He can change any bit out of the 15 to do that, so he doesn’t have to prearrange a pair of bits with his operator, though they do have to agree on whether 0=even and 1=odd, or vice versa.


  6. Continue thinking in the parity direction. A lot more information can be transferred by changing just one bit.
    A good approach is to look at a simpler problem. Imagine that instead the message is 3 bits long and the spy is allowed to change a single bit again. How much info can be transferred now? I think it is simpler to see it like that.


  7. Great puzzle, Nir. It’s been driving me crazy!

    In the 3 bit case, I can send one of 3 symbols (i.e., lg2(3) bits) each day, as follows (note the Gray code):
    000 = A
    001 = B
    011 = A
    010 = C
    110 = B
    111 = A
    101 = C
    100 = A

    Any code can be turned into any of the three symbols either by doing nothing or by flipping one bit.

    Obviously you can add or subtract one by flipping a bit. Interestingly, if you flip the remaining bit, it adds or subtracts 3 (mod 8). Thus, aside from the obvious transitions moving up or down one row in the table, we need the following transitions:
    000->010 A->C
    001->101 B->C
    101->001 C->B
    100->110 A->B

    I imagine this might scale up to 15 bits somehow (letting you send lg2(15) bits per day), but I haven’t figured out the details yet.

    Am I on the right track?


  8. I don’t want to ruin for all the others, but you can transmit much more information, even with 3 bits… sorry 🙂
    but you are on the right track, keep refining your method. Maybe it is a good idea to look at the coding again, symbol A has more representations than the other two symbols. usually in those kind of puzzles symmetry is an important property…


  9. Ah, I get it. As long as I was drawing planar diagrams, it was very hard to visualize. As soon as I realized each code is a corner of a cube (or hypercube, for n>3), it became clear. As you say, symmetry is the key. So with 3 bits, you can transmit 4 symbols = 2 bits per day. The solution isn’t thinking “outside the box”, it’s thinking “outside the sheet of paper.”

    This doesn’t work for n=4; you can’t distribute the codes symmetrically unless 2^n divides evenly by n+1, so n needs to be one less than a power of 2.

    It sure is convenient that the transmission happens to be 15 bits. 🙂

    I won’t spoil it completely for others by explaining how to distribute the symbols, but here are some hints:
    – What shape is a “face” of a 15-cube?
    – If there’s more than one way to answer that question, which one is best for the purposes of this problem?

    Thanks again, Nir, for the puzzle, and also for your hints, which were helpful without giving it all away.


  10. Mark,

    So what is the **general** solution? 😉
    Send me an email (you can find it in the “Who’s writing all this stuff” page)


  11. […] Now for the reason you are reading this post… the solution… oh, if you don’t remember the puzzle, please take a few moments to re-read it and understand what it is all about. […]


  12. Hi Nir,

    How much more information can be sent if the spy and his home country are able to record the last 15 transmissions?


  13. The spy can transmit 4 bits using this algorithm. Let the message bits be numbered 1,2,..,15.
    Let b_i denote the parity of all bits in the original message whose number written in binary has the i-th digit equal to 1. If S is the 4-bits secret the spy computes m= S XOR b_4…b_1 and flip the bit numbered m if m>0, or leave the message unaltered if m=0. The decoder can reobtain S= b_4 … b_1, where the b_i have the same meaning above but this time are computed on the received message.

    A very cute puzzle indeed ;-). Ciao!


  14. we divide A14-A0 into A14-A7,A7-A0 and manipulate their parities to send his message:
    A14-A7 A7-A0
    Odd Odd – Symbol 1
    Odd Even – Symbol 2
    Even Odd – Symbol 3
    Even Even – Symbol 4


    • as one bit is common we can change both parties by flipping one bit



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: