Consider the following game. Let $n$ be a positive integer. There are two players, $\newcommand\A{\mathrm{A}}\A$ and $\newcommand\B{\mathrm{B}}\B$, and a referee.
- $\A$ and $\B$ first agree on a strategy. After this step, $\A$ and $\B$ cannot communicate.
- Initially, the referee chooses a sequence $\{c_i\}$ of length $n$, where each entry is either “black” or “white”. $\A$ is made aware of this entire sequence, but $\B$ is not.
- There are a series of $n$ rounds, where $\A$ and $\B$ simultaneously guess either “black” or “white”. During the $k^\text{th}$ round, the team wins a point if $\A$’s guess and $\B$’s guess are both equal to the $k^\text{th}$ entry of the referee’s sequence.
- After each round, $\B$ is told what $\A$’s guess was, and what the referee’s pick was, for that round. This means $\B$ makes each decision while aware of all information from previous rounds.
Find a strategy for $\A$ and $\B$ so that they can guarantee winning $g(n)$ times, where $\lim\limits_{n\to+\infty}\frac{g(n)}n=\frac34$.
I have a strategy for which $\lim\limits_{n\to+\infty}\frac{g(n)}n=\frac35$. We will prove that $\A$ and $\B$ can win $3$ times in $5$ games. Here is the strategy. In the first game, $\A$ will guess the color that appears more in the subsequence $(c_2,c_3,c_4)$, and $\B$ will guess this color in game $2$ to $4$. If $c_2=c_3=c_4$, then $\A$ and $\B$ can win games $2$ to $4$ (so $3$ games have been won). Otherwise, $\A$ and $\B$ will lose exactly one game among $2$ to $4$. But $\A$ knows which game that will be, so they can guess $c_5$ in that game so that $\A$ and $\B$ win the fifth game.
I have no strategy for which $\lim\limits_{n\to+\infty}\frac{g(n)}n=\frac34$ though.
Best Answer
This problem is analyzed in the paper Online Matching Pennies, by Gossner, Hernandez, and Neyman, available at this link. They prove that the upper limit for the proportion of rounds won is $x^*$, where $x^*\in (0,1)$ is the unique solution to $$ x^*\cdot \log_2(\tfrac1{x^*})+(1-x^*)\cdot \log_2(\tfrac1{1-x^*})+(1-x^*)\cdot \log_23=1. $$ That is, for any $x<x^*$, there exists a strategy for which $\lim_{n\to\infty} g(n)/n=x$. You can calculate $x^*\approx 0.8107$. This shows that a ratio of $3/4=0.75$ is attainable. However, the paper only gives a probabilistic proof of this fact. In what follows, I will give an explicit strategy which shows how to attain $\lim_n g(n)/n=3/4$.
Define a covering code $C$ of length $\ell$ and distance $d$ to be a subset $C\subseteq \{0,1\}^n$ such that, for any word $w\in \{0,1\}^n$, there exists $c\in C$ such that $w$ and $c$ differ in at most $d$ places.
For an example with $\ell=3$ and $d=1$, $C=\{000,111\}$ is an $(\ell,d)$-covering code. Given $w\in \{0,1\}^3$, if $w$ has two or more zeroes, then $w$ is covered by $000$; otherwise, $w$ is covered by $111$.
We can use covering codes to construct strategies for the black and white game.
Proof: We divide the entire process into blocks of length $\ell$. During each block, player $B$ will play a sequence which is equal to the codeword signaled by $A$ in the previous block. This codeword will agree with the referee's sequence in at least $\ell-d$ spots. Meanwhile, player A will choose a sequence which agrees with the referee's sequence and B's sequence at $m$ spots. There will be at least $\binom{\ell-d}{m}\cdot 2^d$ ways for $A$ to make this choice. $A$ uses this freedom to tell $B$ a codeword which agrees with the referee's next block of $\ell$ in at least $\ell-d$ places.
Here is how $A$ sends the message. Let $L$ be the set of rounds in the current block, so $|L|=\ell$. The players first agree on a partitioning of $L$ into two sets $D$ and $E$, so $L=E\cup D$ and $|D|=d$ and $|E|=\ell-d$. The only requirement is that all of the rounds where $B$ guessed incorrectly must be placed in $D$.
First, $A$ will choose a subset $M\subseteq E$ such that $|M|=m$. For each round in $M$, $A$ will guess correctly, earning the team a point, while $A$ guesses incorrectly for the rounds in $E\setminus M$. There are $\binom{\ell-d}m$ ways that $A$ can choose $M$.
Second, during all of the rounds in $D$, $A$ will simply use her guesses to send $B$ a binary sequence of length $d$, with $2^d$ options.
Since $A$ can make $\binom{\ell-d}{m}\times 2^d$ messages, and since $\binom{\ell-d}{m}\times 2^d\ge |C|$, $A$ has enough freedom to communicate a codeword in $C$ which differs in at most $d$ places from the referee's next block of $\ell$. Furthermore, during each round except the first, the team gets $m$ points out of $\ell$, proving an asymptotic ratio of $m/\ell$. $\tag*{$\square$}$
Let us consider an example of applying this claim. When $\ell=3, d=1$, we saw before that $C=\{000,111\}$ is a covering code. Letting $m=2$, we check the requirements of the claim: $$\binom{\ell-d}{m}\cdot 2^d=\binom{3-1}{2}\cdot 2^1=2=|C|,$$ so the requirement is satisfied. The claim gives a strategy with ratio $m/\ell=2/3$. This strategy is similar to the one you came up with; during each block of $3$, $A$ uses one bit to communicate the majority of the next block of $3$, while $B$ guesses the majority color each time (which was communicated during the previous round).
However, to attain a ratio of $3/4$, we need a much larger code. There is a summary of the best known covering codes at Gerzson Kéri's website, which goes up to length $33$ and distance $10$. I searched through the whole table, and I found that the simplest code which could attain a ratio $3/4$ was the code with length $24$ and distance $3$, consisting of $2^{13}=8192$ codewords. Calling this code $C$, we can obtain $C$ by modifying the binary Golay code, $G_{23}$ (wikipedia). Specifically, $$ C=\{v\oplus b \mid v\in G_{23}, b\in \{0,1\}\} $$ Here, $\oplus$ is the concatenation operation. That is, you extend $G_{23}$ by appending a $0$ to all vectors, and appending a $1$ to all vectors, thereby doubling the number of codewords, while preserving the covering distance of $3$. Letting $m=18$, we check the conditions of the claim are satisfied: $$ \binom{24-3}{18}\cdot 2^3=10640>2^{13}=|C|, $$ We can then apply the claim to get a strategy with a ratio of $18/24=3/4$.