Strategy to beat the Casino

Question

Two players, $A$ and $B$, and the Casino play a game. It involves showing zeros or ones: each player picks $0/1$ and also the Casino picks $0/1$.

• If the Casino and both players $A$ and $B$ show the same number ($000$ or $111$), then the two players win the game.
• But in case not all three chosen numbers are identical, the Casino wins.

Altogether there are nine rounds. Now it happens that player $A$ is going to learn some illegal information, just seconds before the game starts: $A$ is going to learn the Casino's choice for each of the coming nine rounds. Unfortunately, there is no way of communicating this information to player $B$ without the Casino noticing. The only way of communicating is via the cards chosen by $A$.

The evening before this game, $A$ and $B$ meet and agree on a common strategy. Is there a strategy that guarantees them to win at least $5$ of the $9$ rounds? And is there a strategy that guarantees at least $6$ wins?

Answer 1

By using Joel Rondeau's strategy as a base, plus some kludgy patchwork, we can get a strategy that always gets at least 6 wins.

For reference, this is his strategy:

Leader Rules:
1. To start, play 0 until the first round the casino doesn't play 0.
2. Look ahead the next 3 rounds. Play the value that the casino plays in the majority of the 3 rounds. This tells the follower what to play in his step 2.
3a. If you will only win 2 of the 3 rounds, look ahead to the 3 rounds after and play the majority value in the round you will lose. Play the winning value in the other 2 rounds. Go to step 3 (a or b).
3b. If you will win all 3 rounds, play the winning value in all 3 rounds and keep playing it until you won't win. Go to step 2.

Follower Rules:
1. To start, play 0 until you lose a round.
2. Play the value played by the leader in the last round that was lost. Do this for 3 rounds.
3a. If you only won 2 of the 3 rounds, do step 2 again.
3b. If you won all 3 rounds, keep playing the value until you lose a round. Do step 2 again.

His strategy clearly nets at least 5 wins. The question is, when does it fail to net 6 wins (or, equivalently, when does it score exactly 5)?

Divide the 9 rounds into 4 groups as follows: 1 222 333 44.
It turns out that Joel's strategy scores exactly 5 if and only if the first play by the Casino is a 1, and none of groups 2 to 4 contain only one choice repeated multiple times.

How can we patch that?

The only cases we need to patch are the ones in which groups 2 and 3 contain a 2/1 split, and group 4 contains a 1/1 split. If that doesn't happen, then Leader follows the original set of rules. In the remaining cases, we will need to do something that deviates from the original strategy as soon as possible, so that follower will have time to react to it. We will do that by sacrificing some points:

Case 1: Group 3 is of the form ABA
In this case, we will intentionally give the minority bit in round 1 (the second player will be able to tell you gave him the wrong bit after round 4). We will lose two of the three rounds in group 2, so we have two free bits of information: with the first of them, identify the first bit of group 3, and with the other one identify the first bit in group 4. This uniquely determines groups 3 and 4.

Case 2: Group 3 is AAB or BAA and Group 4 is 01
We will now roughly follow the initial strategy, with one exception: if group 3 is AAB, in the first round of group 2 that the majority bit is played by the casino deliberately play the other bit instead. If group 3 is BAA do the same, but in the second round. This, coupled with the value of A you will give as normal (in the round the minority bit is played), uniquely determines groups 3 and 4.

Case 3: Group 3 is AAB or BAA and Group 4 is 10
3a) Group 3 is AAB
Play rounds 1 to 5 as normal, but play B in round 6 instead. You only miss round 6 in this case, so the second player is able to deduce the correct play for the last 3 rounds.

3b) Group 3 is BAA
Play rounds 1 to 4 as normal, except that you should flip the answer to the losing round of R2-R4. Then play A in round 5. This is the only case in which you miss round 5, so the second player can determine that he should switch the bit for the next two rounds.

According to the new leader strategy, we can rewrite the follower rules. As some notation, ~A is the value that is not A (so ~1 is 0 and ~0 is 1). Rules added in bold:

1. To start, play 0 until you lose a round.
2. Play the value played by the leader in the last round that was lost. Do this for 3 rounds, unless 3d or 3e happens.
3a. If you only won 2 of the 3 rounds, do step 2 again.
3b. If you won all 3 rounds, keep playing the value until you lose a round. Do step 2 again.
3c. If you won only 1 round, go to Exception 1.
3d. If you played the same value as the Casino, but Leader didn't, and you're at or after Round 5, go to Exception 2.
3e. If you played the same value as the Casino, but Leader didn't, and you're before Round 5, go to Exception 3.

Exception 1. Look at the bits played in the last 2 rounds you lost. Let those be A and B. Play the next 5 rounds as: A ~A A B ~B.
Exception 2. Let the bit you played in the last round you lost be A. Play ~A until round 7, then play 1 0 in rounds 8 and 9.
Exception 3. Play the same bit you played in the last round until round 4. Let A be the bit Leader played in the last round that the Casino played a different bit than you did. If you had already won a round when you came to this exception, play ~A A A 0 1 for the last 5 rounds. Otherwise play A A ~A 0 1.

Answer 2

To get 5 of 9, the players can use the following system:

Let's define the 2 players as the Leader (who knows what the casino will play) and the Follower.

Follower always plays 0 for the first round. If Leader knows Casino will also play 0 in R1, Leader plays 0 and they win the first round, and the rest is trivial: in each even round the Leader simply informs Follower what to play in the next odd round. For example, in R2 Leader plays the bit Follower should play in R3, in R4 Leader plays the bit Follower should in R5, etc. Leader always plays the correct bit in the odd rounds too and they are guaranteed to win all the odd rounds, for a minimum of 5 rounds. (In even rounds it doesn't matter what Follower does, it could be a random bit.)
If they lose the first round, Leader plays R1 with the bit that Follower should start with in R2. Follower continues to play that bit until the game ends, or if in the first round that they lose, if Leader played a different bit, this signals to Follower to switch bits after winning 3 rounds. This will guarantee that they win at least 5 rounds.

Proof that this works when they lose the first round: With 8 rounds remaining, there are 2 possible situations that are relevant here. There are 5 or more of either 1 or 0, or there are 4 of each. In the case of 5 or more of one bit, Leader just plays that bit in R1 and they both play that bit for the rest of the game, guaranteeing at least 5 wins. When there are 4 of each bit remaining, after 5 rounds they are guaranteed to win 3, and with 3 rounds remaining they will be guaranteed to win 2 if they switch bits. Leader simply needs to switch a bit during one of the losing rounds (which will be somewhere in R2-R6) to inform Follower to switch after 3 wins.

I think this strategy can be tweaked for getting 6 out of 9, but it's not perfect yet:

Continuing with the "lose the first round with 4/4 distribution remaining" scenario, after 5 rounds, in the worst case you have only won 3, and you have to win the last 3. Since there are 2 losing rounds in rounds R2-R6, there are actually 3 pieces of information that can be passed:
- 1st losing round bit flipped and not 2nd losing round
- 1st losing round bit not flipped and 2nd losing round flipped
- both losing round bits are flipped
Now each of those 3 scenarios can be assigned to a round: R7, R8, R9. That is the round that is unlike the other 2, so Follower would know to flip that round's bit.
Hmmm, this seems to fail when we have a 5/3 split instead of 4/4. Still working on it...

Answer 3

I have an answer that is similar to TTT's answer and always gets you $5/9$, but sometimes fails to get $6/9$. I'm hopeful that it can be tweaked to always get $6/9$ but I haven't figured that part out yet. It has a simple set of rules:

Follower Rules:

1. To start, play 0 until you lose a round.
2. Play the value played by the leader in the last round that was lost. Do this for 3 rounds.
3a. If you only won 2 of the 3 rounds, do step 2 again.
3b. If you won all 3 rounds, keep playing the value until you lose a round. Do step 2 again.

Leader Rules:

1. To start, play 0 until the first round the casino doesn't play 0.
2. Look ahead the next 3 rounds. Play the value that the casino plays in the majority of the 3 rounds. This tells the follower what to play in his step 2.
3a. If you will only win 2 of the 3 rounds, look ahead to the 3 rounds after and play the majority value in the round you will lose. Play the winning value in the other 2 rounds. Go to step 3 (a or b).
3b. If you will win all 3 rounds, play the winning value in all 3 rounds and keep playing it until you won't win. Go to step 2.

Examples:

Case 1: Casino will play 000000000
Leader and follower will both play 9 0's and win 9 times.

Case 2: Casino will play 01 010 101 0
Leader will play 00 010 101 0
Follower will play 00 000 111 0
They win 6 times.

Case 3: Casino will play 1 010 101 01
Leader will play 0 010 101 0X
Follower will play 0 000 111 00
They win 5 times.

Where it fails:

It always gets $5/9$ but fails to get $6/9$ in many cases where the casino starts with 1 and ends with 01 or 10.

Answer 4

Here is an alternate way to get six rounds correct out of nine

This answer.
It was actually created to solve nine rounds out of thirteen, thus answering this followup question.
It generalizes to 3N rounds correct out of 4N+1, so you can actually scale it downwards to get six rounds out of nine, or three out of five.
In fact any other answer to "Master and Slave versus Bob: hard version" could also be used to do the same thing, the puzzle was created for that reason. But at the time of writing mine is the only answer.

Answer 5

The Question is not clear, WHEN does B know wich card was choosen by A? I'll assume the cards are showed at same time, so B(X) only knows A(X-1).. X is obviously the time. (Of course if question is made more clear I'll update the answer).

A and B agree on 4 sequences

X)  xx1111000   encoded as 0 1
Y)  xx0000111   encoded as 1 0
Z)  xx1111111   encoded as 0 0
W)  xx0000000   encoded as 1 1

The first 2 cards played by A encodes one of the sequences. So B have to play one of the 4 sequences, however, A may at any time make an arbitrary mistake, B then knows it has to change sequence (in example take the next sequence).

So in example if the casino plays 001100011 A has to to play 01, then B starts playing the sequence X, then A plays 110, wich means B will play 111 so 2 correct results and 1 error, after that B see A making an error and both will play 0111 (wich are numbers from the next sequence Y) wich will results in additional 3 correct answers. So we have 5 correct results.

By bruteforcing most times we see we have 6 (or more) correct results and 5 correct results sometimes, but I believe that with the correct 4 starting sequences I can get 6 all the times (still refining that).

I can also encode more information, in example if A makes 2 consecutive mistakes, then B knows it has to switch to sequence by +2 (wich means going backward once compared to original sequence), However I would like to find an optimal strategy without having to bruteforce that, probably I should use something like Grey code..

Further improvment area, if the 2 sequences are sorted by first 2 digits, it is possible that the first move of A will help B in selecting the second move, wich gives another +1..