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.

Solution 1:

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

Solution 2:

This is only a tentative solution, not a complete answer. Still it produces an expectation of $6.076,$ better than any arrived at so far.

Bob guesses $0$ until Alice instructs him otherwise. Bob will follow one of two possible protocols:

Whenever he makes a correct guess, he makes the same guess on the next round. (The Stick protocol.)
Whenever he makes a correct guess, he makes the opposite guess on the next round. (The Change protocol.)

On the first round, Alice guesses $1$ if Bob should follow the Stick protocol, and $0$ if Bob should follow the Change protocol. If Bob's guess is correct, then Alice has told him what to do. If Bob's guess is incorrect, he guesses $0$ on round $2.$ In rounds after the first, when Bob makes an incorrect guess, Alice's guess is what Bob should guess on the next round. I have assumed that Alice should always tell Bob the correct answer for the next round. This seems correct intuitively, but I can't quite see how to prove it.

I can't see any way of computing the expectation but brute force, so I wrote a python script.

def stick(C):
    'Score if the Stick protocol is employed on C'
    # On round 0, Bob guesses 0 and Alice 1 so the round is lost
    # and Bob guesses 0 on round 1
    wins = 0
    Bob = '0'
    for k in range(1,9):
        if C[k]==Bob:
            wins += 1
        elif k < 8:
            Bob = C[k+1]  #Alice tells Bob what to guess 
    return wins

def change(C):
    'Score if the Change protocol is employed on C'
    # On round 0, Bob and Alice guess 0
    # If this is correct, Bob guesses 1 on round 1
    # If it is incorrect, Bob guesses 0
    wins = 0
    if C[0] == '0':
        wins = 1
        Bob = '1'
    else:
        Bob = '0'
    for k in range(1,9):
        if C[k]==Bob:
            wins += 1
            Bob = '1' if Bob == '0' else '0'
        elif k < 8:
            Bob = C[k+1]  #Alice tells Bob what to guess 
    return wins    

results = [ ]
for n in range(512):
    C = bin(n)[2:]
    C=(9-len(C))*'0'+C
    best = max(change(C),stick(C))
    results.append(best)

print('Worst', min(results))
print('Best', max(results))
print('Average',sum(results)/512)

This produced:

Worst 4
Best 9
Average 6.076171875

I can't believe anyone was supposed to produce this answer in an interview, unless he was allowed to write a program. I am not claiming this strategy is optimal. On the contrary, I think it can likely be refined further. Note that it only guarantees $4$ wins.

Solution 3:

This replaces my previous answer. It seems impossible for Alice to give Bob 6 bits of information when she has only 3 bits out of 9 available to do so.

Q2 is rather strangely phrased with "measured by the expectation" and that gave me a clue: this answer is based on timing.

Alice must choose after Bob, so Alice knows when Bob has chosen.
Alice and Bob know the result of each round "just after", so Bob knows how long it took Alice to choose.
An immediate choice by Alice signals 0 and a delayed choice signals 1 to Bob.

Q1. Yes, there is a strategy for them to win at least 6 rounds.

The 9 rounds can be split into 3 groups of 3. Alice uses the first round of each group to tell Bob the answers to the following two rounds.

Round 1: Bob chooses at random. Alice chooses the answer to round 2, using the delay to signal the answer to round 3.

Round 2: Bob and Alice both make the correct choice.

Round 3: Bob and Alice both make the correct choice.

Round 4: as round 1, etc.

This ensures that they always win a minimum of 6 rounds.

Q2. Yes, there is an optimal solution measured by the expectation of the winning rounds.

I was thinking about how Alice could also use timing in rounds 2 and 3 to prevent the result of round 4 being random, when the simple answer hit me. Based on the above strategy, Alice can inform Bob the answer to every round except round 1.

Alice always makes the correct choice.
Alice uses delays to tell Bob the answer to the next round.

This means they will always win 8 rounds, and the first round is 0.5 chance.

If it should be considered uncertain what "just after" means, Alice and Bob could use round 1 to establish the computer's response time, by Alice choosing immediately. That means they "throw" a round and only 7 wins are guaranteed.

(Original answer)

I think the answers are

Q1. There is no guarantee of at least 6 wins.

Q2. There is an optimal solution by prearranged strategy.

They agree that Bob should guess $0$ in each game until Alice tells him otherwise.
As long as the current bit is the same as Bob's guess, Alice chooses correctly and they win the round.
Every time Alice knows that Bob's guess will fail and so they will lose the round, she takes advantage of this to inform Bob of the most frequent value of the remaining bits, by choosing that value.
Bob then changes his choice.

If Bob chooses either at random, always $0$, or always $1$, there will on average be $4.5$ successes. I can only show the result empirically, with the following C program.

The worst single result in my test is $4$ but the average is $5.70$

#include <stdio.h>
#include <stdlib.h>

#define TESTS 40
#define BITS  9

int main(void)
{
    int test, bit, round, count, guess, bob, alice, correct, sum;
    int arr[BITS];
    sum = 0;
    for(test = 0; test < TESTS; test++) {
        guess = 0;
        correct = 0;
        for(bit = 0; bit < BITS; bit++) {
            arr[bit] = rand() % 2;
        }

        for(round = 0; round < BITS; round++) {
            bob = guess;
            if(guess == arr[round]) {
                alice = arr[round];
            }
            else {
                count = 0;
                for(bit = round + 1; bit < BITS; bit++) {
                    count += arr[bit];
                }
                guess = 0;
                if(count * 2 >= BITS - round) {
                    guess = 1;
                }
                alice = guess;
            }
            if(bob == arr[round] && alice == arr[round]) {
                correct++;
            }
        }
        sum += correct;
        printf("%d ", correct);
    }
    printf("\nsum = %d, average = %.2f\n", sum, (float)sum / TESTS);
}

Program output:

6 7 5 5 6 5 6 8 6 7 5 4 5 5 6 8 5 5 5 7 5 5 5 6 6 7 6 5 7 6 5 6 5 5 5 6 4 6 5 7
sum = 228, average = 5.70

I could have seeded the PRNG but chose not to.

9-Bits Game, a Brain Teaser on Information Theory or Cryptography

Solution 1:

Solution 2:

Solution 3:

Related

Recent Posts