Wednesday, 28 June 2017

Communicating using Chessboards!

Any blog such as this must necessarily have a few puzzles. Here's one towards this, which I came across in a recent talk by Paul Cuff. Solving it has been one of my more enlightening moments in the past few months (another equally enlightening moment was standing on the weighing scale to discover how much weight I'd gained).

The puzzle is as follows. There are two parties, Alice and Bob. Alice has access to a chessboard with coins placed on each square. Using this, Alice wishes to send a 6-bit message to Bob. Alice is allowed to flip one coin (among the 64 coins) and upon flipping, the chessboard is made visible to Bob. The question is then to find a strategy that Alice and Bob can agree upon so that Bob can obtain the message on looking at the board.

As a primer, consider the case that the initial configuration (heads up or tails up) of the coins on the board is already known to Bob. A simple strategy here is to map the 6-bit message set to one of 2^6=64 squares, and Alice flips the coin on the square corresponding to the message she wishes to send. Bob then looks at the board, figures out which square has the flipped coin and viola, decodes the message. Sounds too trivial? Read on.

Now suppose that the initial configuration of the coins on the board is not known to Bob. Can Alice still send a 6-bit message? Sounds impossible? Turns out it is possible! Find a strategy for this!

A disclaimer: This problem might take some time to solve. However, the reward/enlightenment on solving it far outweighs the effort involved in doing so. As some of you may have noticed, this problem is notoriously similar to "Dirty Paper Coding".

Find the solution in the comments, solved by one of the legendary puzzle enthusiasts of UCSD, Anant Dhayal. So as to prevent any accidental viewing of the comments, I've filled some space with the famous poem by Robert Frost (which I've incidentally alluded to here).

The Road Not Taken

Two roads diverged in a yellow wood,
And sorry I could not travel both
And be one traveler, long I stood
And looked down one as far as I could
To where it bent in the undergrowth;

Then took the other, as just as fair,
And having perhaps the better claim,
Because it was grassy and wanted wear;
Though as for that the passing there
Had worn them really about the same,

And both that morning equally lay
In leaves no step had trodden black.
Oh, I kept the first for another day!
Yet knowing how way leads on to way,
I doubted if I should ever come back.

I shall be telling this with a sigh
Somewhere ages and ages hence:
Two roads diverged in a wood, and I—
I took the one less traveled by,
And that has made all the difference.