Puzzle 7 : Writing on dirty paper

(from RAW-T)

You have blank piece of paper, divided up into n=64 blocks. You have enough 'power' to perform k=1 operations on the paper. An operation would be either erasing or coloring in k of the n blocks.

You hope to communicate with whoever is going to read the paper the next day. You can meet up before hand and decide a strategy. Unfortunately, the adversary knows your strategy.

This adversary can fill in the blocks however he (or she) chooses. How many bits of information can you communicate ?

To illustrate, suppose there is no adversary. Then you have 64 possible messages, [1000..00],[010...0000].....[00...00001] and can thus communicate log(64) bits.

What if, in general, k=nR, for some fraction R<=1 ?

This is a special case of the problems of dirty paper coding, coding with channel information and information embedding which are very important in information theory!