Project Euler | 欧拉计划
0%

Problem 863

题目发布于 翻译更新于

Problem 863

Different Dice

Using only a six-sided fair dice and a five-sided fair dice, we would like to emulate an $n$-sided fair dice.

For example, one way to emulate a $28$-sided dice is to follow this procedure:

  1. Roll both dice, obtaining integers $1\le p\le 6$ and $1\le q\le 5$.
  2. Combine them using $r = 5(p-1) + q$ to obtain an integer $1\le r\le 30$.
  3. If $r\le 28$, return the value $r$ and stop.
  4. Otherwise ($r$ being $29$ or $30$), roll both dice again, obtaining integers $1\le s\le 6$ and $1\le t\le 5$.
  5. Compute $u = 30(r-29) + 5(s-1) + t$ to obtain an integer $1\le u\le 60$.
  6. If $u>4$, return the value $((u-5)\bmod 28) + 1$ and stop.
  7. Otherwise (with $1\le u\le 4$), roll the six-sided dice twice, obtaining integers $1\le v\le 6$ and $1\le w\le 6$.
  8. Compute $x = 36(u-1) + 6(v-1) + w$ to obtain an integer $1\le x\le 144$.
  9. If $x>4$, return the value $((x-5)\bmod 28) + 1$ and stop.
  10. Otherwise (with $1\le x\le 4$), assign $u:=x$ and go back to step $7$.

The expected number of dice rolls in following this procedure is $2.142476$ (rounded to $6$ decimal places). Note that rolling both dice at the same time is still counted as two dice rolls.

There exist other more complex procedures for emulating a $28$-sided dice that entail a smaller average number of dice rolls. However, the above procedure has the attractive property that the sequence of dice rolled is predetermined: regardless of the outcome, it follows $(D5,D6,D5,D6,D6,D6,D6,\ldots)$, truncated wherever the process stops. In fact, amongst procedures for $n=28$ with this restriction, this one is optimal in the sense of minimising the expected number of rolls needed.

Different values of $n$ will in general use different predetermined sequences. For example, for $n=8$, the sequence $(D5,D5,D5,\ldots)$ gives an optimal procedure, taking $2.083333\ldots$ dice rolls on average.

Define $R(n)$ to be the expected number of dice rolls for an optimal procedure for emulating an $n$-sided dice using only a five-sided and a six-sided dice, considering only those procedures where the sequence of dice rolled is predetermined. So, $R(8) \approx 2.083333$ and $R(28) \approx 2.142476$.

Let $S(n) = \displaystyle\sum_{k=2}^n R(k)$. You are given that $S(30) \approx 56.054622$.

Find $S(1000)$. Give your answer rounded to $6$ decimal places.

不同的骰子

我们尝试用一枚公平的六面骰和一枚公平的五面骰来模拟一枚公平的$n$面骰。

例如，遵照如下方案，我们可以模拟一枚$28$面骰：

  1. 同时抛掷这两枚骰子，得到整数$1\le p\le 6$和$1\le q\le 5$。
  2. 计算$r = 5(p-1) + q$，得到整数$1\le r\le 30$。
  3. 若$r\le 28$，给出$r$并停止。
  4. 否则（若$r$为$29$或$30$），再次同时抛掷这两枚骰子，得到整数$1\le s\le 6$和$1\le t\le 5$。
  5. 计算$u = 30(r-29) + 5(s-1) + t$，得到整数$1\le u\le 60$。
  6. 若$u>4$，给出$((u-5)\bmod 28) + 1$并停止。
  7. 否则（若$1\le u\le 4$），抛掷六面骰两次，得到$1\le v\le 6$和$1\le w\le 6$。
  8. 计算$x = 36(u-1) + 6(v-1) + w$，得到整数$1\le x\le 144$。
  9. 若$x>4$，给出$((x-5)\bmod 28) + 1$并停止。
  10. 否则（若$1\le x\le 4$），令$u:=x$并回到第$7$步。

遵照上述方案，抛掷骰子次数的期望为$2.142476$（四舍五入保留$6$位小数）。注意同时抛掷两枚骰子被算作抛掷两次。

对于模拟$28$面骰的问题，存在更复杂但抛掷次数期望更小的方案。然而，上述方案的特点之一是，无论结果如何，抛掷骰子的序列是事先确定的，在停止前总是遵循$(D5,D6,D5,D6,D6,D6,D6,\ldots)$。事实上，在所有考虑这一额外规则的模拟$28$面骰的方案中，上述方案所需的抛掷次数期望最小。

对于不同的$n$，事先确定的抛掷序列也会不同。例如，对于$n=8$，最优方案中的抛掷序列为$(D5,D5,D5,\ldots)$，对应抛掷次数的期望为$2.083333\ldots$。

定义$R(n)$为仅使用一枚五面骰和一枚六面骰，且遵循上述“抛掷序列必须事先确定”的额外规则，以模拟$n$面骰所需的最小期望抛掷次数。因此，$R(8) \approx 2.083333$，$R(28) \approx 2.142476$。

记$S(n) = \displaystyle\sum_{k=2}^n R(k)$。已知$S(30) \approx 56.054622$。

求$S(1000)$，并四舍五入保留$6$位小数作为你的答案。