h1

Puzzle #6 – The Spy- Solution

August 28, 2007

This puzzle created some interest, but apart from one non-complete solution which demonstrates the principle only, I didn’t receive any other feedback. Here is my own solution, which is different than the one given in the Winkler book. Naturally, I believe my solution is easier to understand, but please get the Winkler book, it is really that good and you could decide for yourself.

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.

I will (try to) prove that 16 different symbols can be transmitted by flipping a single bit of the 15 which are transmitted daily.
First, for convenience reasons we define the 15-bit transmission as a 14-0 vector.
We will now define four parity functions P0,P1,P2,P3, as follows:

spy_solution1.png

Why these specific functions will be clear in a moment.
Let’s try to view them in a more graphical way by marking above each bit in the vector (with the symbols P0..P3) iff this bit affects the calculation of the respective “P-function”. For example, bit 11 is included in the formula for P0 and P3 therefore we mark the column above it with P0 and P3.
So far so good, but a closer look (diagram below) on the distribution of the “P-functions” reveals why and how they were constructed.

spy_solution2.png

The “P-functions” were constructed in such a way that we have 1 bit which affects only the calculation of P0, one bit which affects only P0 and P1, one which affects only P0 and P2 and so on… Try to observe the columns above each of the bits in the vector – they span all the possible combinations!

From here the end is very close.
The operators on the receiving side have to calculate the P0..P3 functions and assemble them into a 4-bit “word”.
All the spy has to do, is calculate the actual “P-functions” given by today’s random transmission and get a 4-bit “word”. The spy compares this to the 4-bit “word” she wants to transmit and discovers the difference – or in other words: the bits which need to be flipped in order to arrive from the actual “P-functions” to the desired “P-functions”. She then looks up in the diagram above and flips exactly that bit which corresponds to exactly the “P-functions” that she needs to flip. A single bit flip will also toggle the corresponding “P-function/s”.

Since the above wording may sound a big vague, here is a table with some examples:

spy_solution3.png

I have to say this again, This is really one of the most beautiful and elegant puzzles I came across. It is definitely going into “the notebook”…

Advertisements

4 comments

  1. Oh, this is beautiful! By coincidence I was just preparing some slides on Modulo-2 arithmetics for a lecture on introductory switching theory. Perhaps this problem might come in handy as a brain teaser during the break or so 🙂


  2. The beauty of this problem is only evident when trying to solve it from scratch. Try to present this as a teaser and give them the answer only after some weeks…


  3. I have now given them the problem. We shall see if they happen to find this blog by chance if they google for keywords in the problem in their search for a solution 🙂


  4. Nir,
    This is an excellent puzzle and the solution is too good. When I had gone through the solution I had come onto some other interesting thing. The solution can be obtained by using hamming code. Whatever you have kept as the parity functions can be actually done using the hamming code parity functions. Please correct me if I miss something



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: