Ponder This Challenge - September 2013 - Bob and Alice vs the casino

Ponder This Challenge:

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.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  For those of you who asked, testing your submissions is not trivial. We used a SAT solver to do that, and even used it as a programming challenge in an IEEEXtreme-7.0 competition.

  The problem was posed several years ago on the RAD challenge site (the site is not on-line anymore, see a news story about it at http://www.globes.co.il/serveen/globes/docview.asp?did=892557. MSRI has a nice mathematical puzzles corner and you can see a version of this challenge there too.

  Here is Michael Brand's solution:

  First, the general premise:

  1. Alice determines her bits based on signalling that was given by Bob. Regardless of how many bits of signal Bob has given her or what they were, both sides know exactly what Alice is going to do.
  2. If Bob believes Alice's next bit to match the casino's, he does not signal. Instead, he goes for a win. Only when a loss is inevitable does Bob use his bit to signal.
  3. Alice's first bit comes with no signalling from Bob, so can always fail.
  4. Divide all other bits to consecutive 3s. Bob signals to Alice the majority bit of the next relevant triplet (the nearest one still in the future, which hasn't been signaled for, yet.)

  This strategy clearly meets n=3k+1, m=2k. Two bits of every triplet are guaranteed.

  This guarantees m=6 for all cases except when all of the following conditions hold:

  1. The first bit is wrong
  2. Bits 2-4 and 5-7 both have a minority
  3. Bits 8 and 9 have different values.

  Therefore, if Bob diverges visibly from the strategy described above, Alice knows we are in this situation. Now, the question is only in which of these situations, which takes less bits to communicate. Here's how Bob does it. We divide it into three cases, according to where the minority of 5-7 is located (first position, middle position, last position).

  Case #1: Minority of 5-7 is in position 5.
  Bob diverges from his strategy on bits 2-4 by using one extra bit (one of the majority bits) for signalling. His signal is now his original (minority) signal bit, plus a second bit which is the choice of a majority bit to mess up. Two bits can communicate the value of 8 and the majority of 5-7. Together with the knowledge of the case, we know all of 5-9 and will have no further mistakes.

  Case #2: Minority is in position 6.
  Bob diverges from his strategy on bit 1 by communicating the minority bit of 2-4. (Alice discovers this after bit 4.) He can now use both majority bits for signalling. The rest is as in case #1.

  Case #3: Minority is in position 7.
  Bob diverges from his strategy on bits 5-6 by messing up one of them. The choice of which to mess up is one bit of signalling. It gives the value of bit 8. Note that because Alice notices this already on bits 5-6, Alice and Bob win at position 7, so they are still m=6.

Solvers

• Michael Brand (09/03/2013 02:00 AM EDT)
• Daniel Bitin (09/08/2013 07:08 PM EDT)
• Joseph Berman (09/10/2013 10:19 AM EDT)
• Tom Harley (09/10/2013 04:28 AM EDT)
• Liubing Yu (09/10/2013 08:50 PM EDT)
• James Dow Allen (09/13/2013 03:56 AM EDT)
• Piotr Zielinski (09/14/2013 12:09 AM EDT)
• Motty Porat (09/14/2013 03:09 PM EDT)
• Florian Fischer (09/15/2013 02:23AM EDT)
• Aharon Malachi (09/15/2013 08:00AM EDT)
• Graham Hemsley (09/16/2013 06:18 AM EDT)
• Bart De Vylder (09/16/2013 05:22 PM EDT)
• Don Dodson (09/17/2013 08:34 PM EDT)
• William Heller (09/19/2013 04:32 PM EDT)
• Oleg Nitz (09/20/2013 10:49 AM EDT)
• Michael Wilms (09/24/2013 03:21 PM EDT)
• John P Spurgeon (09/24/2013 05:09 PM EDT)
• Javier Rodriguez (09/28/2013 06:33 PM EDT)
• Adrian Orzepowski (09/29/2013 03:02 PM EDT)
• Radu-Alexandru Todor (09/29/2013 05:00 PM EDT)
• Alex Wagner (09/30/2013 01:24 AM EDT)
• Kevin Bauer (09/30/2013 07:12 PM EDT)
• Jason Levy (10/01/2013 08:23 AM EDT)
• kitutwas & flyiop & NjuBee (10/03/2013 04:15 PM EDT)
• Regis Vert (10/06/2013 04:18 PM EDT)
• *Olivier Mercier (10/06/2013 09:48 PM EDT)
• Anatoly Vorobey (10/09/2013 08:18 AM EDT)
• Todd Will (10/10/2013 03:48 PM EDT)
• Antoine Comeau (10/13/2013 06:32 PM EDT)
• Dharmadeep Muppalla (10/19/2013 05:56 AM EDT)
• Svyatoslav Savenko & Tatiana Stepanova (10/20/2013 04:44 PM EDT)
• Grzegorz Anielak (10/22/2013 06:07 PM EDT)
• Andrew Gacek (10/29/2013 07:11 AM EDT)
• Dennie Tyshchenko (10/30/2013 05:07 PM EDT)
• Kan Shen (10/31/2013 10:45 PM EDT)
• Daniil Razumikhin (11/01/2013 03:11 AM EDT)
• Uoti Urpala (11/03/2013 11:27 PM EDT)