13
$\begingroup$

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.

  1. Some computer generates 9 random 0/1 bits in a sequence $C_i, i=1,2,3,...,9$.
  2. Before the rounds start, Alice takes a look at the sequence and remembers the entire sequence.
  3. The game has nine rounds.
  4. 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.
  5. Alice and Bob know $A_i,B_i,C_i$ just after the result of the round.
  6. 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.

$\endgroup$
12
  • $\begingroup$ Does question 1 mean a strategy to ensure $6$ or a strategy to give an expectation of $6$ wins? $\endgroup$
    – saulspatz
    Commented Jul 29, 2018 at 17:23
  • $\begingroup$ @saulspatz At least 6 wins. So the expectation should exceed 6. $\endgroup$
    – FDR
    Commented Jul 29, 2018 at 17:30
  • 1
    $\begingroup$ Does Alice know the value of $B_i$ before she enters $A_i$? $\endgroup$ Commented Jul 29, 2018 at 17:39
  • 1
    $\begingroup$ @DavidC.Ullrich It depends. If they make an agreement beforehand, say $B_i = A_{i-1}$, then Alice certainly knows the value of $B_i$ $\endgroup$
    – FDR
    Commented Jul 29, 2018 at 17:43
  • $\begingroup$ @DavidC.Ullrich rule 5 says that Alice does not know Bob's choice until after the round. $\endgroup$ Commented Jul 29, 2018 at 18:53

5 Answers 5

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Why not just tell the next bit with the first bit? $\endgroup$
    – kelalaka
    Commented Oct 4, 2018 at 14:06
  • $\begingroup$ @kelalaka You're not getting enough information that way. You have to somehow get more than one bit of information out of a single bit. $\endgroup$
    – Carl
    Commented Oct 5, 2018 at 15:03
  • $\begingroup$ Yes yes, contradicting to the 4th rule. $\endgroup$
    – kelalaka
    Commented Oct 5, 2018 at 19:14
1
$\begingroup$

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:

  1. Whenever he makes a correct guess, he makes the same guess on the next round. (The Stick protocol.)
  2. 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.

$\endgroup$
2
  • 1
    $\begingroup$ "I would say that it takes one bit of information to tell Bob the right answer for a round" I was thinking along those lines as well. But in fact a one-bit message is enough to guarantee that Bob gets at least four later rounds correct. See the non-answer I'm about to post... $\endgroup$ Commented Jul 30, 2018 at 13:41
  • $\begingroup$ @DavidC.Ullrich Think outside the box, right. $\endgroup$
    – saulspatz
    Commented Jul 30, 2018 at 14:37
0
$\begingroup$

Not an answer. Some thoughts, followed by a simple example showing that those thoughts can't be quite right.

I was thinking that perhaps one could get upper bounds by reasoning like so:

Fuzzy part: Assume the rounds are divided into two categories, the ones where Alice tries to win by saying $A_j=C_j$ and the ones where she tries to send Bob a message about what to do in later rounds. Say the number of rounds she tries to win is $w$.

Wrong part: Then she can send only $9-w$ bits of information to Bob, so she can only guarantee he gets $9-w$ rounds right. Hence they cannot guarantee more than $\min(w,9-w)\le 4$ rounds right.

Example Strategy: Say $n$ is the number of $j\ge2$ with $C_j=1$. Alice says $$A_1=\begin{cases}1,&(n>4), \\0,&(n<4), \\C_1,&(n=4).\end{cases}$$

Then Bob chooses $B_j=A_1$ for all $j>1$.

If $X$ is the number of wins this ensures $X\ge4$. Which doesn't contradict the conclusion of the bogus argument above, but it does show that the reasoning isn't right: We ensured $X\ge 4$ with just one bit of information.

Working out $E[X]$ for this strategy seems like a bit of combinatorics. Perhaps several bits...

$\endgroup$
1
  • 1
    $\begingroup$ We can improve on this idea. See my comment on Weather Vane's answer. $\endgroup$
    – saulspatz
    Commented Jul 30, 2018 at 15:03
0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ I feel sure that the interview question was asked, because there is a solution to always achieve at least 6 correct rounds. My answer obtained $5.70$ correct rounds on average. There are 9 rounds, 6 of which must be correct. That leaves the first 3 rounds for Alice to tell Bob the future she knows, which requires informing a sequence of 6 bits. Having said that, I don't believe that it was an "interview question". I can't figure it out, but can anyone take this further? $\endgroup$ Commented Jul 29, 2018 at 21:30
  • 1
    $\begingroup$ Good idea, but I it can be refined further. Here's an example. Suppose Bob's guess in round 4 will be incorrect, so that Alice will inform what to guess from now on, at that $(C5,\dots,C9) = (0,0,1,1,1).$ If Alice tells Bob to guess the most frequent remaining values, $1,$ they will wing $3$ more rounds. She should tell him to guess $0$, and in round $7$, when he's wrong, tell him to guess $1$. That way, they win four more rounds. I don't see a simple way to formalize this. It seems like a dynamic programming problem. $\endgroup$
    – saulspatz
    Commented Jul 30, 2018 at 15:02
  • $\begingroup$ Maybe we just say, whenever Bob's guess is right, he makes the same guess on the next round. Whenever Bob's guess is wrong, Alice's guess is what he should guess on the next round. That would cover the case in my previous comment. $\endgroup$
    – saulspatz
    Commented Jul 30, 2018 at 15:12
  • 2
    $\begingroup$ This is a clever solution, and may well be what the interviewer intended, but in my view, it violates the rule that they may not communicate. If this is valid, why isn't it valid for Alice to hold up fingers to indicate the next number? +1 for originality, though. $\endgroup$
    – saulspatz
    Commented Jul 31, 2018 at 12:24
  • 2
    $\begingroup$ Not true. Bob is told Alice's guesses. In the context of the puzzle it is clear that "not communicate" means that they can have no communication other than this. Various answers have shown how the players can do better than random using only this information. $\endgroup$
    – saulspatz
    Commented Jul 31, 2018 at 12:30
-1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Sorry. I made a mistake. Bob didn't know the sequence. $\endgroup$
    – FDR
    Commented Jul 29, 2018 at 17:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .