9-Bits Game, a Brain Teaser on Information Theory or Cryptography This question was asked in a recently interview, I didn't solve it.

Suppose there are two very smart people Alice and Bob, that participate in a game. The game is set as follows. 


  
  Some computer generates 9 random 0/1 bits in a sequence $C_i, i=1,2,3,...,9$.
  Before the rounds start, Alice takes a look at the sequence and remembers the entire sequence.
  The game has nine rounds. 
  At the start of the i-th round, Bob enters a bit (0 or 1) $B_i$, then Alice enters another bit $A_i$. If $A_i=B_i=C_i$ then they win the round, else they lose.
  Alice and Bob know $A_i,B_i,C_i$ just after the result of the round.
  Round i ends, round i+1 starts, go to step 4.
  


Alice and Bob can develop a strategy before the game starts, but during the game they are not allowed to communicate with each other. 

Q1. Is there a strategy for them to win at least 6 rounds? 

Q2. What is the optimal solution measured by the expectation of the winning rounds?

EDIT:

For Q1, I have some idea. Bob can receive information during the mismatched rounds.

$P_k$ denote the guaranteed winning rounds of totally $k$ round.

Obviously, $P_k \ge \dfrac k2$ when $k$ is even. 

Strategy is simple, $A_i := C_{i+1},B_{i+1} := A_i$, when i is odd. $A_i := C_i$, when i is even.

And we should have the following relationships.

$P_{k+1} \ge P_k,P_{k+1} \le P_k+1$

Easy to prove, $P_1=0, P_2=1$.

When $k=3, 1=P_2 \le P_3 \le P_2+1=2$

We want to testify whether $P_3$ could be 2. 

Considering the extremely bad case, the first round doesn't match. Bob only have 1-bit information, it is impossible to cover every 2-bit case. 

So $P_3=1$

$2=\dfrac42 \le P_4 \le P_3+1=2$, so $P_4=2$.

$2=P_4 \le P_5 \le P_4+1=3$ , we testify if $P_5$ could be 3.

I come up with a rather complex strategy. 

Let $B_1=1$, if $C_1=1$, then everything done. 

If $C_1=0$, $A_1 := \text{most frequent bit in} \{C_2, C_3, C_4\}, B_2=B_3=B_4 := A_1$. 

If $C_2=C_3=C_4$ then done.

If they are not same, suppose $C_2=1,C_3=C_4=0$. Let $A_2:=C_5, B_5:=A_2$, problem solved.
Another post of just thoughts (for now):  The default idea, as has been noted, is basically for Alice to use the first bit to tell Bob whether there are more 1s or more 0s.  Now, Bob may be wrong multiple times if he just keeps guessing $A_1$.  But whenever Bob gets it wrong, Alice's bit can be taken as a bit of information given to Bob.

The interesting observation then is that since Alice knows when Bob will get it wrong, Alice could do as above, but she could also purposely get it wrong early to transfer some extra information.  Then, for example (based on the strategy) Bob might know that he was about to get the next bit wrong (so we haven't lost anything) but also some additional information based on the fact that Alice chose to get it wrong early rather than waiting for Bob to get it wrong.  For example, this could be used to tell Bob that he was about to get the next TWO bits wrong (even given the information that Alice would have given in the first bit Bob would get wrong).  Then, for example, Alice could get it wrong again on purpose during that next bit or two to transmit that it is some kind of worst case scenario like 101010101.  This is hard to turn into an actual strategy but it makes me think there is actually some strategy to guarantee 6.  A naive upper bound on the amount of information given by Alice is something like $2^3 {8 \choose 2}$ since she gives 3 bits of information and can get those bits wrong in two of the last 8 bits.  And this is a decent amount larger than $2^6$.
Probably not the correct answer, but you wrote:


  Before the game start, Alice take a look at the sequence and remember them all


and


  Alice and Bob could develop a strategy before the game start


Since they are both before the game starts, Alice could tell Bob the sequence.

The expected win would be 9 out of 9.