Strategy to beat the Casino reversed

Question

Let's consider Strategy to beat the Casino puzzle, but reverse it - fix number of losses and ask a question about amount of rounds:

Two players, A and B, and the Casino play a game. The game consists of $N$ rounds. $N$ can be chosen by players.

Each round 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 ([0,0,0] or [1,1,1]), then the two players win the round. Otherwise - the Casino wins.

The players have to play all $N$ rounds, but if they lose at least $M=5$ times - the Casino will kill them. Ha-ha.

Player A is going to learn the Casino's choice for all incoming rounds right before the game starts. Unfortunately, the only way of communicating this information to player B is via the numbers chosen by A.

The evening before the game, A and B meet and agree on a common strategy and on amount of rounds to play. What is the biggest $N$ they can pick with no danger to lives?

For example, a trivial strategy would be each odd round to communicate what Casino will chose in the next round. Then they can play $N$=8 rounds, while losing 4 at most.

It's pretty easy to figure out how to win 8 out of $N$=12. But can we do 9 out of $N$=13? If not - prove it, if yes - what's the strat?
Also, can we prove that $N$=14 is not achievable? (Unless it is magically is...)

Answer 1

(Summary at the very bottom)

After many sleepless nights and much contemplation, I believe I have finally created a strategy to guarantee 9 out of 13 games.

I want to give credit to Joel Rondeau (who's strategy is the basis of my work), ffao who created the solution for winning 6 out of 9 games (improving on Joel's strategy). Credit is also due to Bennett Bernardoni who solved 8 out of 12 games and also showed that there can be "composite" deviations from Joel's strategy aside from the main 20 deviations you can typically find in a 9 of 13 game.

Before digging into my solution, I should clarify notation. As mentioned, my work is based on Joel's strategy which breaks the rounds into groups of three, starting with the second round (for a 9 of 13 game, the groups are 1 222 333 444 555: round 1 is in group 1; rounds 2,3 and 4 are in group 2; rounds 5,6 and 7 are in group 3; and so on). Sometimes I will need to describe a group by its form and for that I will be using A and B with X as a wild card (eg. saying group 3 is of the form ABA means that its rounds are either 101 or 010. Saying that group 2 is of the form AAX means it could be 110 or 111, 001, or 000).

I won't repeat the details of Joel's strategy in particular, but as shown by ffao, there's two main ways to deviate from his strategy; either through signaling a minority number in the next set, or by purposely "throwing" a round you normally would have won. To clarify, I consider "throwing a round" as Player A playing the opposite number when both player B and the casino are playing the same number. This is different to "signaling" where player A can "signal" either 0 or 1 when Player B and the casino are playing opposite numbers.

With that out of the way, let's get into the details of my solution.

Part 1:

We start by confirming that Joel's strategy with ffao`s modifications will guarantee 9 of 13 wins under either of the following conditions:
#1. If the casino plays a 0 on the first round.
#2. If the casino plays a triplet in any group (plays the same number in all three rounds of that group).

It is easy to prove condition #1 as playing 0 on round 1 will lead to a win for the players under Joel's strategy. The rest of the game effectively becomes an 8 of 12 game, which Joel's strategy with ffao's modifications can guarantee (as proven by Bennett Bernardoni). Thus in all future analysis from here on out, we can ignore the scenarios where the casino plays 0 on round 1.

Condition #2 is a bit tougher to prove:
- If the triplet is in group 5, Joel's strategy can be played as usual.
- If the triplet is in group 2, Joel's strategy can be played as usual for the first four rounds. Starting from round 5, the game effectively becomes a 6 of 9 game, which Joel's strategy with ffao's modifications can guarantee.
- if the triplet is in group 4, Joel's strategy will not work as by the time you finish round 10, the game effectively becomes a 2 of 3 game, which Joel's will loose against if, and only if, round 11 is not the same as the triplet and rounds 12 and 13 are either 01 or 10. We can account for these two possibilities by throwing either of round 9 or round 10. With this modification, Joel's strategy will guarantee victory if the triplet is in group 4.
- If the triplet is in round 3, Joel's strategy will again not work as by the time you finish round 7, the game effectively becomes a 4 of 6 game, which Joel's will loose against if, and only if; round 8 is not the same as round 7; rounds 9, 10, and 11 are of the form AAB, ABA or ABB; and rounds 12 and 13 are either 01 or 10. A total of 6 possible cases in which Joel's strategy will fail. If we apply ffao's modifications we can account for 2 of these 6 cases (throwing either round 9 or 10) and if we throw round 7 we can account for another 2 of these cases. To account for the last 2 cases, we have to throw round 6. However this throw in round 6 must force player B to play opposite what he normally would have played on round 7 (for reasons that will become apparent later).

We will call these deviation strategies "triplet modification strategies" to differentiate them from ffao's deviation strategies. To clarify, triplet modification strategies use elements of ffao's deviation, but only in very specific scenarios.

Part 2:

If we consider only the first 7 rounds of the game, then (given our previous analysis) there are only 9 possible combinations that we do not know for sure if Joel's strategy (with modifications) will work for:
1 AAB AAB XXX XXX
1 AAB ABA XXX XXX
1 AAB BAA XXX XXX
1 ABA AAB XXX XXX
1 ABA ABA XXX XXX
1 ABA BAA XXX XXX
1 BAA AAB XXX XXX
1 BAA ABA XXX XXX
1 BAA BAA XXX XXX

Before we can prove any of these combinations, we first need to determine what we need to prove them. and for that, we need to take a detour.

Part 3:

Based on the part 1 analysis, a new rule for player B can be established:
Rule 1: If ANY ffao deviation from Joel's basic strategy occurs in the first 3 groups, assume the last two groups are in the form of ABB.

Now let us consider a game where:
1. the players have just finished the 7th round,
2. player B has been signaled by player A the answer to round 8,
3. player A has made a deviation from Joel's basic strategy sometime in the first 7 rounds and,
4. they can afford to loose one more round (effectively a 5 of 6 game).

Because they have deviated from Joel's basic strategy, we know that the last two groups cannot be of the form AAA. This in conjunction with the new rule we just established results in the following:
Joel's strategy with the new rule applied AND with ffao's strategy applied to it will fail this situation if and only if neither group 4 nor group 5 has the form ABB.

A total of 16 cases fit this failure condition, 8 of which can be represented by either signaling on the 1st of the 6 games, or by using ffao's deviation on the 1st or 2nd of the 6 games. There are still 8 cases which require a unique signal for this strategy to succeed.

Going back to our 9 unproven combinations, we can say that a combination is proven to succeed with Joel's strategy (with modifications) if two conditions are met:
Condition 1: There is 1 unique deviation for player A to play in that combination such that, by the end of round 7; he has deviated from Joel's basic strategy; he has conveyed to player B the answer to round 8 and; he can afford to loose one more round (we will call this the Main Deviation for the given combination),
Condition 2: There are 8 other unique deviations from Joel's basic strategy such that they make it through the 7 rounds without going over the 4 loss limit (we will call these the 8 Side Deviations for the given combination).

In addition to these two requirements, we also need to be conscious of what signals and deviations we use for which combinations as using some signals for one combination may leave not enough to prove another combination.

Part 4:

Now all we need to do is prove that there is 1 main deviation and 8 side deviations (as defined in the previous section) for each of the 9 combinations.

For 1 AAB BAA XXX XXX, 1 ABA BAA XXX XXX and 1 BAA BAA XXX XXX:
Main Deviation:
We will use ffao's minority deviation to define our main deviation. That is, for round 1, player A will signal the minority number in group 2. Two rounds of group 2 will be lost lost, but this allows player A to use these loses to signal the majority number in group 3 and the answer to round 8. The following rule must be imposed on player B for this to work:
Rule 2: If a minority deviation occurred on round 1 and no throw occurred on round 2, then group 3 is of the form BAA.

Side Deviations:
For 4 of the 8 side deviations needed, we will use a minority deviation on round 1 followed by a throw on round 6 or 7. The other 4 side deviations can be obtained by not signaling a minority on round 1 and instead signal a minority deviation on the loosing round in group 2. This forces two lost rounds in group 3 where player A can signal 4 different deviations.

Now it should be mentioned that for all 9 of the unproven combinations, a minority signal in group 2 will always accommodate 4 side deviations and will never interfere in the signaling of any of the other 8 combinations. Thus going forward in our proving of the 9 combinations, we will assume that these are accounted for and will change our requirements such that only 1 main and 4 side deviations are required for any particular combination to be proven successful.

For 1 AAB ABA XXX XXX:
Main Deviation:
Another rule is required for player B to create a main deviation for this combination:
Rule 3: If group 2 is known to be of the form AAX and a throw occurred on the second round of group 2, then group 2 is of the form AAB and group 3 is of the form ABA.

Using this rule, player A can throw round 2 of group 2, and then signal on round 1 of group 3 the answer to round 8. Player B knows the form of group 3, so after the first round of group 3, he knows the answer for the second and third rounds of that group, allowing them to finish the first 7 rounds with knowledge of round 8, and having only lost 3 rounds, thus this is the main deviation for this combination.

Side Deviations:
Our 4 side deviations here can be defined by throwing on round 3 and signaling on round 4 (as you would for the main deviation), but then throwing on either round 6 or 7. (Again, The other 4 side deviations are obtained by a minority signal in group 2).

For 1 ABA ABA XXX XXX:
Main Deviation:
More rules needed for Player B:
Rule 4: If a throw occurred on round 2, then assume group 2 is of the form ABA.
Rule 5: If a throw occurred on round 2 and group 2 is of the form ABA, then assume group 3 is of the form ABA.

From here it is similar to 1 AAB ABA XXX XXX. Throw on round 2 and signal on round 1 of group 3.

Side Deviations:
The side deviations are also similar, only this time the throw is on round 2 instead of round 3.

For 1 BAA ABA XXX XXX:
Main Deviation:
We need to impose some rather specific rules on player B for this one:
Rule 6: if a throw occurred on round 2 and group 2 is of the form BAA, then group 3 is of the form ABA and the answer to round 8 is 0.
Rule 7: if a throw occurred on round 4 and group 2 is of the form BAA, then group 3 is of the form ABA and the answer to round 8 is 1.

If round 8 is 0, then Player A will signal a minority deviation on round 1, then throw round 2. Rule 4 dictates that Player B will play group 2 in the form of BAB which will loose on the last round of the group where Player A can signal the majority number of group 3, thereby finishing the first 7 rounds with only 3 losses.

If round 8 is 1, then Player A will instead play Joel`s basic strategy for the first three rounds and then throw on round 4. The lost round 2 will be the signal for the majority of group 3 in this case.

Side Deviations:
We have lots of options for side deviations. Following either path for the main deviation and then throwing on either round 6 or 7 will account for the 4 side deviations needed.

For 1 AAB AAB XXX XXX:
Main Deviation:
Playing Joel's normal strategy, but then throwing on either round 5 or 6 can signal the answer to round 8 while also leaving the players with only 3 losses by the end of round 7. The following rules must be applied to Player B for this main deviation to work:
Rule 4: If a throw on round 5 is the first deviation from Joel's basic strategy, then group 3 is of the form AAB.
Rule 5: If a throw on round 6 is the first deviation from Joel's basic strategy and group 3 is of the form AAX, then group 3 is of the form AAB.

It should be mentioned that Rule 5 does not interfere with the group 3 triplet strategy as outlined in part 1 (this is why player B needs to play opposite on round 7 during the group 3 triplet strategy)

Side Deviations:
2 of the 4 side deviations for this combination can be assigned to throwing round 7 after throwing either round 5 or 6. The other 2 can be assigned to throwing round 3. This signals to Player B (via rule 3) that group 3 is of the form ABA, which it actually isn't, but that's okay as by the time round 6 is over, they will know that group 3 is of the from AAB and can therefore finish round 7 without going over 4 losses.

For 1 ABA AAB XXX XXX:
Main Deviation:
The main deviation is the same as it was for 1 AAB AAB XXX XXX (round 5 or 6 throw).

Side Deviations:
Similarly, 2 of the 4 side deviations are assigned to throwing round 7 while the other two are assigned to throwing round 2, which via rules 4 and 5 will compel Player B to assume group 2 is of the form ABA (which it is) and group 3 is of the form ABA, which it isn't, but that's okay as by the time round 6 is over, they will know that group 3 is of the from AAB and can therefore finish round 7 without going over 4 losses.

For 1 BAA AAB XXX XXX:
Main Deviation:
The main deviation is the same as it was for 1 AAB AAB XXX XXX (round 5 or 6 throw).

Side Deviations:
Similarly, 2 of the 4 side deviations are assigned to throwing round 7 while the other two are assigned to throwing round 4, which via rule 7 will compel Player B to assume group 3 is of the form ABA, which it isn't, but that's okay as by the time round 5 is over, they will know that group 3 is of the from AAB and can therefore finish round 7 without going over 4 losses.

After all of that we are left with rough and crude strategies for Player A and Player B.

Summary of Player A Strategy:

If round 1 is 0, then play Joel's with ffao's modification.

If any group is of the form AAA, then play the relevant triplet strategy corresponding to the group that is the triplet. (see part 1 of my solution)

If the last 6 rounds are of the form ABBXXX, XXXBAA, ABAABA, or ABABAB, then play the main deviation of the combination defined by the casino numbers from the first 7 rounds (see part 2 and part 4 of my solution).

If the last 6 rounds are of the form ABAAAB, or ABABBA, then play the main deviation of the combination defined by the first 7 numbers, but invert the signal to player B that tells him the answer to round 8 (see part 2 and part 4 of my solution).

If the last 6 rounds are of the form AABABA or AABBAB, then play one of the four side deviations of the combination defined by the first 7 numbers (see part 2 and part 4 of my solution).

If the last 6 rounds are of the form AABAAB or AABBBA, then play a second round minority deviation.

Summary of Player B Strategy:

Begin by playing Joel's basic strategy.

After Round 2:
If a throw occurred on the 1st round of group 2, then assume group 2 is of the form ABA.


After Round 3:
If group 2 is known to be of the form AAX and a throw occurred on the 2nd round of group 2, then assume group 2 is of the form AAB and group 3 is of the form ABA.


After Round 4:
If a throw occurred on the 1st round of group 2 and group 2 is of the form BAA, then assume group 3 is of the form ABA and the answer to round 8 is 0.

If a throw occurred on the 3rd round of group 2 and group 2 is of the form BAA, then assume group 3 is of the form ABA and the answer to round 8 is 1.

If a throw occurred on the 1st round of group 2 and group 2 is of the form ABA, then assume group 3 is of the form ABA.

If a minority deviation occurred on round 1 and no throw occurred on round 2,then group 3 is of the form BAA.


After Round 5:
If the assumption from earlier that group 3 is of the form ABA is proven wrong, then group 3 is of the form AAB

If round 5 was thrown, and this is the first deviation from Joel's basic strategy, then assume group 3 is of the form AAB


After Round 6:
If the assumption from earlier that group 3 is of the form ABA is proven wrong, then group 3 is of the form AAB

If round 6 was thrown, group 3 is of the form AAX, and this is the first deviation from Joel's basic strategy, then assume group 3 is of the from AAB


After Round 7:
If a minority deviation was signaled in group 2 (Player A signaled the minority number of group 3), then the last 6 numbers are of the form AABAAB or AABBBA. Check the signals of the two lost rounds to determine which of the four possibilities it is.

If a Main Deviation has been played, it means player A has signaled the answer to round 8 in the first 7 rounds and the last 6 rounds are in the form of ABBXXX, XXXBAA, ABAABA, or ABABAB. Assume the remaining numbers are in the form ABBABB, play the round 8 number that Player A signaled, and then follow the remaining signals to determine which of the possibilities it really is.

If a Side Deviation has been played, then there is exactly one possibility for the last 6 numbers (which will always be in the form of AABABA or AABBAB). The exact answer will be dependent on what Player A and Player B agreed on before hand regarding which Side Deviation meant what.

If a triplet occurred in group 3, then check if round 6 was thrown and check if round 7 was thrown. Play according to the signals provided by Player A


After Round 8:
If a Main Deviation was played, and the answer to round 8 was the reverse of what Player A signaled, then the final 6 numbers are of the form ABAAAB or ABABBA. The number that Player A signaled on Round 8 will tell you which is the answer.


After Round 10:
If a triplet occurred in group 4, then check if round 9 was thrown and check if round 10 was thrown. Play accordingly.

Dear Lord I can't believe I typed all of that out. I don't know if 10 out of 14 games is possible, but I feel like I can confidently say 9 out of 13 games is possible. Feel free to critic my solution. There's a very good chance I've missed something or left some vagueness in my explanation. But at this point, I think I need to go rest my brain.

Answer 2

The answer is that

yes, they can guarantee 9 correct out of 13.

In fact I claim that

they can also 12 out of 17, 15 out of 21, 18 out of 25 .. that is, if they die on their M'th mistake, they can guarantee survival up to N=4M-7.

The overall idea is this:

- There is a strategy which, after 2 rounds, ends up "healthy" with at most 2 mistakes.
- There is a strategy which, assuming that it starts "healthy" with at most M mistakes, ends up, after 4 more rounds, "healthy" with at most M+1 mistakes.
- There is a strategy which, assuming that it starts "healthy" with at most M mistakes, ends up, after 3 more rounds, having made at most M mistakes.
So we can chain them (2+4+4+3) to get the answer required. And for every extra mistake we are allowed, we can insert a group of 4 rounds.

I define "healthy with at most M mistakes" as follows:

One of the following holds:
- They have made M-1 or fewer mistakes, and the Slave has "a Small amount of information"; OR
- They have made M mistakes, and the Slave has "a Large amount of information".

With that in mind, now let us forget OP's game, and consider this alternate (and less boringly labelled) game:

"Master and Slave versus Bob: hard version" The answer is rather long, and it occurs to me this is a good excuse to create a new puzzle... or two!
Now, take any answer to that puzzle (such as mine), and do this:
- Divide the 13 rounds into an initial group A of 2 rounds, groups B and C of 4 rounds each, and a final group D of 3 rounds.
- Play the groups in reverse order (D, then C, then B, then A) up to step (3) in each group. The Master's card in step (3) of one group becomes Bob's card in step (1) of the previous group.
- Finish the groups in proper order (A to D) from step (4) onward. The Slave's decision at step (6) of one group becomes Bob's decision in step (4) of the next group.
Thus, once the strategies are chained together, the 'Deck of cards' exists only in the mind of the Master and Slave, Bob doesn't actually have anything to do with it.

Answer 3

Here is a solution to $N=12$ and some thoughts about $N=13$.

First, we must analysis the solution to the previous puzzle given by ffao here. ffao's answer was based on a simple strategy from Joel Rondeau. Here is Joel's strategy which guarantees $\lceil \frac{N-1}{3} \rceil$ out of $N$ wins (5 of 9 in the previous puzzle):

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.

However this strategy will fail getting 6 of 9 wins in the following scenario.

The casino can always force the first loss and then one loss every three rounds. So, if we group the rounds into sets as follows (1 222 333 44), this strategy will fail when set 1 is 1 and the rest of the sets are all not the same number.

Here is ffao's modifications which guarantees 6 of 9 wins. Note: I slightly changed this to generalize better when we analysis this later.

ffao's modifications work by signaling player B that we are in a previously losing scenario by deviating from Joel's strategy. There are two ways of doing this.

First, by intentionally giving a minority indicator instead of the regular majority indicator. This will cause Player B to fail twice next set, however this gives you two bits of info to communicate to future sets instead of one. Also, player B won't fully notice this until the next set is done. Let's abbreviate this to ND (miNority Deviation).

Second, by intentionally failing a majority round. We can give one bit as normal during the minority round and another by which of the two majority rounds we fail. Let's abbreviate this to JD (maJority Deviation).

Next, we need a bit of shorthand notation. The deviations (ND and JD) will each give us two bits of information that will be denoted as $A$ and $B$. Each one can either be a 0 or 1. Furthermore, the inverse of these bits are the lowercase version. For example, if $A=1$ then $a=0$. Finally, if a set follows the Joel's original (or follows the second set of a ND) it will be denoted as FJ (Follows Joel's strategy).

Now, let's start figuring out how to use these deviations for the 6 or 9 wins puzzle.
Deviation 1: Used when set 3 is $aAA$ and set 4 is $Bb$. Indicated when set 1 is a ND, set 2 is a FJ.
Deviation 2: Used when set 3 is $AaA$ and set 4 is $Bb$. Indicated when set 1 is a FJ, set 2 is a JD.
Deviation 3: Used when set 3 is $AAa$ and set 4 is $Bb$. Indicated when set 1 is a FJ, set 2 is a FJ, set 3 is a JD. Note that we can make set 3 a JD since both its majority rounds come before the minority. Player B can recognize this and play the minority number and win that round.

If you are confused at this point, I suggest reading ffao's answer that is linked above. It is slightly different as I found a way of changing case 2 to make a unified case 3 but it is mostly the same.

Let's analysis how this worked.

In the above strategy we choose the deviation based off the last two sets. There are 6 combinations for set 3 and 2 combinations for set 4 for a total of 12 combinations. Each deviation gives two bits of information with have $2^2=4$ combinations. Since we have 3 deviations we can detect $3*4=12$ combinations.

Here is the $N=12$ solution

The solution is almost exactly the same as ffao's solution with an extra set and an extra allowable loss. The first change we make is to choose the deviation based on set 4 and 5. In deviation 1 and 2, set 3 will be FJ. In deviation 3, player B does not know the last round of set 3 and follows the standard strategy. The rest is the same.

Here is my thoughts on $N=13$

$N=13$ is not possible with a modification of Joel's strategy and here's why. Now that we have an extra round the grouping is 1 222 333 444 555. Sets 4 and 5 have $6*6=36$ combinations. There are 5 standard deviations (ND/FJ/FJ, FJ/ND/FJ, FJ/JD/FJ, FJ/FJ/JD, and FJ/FJ/FJ/JD) giving a total of $5*4=20$ combinations. There are two more deviations (ND/JD, FJ/JD*2) that combined give only a single combination (I don't know how to properly explain why this is the case but if you made it this far hopefully you can work it out yourself). This brings us to 21 detectable combinations which is still short of the 36 we need. Therefore, a modification of Joel's strategy is impossible when $N=13$. The problem is even worse when we consider that there are other groupings that fail Joel's strategy. One example is 1 222 3 444 555 66, where set 2 are all the same and set 4, 5, and 6 are not. This makes me think that $N=13$ is impossible for any strategy.