4
$\begingroup$

This question already has an answer here:

This is another iteration of beat the casino. That question did not require a practical, implementable strategy, whereas this one does.

The rules are the same and I list them below. However, the OP answer to that question only had a theoretical result with no concrete strategy, and the accepted answer was not much of an improvement on the naive 2/3 method. I am looking for a practical, implementable result that achieves at least 70% success rate; well within the bounds of the theoretical result.

The rules are the same:

  1. Each round, $A$, $B$, and the casino simultaneously decide to show a $0$ or a $1$. If all three numbers match, $A$ and $B$ win that round.
  2. $A$ and $B$ are working cooperatively and can communicate before the game begins.
  3. $A$ has a method, just before the game starts, to learn the choices the casino will make over all the rounds. However, after learning this information $A$ cannot communicate with $B$ in any way except by her choices in the game.
  4. $A$ and $B$ are trying to maximize the fraction $p$ of rounds they win in the worst case.
  5. the game lasts for $n$ rounds.

What is the best possible $p$ that $A$ and $B$ can achieve as $n \to \infty$?

NOTE: I answered the referenced question (very late) and was able to achieve 67.8% with a relatively easy to describe strategy. I provided exact details on the strategies of each player, which got fairly complicated. If your strategy is easy to describe but complicated to implement, that is fine, so long as you can show the implementation is possible.

$\endgroup$

marked as duplicate by Fabich, Deusovi, Engineer Toast, manshu, Jonathan Allan May 20 '16 at 7:10

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What is the difference with the referenced question ? $\endgroup$ – Fabich May 19 '16 at 15:03
  • $\begingroup$ @Lordofdark That one has an accepted answer, so there is no point in continuing on that question. Also, the OP had his own answer in mind and posted a theoretical result which while very cool, is kind of unsatisfying since it does not have a method to actually reproduce. I thought the best way to try and get an answer I was looking for was to post a new question. $\endgroup$ – Trenin May 19 '16 at 15:13
  • $\begingroup$ @Trenin The question is tagged as "open ended" which means that the current answer could be "bested" at any point. So you can keep working on it. See open ended tag info : puzzling.stackexchange.com/tags/open-ended/info $\endgroup$ – Fabich May 19 '16 at 15:20
  • 1
    $\begingroup$ @Lordofdark Does that tag mean that an accepted answer can be changed? Looking at the tag, that is not clear. Because typically, if a question is answered, some puzzlers won't look at it. $\endgroup$ – Trenin May 19 '16 at 15:25
  • $\begingroup$ @GordonAllocman The difference is that in this question, I am looking for a practical strategy, not just a theoretical one. The OP of that question came up with a great theoretical limit for what you can achieve, but freely admits that there is no strategy that can do so. I am looking for a strategy that while doesn't need to be close to the theoretical limit (77%), should still be better than 66%. $\endgroup$ – Trenin May 19 '16 at 15:29
1
$\begingroup$

Edit edit: Reverted an answer due to critical math error.

This doesn't achieve 70%, but it's an improvement based on your previous answer, so I'll post it to get started.

Assume we have one bit of information, communicating the most common answer in the next 29 rounds. We'll design a method that cycles every N rounds, and passes such a bit forward for each next iteration of the method. For those 29 rounds, Bob will always pick the answer indicated by the majority bit. Whenever Bob will be answering wrong, Alice can communicate information (14 bits). Alice can also communicate 4 bits by getting one answer wrong that Bob gets right: getting the first wrong communicates 0000, the second communicates 0001, all the way up to getting the fifteenth wrong: 1110. 1111 is represented by Alice choosing to get none of the answers wrong. One of the bits will be the majority bit for the next batch. 15 of those bits can be spent to tell Bob the next 15 answers, (leaving us with 2 bits unspent), and again Alice can get one of those 15 answers wrong to communicate 4 additional bits (again with 1111 being represented by getting all answers right). We then use the remaining 6 bits to communicate the next 6 answers.

So we get 14 of the first 29 right, 14 of the next 15 right, and 6 of the next 6 right, 34/50 = 68%.

This can be improved further: consider three of these 50-game batches: we always win game 45-50, 95-100 and 145-50. By choosing to lose one of those games we can communicate an additional 4 bits of information about the answers for 151-154.

So for every 154-game period, we get 34/50, 34/50, 34/50, -1 for the game we sacrifice from [45-50,95-100,145-150], + 4/4 = 68.2%

We could cut the above a little finer still (instead sacrifice two games from [45-50,95-100,145-150,195-200,245-250] in order to get 8 bits, then look at [251-258, 509-516] and sacrifice one of them to get an additional 4 bits...) but that's a pit of diminishing returns that I doubt will take us above 70%.

$\endgroup$
  • $\begingroup$ Nice! I am wondering if there is something more intelligent that can be done with all those bits, but this is a great start! $\endgroup$ – Trenin May 19 '16 at 18:56
  • $\begingroup$ @Trenin The obvious more intelligent approach is to be willing to get two answers wrong: From 11 right answers, you can get two wrong in order to communicate 8 bits (11 ncr 2 + 11 ncr 1 + 11 ncr 0 = 66 = 8 bits). It's a long and fiddly road to figure out the best way to do that, but I'm planning to keep at it. $\endgroup$ – Ninety-Three May 19 '16 at 19:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.