{\huge One Flip Sends Many Bits}

Another coins on a chessboard puzzle \includegraphics[width=1.15in]{HouYifanMauriceAshley.jpg}

Hou Yifan and Maurice Ashley are champions of chess in several senses. Hou just regained the Women's World Champion title by defeating Mariya Muzychuk of Ukraine 3-0-6 in their match which ended today in Lviv. Along with her male Chinese compatriots who reign as Olympiad team champions, she headlines an extraordinary growth of the game in southeast Asia. Ashley became the first ever grandmaster to play a tournament in Jamaica where he was born and has been one of the game's premier video commentators and ambassadors for over two decades. The past two years he teamed with entrepreneur Amy Lee of Vancouver to create and run the Millionaire Chess open tournaments in Las Vegas, to raise the professional profile of the game.

Today Ken and I present another puzzle in our ``Coins on a Chessboard'' series, theming it after Ashley's ``Millionaire Square'' promotion.

These are exciting weeks in Chess and in Go. Besides the women's championship match, the World Chess Federation (FIDE) Candidates' Tournament to determine the next challenger to world champion Magnus Carlsen started Friday in Moscow. Former world champion Viswanathan Anand of India, the oldest player at 46, shares the lead with Levon Aronian of Armenia and Sergey Karjakin of Russia, each with a win and two draws, A major international Open is taking place in Reykjavik, 44 years on from the famous match between Boris Spassky and Bobby Fischer. The fifth and final game of the Go match between Google DeepMind's AlphaGo program and world \#4 Lee Sedol will start ad midnight ET; Sedol has lost the series at 3-1 down but will try to build on his Game 4 win.

Millionaire Chess brought the first ever $1,000,000 total prize fund to a long weekend of open chess. As customary at many events, the tournament is divided into sections by rating class, so that amateur players have a shot at the biggest prizes. Last October's event introduced the ``Millionaire Square'' finale in which the nine section winners played a quiz-game show to give one a chance to win a separate $1M prize underwritten by the sponsors by guessing which of 64 squares it was ``under.'' The winner guessed c4 but it was b1. I do not know if this promotion will be brought back for the 2016 tournament at Harrah's in Atlantic City, but it gave Ken a neat way to re-phrase the puzzle from the source given by a student in my discrete math class.

\includegraphics[width=3in]{chessboardcoins.png}

The Puzzle

Suppose ``Millionaire Square'' is presented in this glitzy manner next October: A chessboard is set out with 64 gold coins bearing the Harrah's logo (``heads'') on one side and the Millionaire Chess logo (``tails'') on the other. The prize is under one of the squares. The coins are randomly arranged heads or tails. The lucky finalist is led out from a blind never having seen the board before, picks a coin, and wins if he or she chose the right square. Like last October it's a 1-in-64 shot.

Now suppose this is presented to the audience with extra pizzazz. A staffer comes out first, picks up one of the coins, shows both sides to the audience, and puts it back on the square. The coin is set back just like all the other coins except it might now be heads instead of tails, or tails instead of heads. Is this secure?

Suppose the staffer knows the right square and wishes to give it away, perhaps out of grudge or hope of hitting up the winner later. The staffer has no contact at all with the contestant, who knows nothing except perhaps having read this GLL post, and sees nothing except the final arrangement of the coins. Can the staffer communicate the winning square just by having flipped one coin, and if so, how? That is the puzzle.

Note that the employee has no control over the setup of the coins which is completely random. The configuration after flipping one coin was just as likely as the original to be chosen randomly. So how can six bits of information have been transmitted?

Toward a Solution

I shared this puzzle with Vipul Goyal when he visited Tech last month. He is currently at Microsoft Research in India and does strong research in cryptography, security, and privacy---not surprising since he did his PhD at UCLA under Rafail Ostrovsky and Amit Sahai. It took awhile for him to understand why it could even remotely be soluble, but that evening he sent me a complete solution. Impressive. He has given permission for me to relate it. First, let me re-phrase the puzzle not in Ken's way or the source's way with a jailer and two prisoners, but in simple complexity terms:

Alice receives a string $latex {X}&fg=000000$ of length $latex {n=2^{k}}&fg=000000$. She also receives an index $latex {i}&fg=000000$ in $latex {\{1,\dots,n\}}&fg=000000$. She must flip one bit of $latex {X}&fg=000000$ so that when Bob gets the resulting string $latex {X'}&fg=000000$ he always can get $latex {i}&fg=000000$.

Now here is how Alice can send one bit, namely whether $latex {i}&fg=000000$ is even or odd. If $latex {i}&fg=000000$ is odd and $latex {X}&fg=000000$ has an even number of 1's in the first half, she flips a bit in the first half, likewise if $latex {i}&fg=000000$ is even and $latex {X}&fg=000000$ has an odd number of 1's in the first half. Otherwise she flips a bit in the second half. Then in $latex {X'}&fg=000000$ the parity of $latex {i}&fg=000000$ and the parity of the count of $latex {1}&fg=000000$s in the first half always agree. Thus Bob has narrowed down the possibilities by half. In chessboard terms this is like choosing to flip a coin on White's side or Black's side of the board.

Now imagine this scheme using the odd versus even positions in $latex {X}&fg=000000$---which is like light versus dark squares on the chessboard---or using the right and left halves of the board. Can we combine these schemes to communicate more bits? If you're aware of Hamming codes, you might realize that if $latex {X}&fg=000000$ is initially a codeword, any bit flip will be detectable since the code will correct any one error. But what if $latex {X}&fg=000000$ is not a codeword? It still needs setting the details down precisely.

Goyal's Solution

Our source has its own solution and there are others, but let's see Vipul's. Denote the input string (to Alice) by $latex {X}&fg=000000$, where $latex {|X| = n = 2^k}&fg=000000$. Let $latex {X[i]}&fg=000000$ denote the $latex {i}&fg=000000$-th bit of $latex {X}&fg=000000$.

We will define sets $latex {S_1, \ldots, S_k}&fg=000000$. Each set will contain a subset of the $latex {n}&fg=000000$ bits from $latex {X}&fg=000000$ (denoted by their positions in $latex {X}&fg=000000$). Denote the parity of all the bits in $latex {S_i}&fg=000000$ by $latex {P_i}&fg=000000$. The $latex {k}&fg=000000$ bit string that Alice will transmit to Bob will be $latex {P_1, P_2, \ldots, P_k}&fg=000000$. The primary challenge will be to choose the sets $latex {S_1, \ldots, S_k}&fg=000000$ in such a way that exactly by flipping one of the bits from $latex {X}&fg=000000$, all the parities can be set to any desired value.

Now I will describe how to construct these sets. The key observation is the following. Alice would like to flip the parity of a collection of these $latex {k}&fg=000000$ sets. That means for every such collection, there must exist a unique bit in $latex {X}&fg=000000$ which is exactly in all the sets from this collection but not in the sets outside this collection. There exist $latex {2^k}&fg=000000$ such collections. And this is also exactly the number of bits in $latex {X}&fg=000000$. Hence, it appears to be possible to have such sets. These sets are constructed as follows. A bit $latex {X[i]}&fg=000000$ is in set $latex {S[j]}&fg=000000$ iff the $latex {j}&fg=000000$-th bit of $latex {i}&fg=000000$ is 1.

Denote the original $latex {k}&fg=000000$-bit parity string for the sets to be $latex {P_{original}}&fg=000000$ and the $latex {k}&fg=000000$ bit string that Alice wants to communicate to Bob to be $latex {P_{final}}&fg=000000$. Let $latex {C = P_{original} \oplus P_{final}}&fg=000000$. Now the parity of $latex {S_i}&fg=000000$ must be flipped iff $latex {C[i]}&fg=000000$ is 1. We will simply flip the bit $latex {X[C]}&fg=000000$ and observe that $latex {X[C] \in \{S_i\}_{C[i] = 1}}&fg=000000$ but $latex {X[C] \notin \{S_i\}_{C[i] = 1}}&fg=000000$ (by construction).

Open Problems

Did you know this fact about communication? Are there any possible applications that come to mind?

Incidentally, today is Pi Day 3/14, indeed rounded Pi Day 3/14/16. Georges-Louis Leclerc, Comte de Buffon, famously showed how to approximate $latex {\pi}&fg=000000$ probabilistically by randomly throwing a needle the width of one tile on a square-tiled floor and counting whether it crosses a vertical side of a square. Suppose we randomly toss a coin on the floor instead. Depending on the width of the coin relative to a tile---assuming it's a rational number---can we ever get an estimate for $latex {\pi}&fg=000000$ that way?