Best strategy for cheating in the “cheating royal riddle”

game theoryprobabilitypuzzlestatistics

I watched a video awhile ago from Ted-Ed called the "cheating royal riddle": https://www.youtube.com/watch?v=hk9c7sJ08Bg. The riddle is as follows:

  1. You're the advisor in a competition where four contestants roll both dice 20 times, in private, and add up the results.
  2. The red die has the numbers 2, 7, 7, 12, 12, and 17 on the six sides, and the blue die has 3, 8, 8, 13, 13, and 18. The dice are fair.
  3. A contestant should be disqualified by you, the advisor, if you're at least 90% sure that the score they reported wasn't actually their total.
  4. The highest-scoring player who wasn't disqualified is the winner.

In the video, the contestants A, B, C, and D, reported values 385, 840, 700, and 423, respectively. B was disqualified for not being possible (too high). C was disqualified or being improbable (would require rolling highest numbers on all 20 rolls), and D was disqualified for not being possible (not a multiple of 5). A was the only one left not disqualified, so she won.

My Question

What would the optimal strategy look like for this game if you were one of the contestants and wanted to cheat and not be detected by the advisor?

My first attempt is to honestly play the game mostly, but have a "cheat" round every 3 rounds, where I take the lowest number rolled and manually flip it to the highest number on that die. But I cannot figure out how to calculate the odds of that strategy on average.

I guess there is perhaps a calculable number that you can just calculate and report, but it would be interesting to also know if there is an optimal strategy to "play the game out" and be very likely to score higher than your opponents but not too high as to exceed the advisor's 90% threshold for cheating; that strategy would work even if you were observed by a proctor. I guess if you "play the game out", there is always a possibility that you get extremely lucky and are disqualified for cheating even if you didn't, so any strategy to improve your odds will make that situation more likely, so perhaps the best strategy is to just calculate the number and report it to ensure you're right below the threshold of being disqualified.

I'm working on a simulator for this just out of curiosity, but I figured I would ask here. I am new to this SE (normally on SO), but "Solving mathematical puzzles" showed up on the on-topic help (https://math.stackexchange.com/help/on-topic) for this SE, so I hope this is an appropriate place to put this question.

Best Answer

The following solution uses probability generating functions to find the probability of rolling a sum of $n$ with 20 rolls of the two dice. The probability generating function of a random variable $X$ (not to be confused with the moment generating function) is by definition $$\sum_{n=0}^{\infty} P(X=n) \; x^n$$ In the case of the two dice, the PGF of the red die is $$f_{red}(x) = (x^2+2x^7+2x^{12}+x^{17})/6$$ and that of the blue die is $$f_{blue}(x) = (x^3+2x^8+2x^{13}+x^{18})/6$$ The advantage of using PGFs is that is very simple, at least conceptually, to find the PGF of the sum of 20 rolls of the two dice: $$f_{sum}(x) = (f_{red}(x) \cdot f_{blue}(x))^{20}$$ So the probability of rolling a sum of $n$ is the coefficient of $x^n$ when $f_{sum}(x)$ is expanded, which we write as $[x^n]f_{sum}(x)$. Since $f_{sum}(x)$ is a polynomial of degree $700$, the probability of rolling a sum of $n$ or more is $$\sum_{i=n}^{700} [x^n]f_{sum}(x)$$ It makes me tired just to think about writing down the coefficients of a $700$ degree polynomial, even if only the coefficients of $x^n$ where $n$ is a multiple of $5$ are non-zero, but it's an easy task for a computer algebra system to do the expansion and summations. The following table shows a portion of the results.

n P(sum of n or more)
430 0.182105
435 0.141704
440 0.107822
445 0.0801753
450 0.0582282
455 0.0412809
460 0.0285536

We see that the probability of rolling $440$ or more is about $0.108$ and the probability of rolling $445$ or more is about $0.080$, so the advisor should accept any roll of $440$ or less, provided the roll is a multiple of $5$.

Here is a Mathematica program which implements the computation.

fred = (x^2 + 2 x^7 + 2 x^12 + x^17)/6
fblue = (x^3 + 2 x^8 + 2 x^13 + x^18)/6
fsum = Expand[(fred * fblue)^20];
tot[n_] := N[Sum[Coefficient[fsum, x^i], {i, n, 700}]]
Table[{n, tot[n]}, {n, 400, 500, 5}]

I am sure that other computer algebra systems such as Sage or Macsyma could also be used. I don't personally know how to run code of this level of complexity in Wolfram Alpha, but maybe it can be done.

Related Question