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".

Update: While musing the web, I found this list of puzzles in Prof. Young-Han Kim's webpage. It includes a variant of this puzzle and other equally elegant ones. I encourage the enthusiast to take a look.

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.

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".

Update: While musing the web, I found this list of puzzles in Prof. Young-Han Kim's webpage. It includes a variant of this puzzle and other equally elegant ones. I encourage the enthusiast to take a look.

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.

Bob after receiving the message will extract bit 'i' by calculating the parity of all the 32 locations on the board whose bit-representation has 1 in the position 'i'. Alice will simply see the initial configuration of the board, calculate the subset of bits which need flipping, and then change the exact location which has 1s only on that subset in its bit-representation (in case no flipping is required Alice will change the location '000000').

ReplyDelete- "The puzzle guy"

Nice! Just so as to make your solution a bit more clear to the reader, here's what we do: For each of the 64 positions on the board, we assign a 6-bit number. A heads on a particular square is denoted by a '1' and a tails by a '0'.

ReplyDeleteTo encode, Alice first computes the XOR sum or parity of the 6-bit positions where there is a '1'. Denote the resulting sum by X. Say the intended 6-bit message to send is M. Then, Alice simply flips the coin on the square corresponding to the XOR sum: M+X.

To decode, upon seeing the board, Bob now computes the same XOR sum of the 6-bit positions where there is a '1'. This sum is now M (by virtue of our flipping M+X).