IBM Ponder This #185 · September 2013

Alice and Bob are playing against the casino in the following game:
First Alice places her 0/1 bet. Bob then places his 0/1 bet. Finally, the casino provides its bet.
If all three bets are equal - Alice & Bob win; otherwise, the casino wins.
Alice and Bob can coordinate their strategy in advance, but once the games starts, they may not talk to one another or pass information in any way other than by announcing their bets.
Since the casino could easily cheat and always win by deciding its bet only after Alice and Bob announce their guesses, the casino must actually determine all its bets in advance and keep them in a safe from which they are drawn..
It is easy to see that the casino wins 75% of the time if Alice and Bob play at random, but they can get to 50% by agreeing that Alice will play at random and Bob will copy her. In both cases, Alice and Bob might, in the worst case, lose all the time (indeed with negligible probability, but still a nonzero one).

Now comes the interesting twist: Just before the beginning of the game, Bob steals the secret casino sequence from the casino's safe.
He knows he is going to get the secret Casino bets, but once he touches it - he can not talk to Alice anymore.
Now they can get 50% chance of winning, for example, by letting Alice play at random and having Bob play the secret casino bet.
This way, however, they still might (in the worst case) lose all the bets.
They can, however, guarantee 50% winning by letting Alice repeat Bob's previous bet, and letting Bob play the right bet in the even rounds and the future bet in the odd rounds.

What we ask this month is to provide Bob's strategy from n=9 rounds of the game that guarantees that Alice & Bob will win at least m=6 times.

Please provide the answer as a list of 512 lines of nine bits. In each line, write Bob's bets for the specific nine bets of the casino.

For example, here is the answer for the same question with n=2 and m=1:
00
11
00
11
This answer implements the strategy mentioned above.

As a bonus question: when n goes to infinity, can they do better? What is the maximal probability they can guarantee in the worst case?

Update 09/04: Alice strategy is too big to be sent explicitly, so even though you should send us only Bob's strategy, Alice should have a compatible strategy and we encourage you to describe it.

Solution

Best opened after a real attempt

To be added.