Are you a professional problem solver? If so, we invite you to submit your Ponder This solution for this month’s challenge. Ponder This is IBM Research’s monthly brain-twister where you can match wits with some of the best minds in IBM Research. If you’re successful, IBM Research will post your name to the list of people who answered correctly on their website. When you have solved the puzzle, you may submit your solution to the webmaster.
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 cannot 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:
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.
IBM Research 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!
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: firstname.lastname@example.org