September 2013
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.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com