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.
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
Challenge:
09/03/2013 @ 01:00 PM EST
Solution:
10/01/2013 @ 01:00 PM EST
List Updated:
09/03/2013 @ 01:00 PM EST
People who answered correctly:
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)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.