Project Euler 848

发表于 分类于 阅读次数： 本文字数： 4.6k 阅读时长 ≈ 4 分钟

Project Euler 848

题目

Guessing with Sets

Two players play a game. At the start of the game each player secretly chooses an integer; the first player from \(1,\dots,n\) and the second player from \(1,\dots,m\). Then they take alternate turns, starting with the first player. The player, whose turn it is, displays a set of numbers and the other player tells whether their secret number is in the set or not. The player to correctly guess a set with a single number is the winner and the game ends.

Let \(p(m,n)\) be the winning probability of the first player assuming both players play optimally. For example \(p(1, n) = 1\) and \(p(m, 1) = 1/m\).

You are also given \(p(7,5) \approx 0.51428571\).

Find \(\displaystyle \sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i, 5^j)\) and give your answer rounded to \(8\) digits after the decimal point.

解决方案

把游戏状态记为 \((m,n)\)：轮到当前玩家行动，对方秘密数还可能在 \(m\) 个候选里；而当前玩家自己的秘密数还可能在 \(n\) 个候选里。当前玩家要通过询问集合来尽快锁定对方。

当处于 \((m,n)\) 且 \(m\ge 2\) 时，当前玩家选一个集合 \(S\)，等价于选它的大小 \(i=|S|\)，其中 \(1\le i\le m-1\)（取补集与之对称，只需考虑大小）。对方回答：

  • 以概率 \(i/m\) 回答 “在集合中”，于是对方的候选缩为 \(i\)；
  • 以概率 \((m-i)/m\) 回答 “不在集合中”，于是对方候选缩为 \(m-i\)。

回答结束后轮到对方行动，角色互换：新状态分别变成 \((n,i)\) 或 \((n,m-i)\)。 若之后对方获胜的概率是 \(p(\cdot,\cdot)\)，那么当前玩家在该分支的胜率是 \(1-p(\cdot,\cdot)\)。

唯一需要单独强调的是 \(i=1\) 的“立刻获胜”机制：当 \(S\) 为单元素集合时，若对方回答“在集合中”，当前玩家直接结束游戏获胜。这件事可以用一个非常方便的约定统一进公式。

为统一递推表达，约定在递推过程中取 \(p(m,1)=0\)。其含义是：当某方行动且对手候选集规模已为 \(1\) 时，该方可立即通过提交对应的单元素集合获胜，因此在“轮到对手行动”的后继状态中，将该项记为 \(0\) 与博弈终止条件一致。在这个约定下，对 \(m,n\ge 2\) 有统一递推：

\[ p(m,n)=\max_{1\le i\le m-1}\left\{\frac{i}{m}\bigl(1-p(n,i)\bigr)+\frac{m-i}{m}(1-p(n,m-i))\right\}, \]

其中递推内部用到的 \(p(\cdot,1)\) 取 \(0\)。边界（真实胜率）仍是\(p(1,n)=1, p(m,1)=\dfrac1m.\)

令\(g(m,n)=mn\cdot p(m,n).\)把上式两边乘以 \(mn\)，并整理可得（对 \(m,n\ge 2\)）：\(\displaystyle{g(m,n)=\max_{1\le i\le m-1}\{mn-g(n,i)-g(n,m-i)\}.}\)因此

\[ g(m,n)=mn-\min_{1\le i\le m-1}\{g(n,i)+g(n,m-i)\}. \]

只要边界是整数，递推全是加减与取 \(\max\)，故 \(g(m,n)\) 都是整数。

固定 \(n\)，记\(h_n(i)=g(n,i), 1\le i.\)设\(F_m(i)=h_n(i)+h_n(m-i), 1\le i\le m-1.\)若序列 \(h_n\) 满足离散凸性（即一阶差分单调不降）：\(\Delta h_n(i)=h_n(i)-h_n(i-1), \Delta h_n(i+1)\ge \Delta h_n(i),\)则 \(F_m(i)\) 的最小值在中心取得：\(m\) 为偶数时取 \(i=m/2\)，\(m\) 为奇数时取 \(i=(m-1)/2,(m+1)/2\)（两者等价）。下文将通过 \(K_n\) 的闭式反推离散凸性成立。

证明： 计算相邻差分\(F_m(i+1)-F_m(i)=\bigl(h_n(i+1)-h_n(i)\bigr)-\bigl(h_n(m-i)-h_n(m-i-1)\bigr)=\Delta h_n(i+1)-\Delta h_n(m-i).\)由于 \(\Delta h_n\) 单调不降，右侧随 \(i\) 单调不降，故 \(F_m\) 为离散凸函数；又因\(F_m(i)=F_m(m-i),\)其最小值只能出现在中心位置，结论成立。

在本题规模下，最终得到的最优行动规则可以写成：

  • 若 \(m\le 2\)，必然选单点（因为无法真正二分）；
  • 若 \(n\le 2\)，也会选单点（对方离胜利太近，需要追求立刻命中概率）；
  • 否则（典型区域 \(m\ge 3,n\ge 3\)），选二分 \(i=\lfloor m/2\rfloor\)（等价于“尽量平分”）。

这使得问题从遍历所有 \(i\)降为只需理解二分产生的自相似结构。

固定 \(n\ge 2\)，考虑函数 \(t\mapsto g(n,t)\)。由前文增量公式可得\(g(n,t)-g(n,t-1)=\min(n,B(t)),\)其中 \(B(t)\) 为里程碑序列（\(1,2,3,6,12,24,48,\dots\)，即 \(1,2,3\) 之后不断乘 \(2\)。）且满足 \(B(t)\ge t\)。因此当 \(t\ge n+1\) 时，\(B(t)\ge t>n\Longrightarrow g(n,t)-g(n,t-1)=n.\)

故在区间 \([n,\infty)\) 上，\(g(n,t)\) 的相邻差恒为 \(n\)，从而\(g(n,t)-nt\)为常数。记该常数为 \(\beta_n\)，即\(g(n,t)=nt+\beta_n (t\ge n).\)在 \(t=n\) 处代入即得\(\beta_n=g(n,n)-n^2,\)所以\(g(n,t)=nt-(n^2-g(n,n)) (t\ge n).\)

另一方面，由前文中心分割最优可知，递推\(\displaystyle{g(m,n)=mn-\min_{1\le i\le m-1}\{g(n,i)+g(n,m-i)\}}\)在 \(m\ge 2n\) 由\(i=\left\lfloor\dfrac m2\right\rfloor,\left\lceil\dfrac m2\right\rceil\)达到最小，且二者均不少于 \(n\)，可直接使用上式的线性表示：

\[ \begin{aligned} g(m,n) &=mn-g\left(n,\Bigl\lfloor\frac m2\Bigr\rfloor\right)-g\left(n,\Bigl\lceil\frac m2\Bigr\rceil\right)\\ &=mn-\left(n\Bigl\lfloor\frac m2\Bigr\rfloor+\beta_n\right)-\left(n\Bigl\lceil\frac m2\Bigr\rceil+\beta_n\right)\\ &=mn-nm-2\beta_n\\ &=-2\beta_n\\ &=2\bigl(n^2-g(n,n)\bigr). \end{aligned} \]

于是存在阈值 \(M(n)\)（可取 \(M(n)=2n\)），使得 \(m\ge M(n)\) 时 \(g(m,n)\) 与 \(m\) 无关。记该稳定值为 \(K_n\)，得到\(K_n=2\bigl(n^2-g(n,n)\bigr).\)

另一方面，在对角点 \((n,n)\) 的递推为\(g(n,n)=n^2-g\left(n,\left\lfloor\dfrac n2\right\rfloor\right)-g\left(n,\left\lceil\dfrac n2\right\rceil\right),\)代回即得

\[ K_n=2g\left(n,\Bigl\lfloor\frac n2\Bigr\rfloor\right)+2g\left(n,\Bigl\lceil\frac n2\Bigr\rceil\right). \]

再用稳定性阈值：对任意 \(r\)，当 \(m\ge 2r-1\) 时有\(g(m,r)=K_r.\)由此在前面的表达式中可直接替换：

  • 若 \(n=2t(t\ge2)\)，则\(K_{2t}=2g(2t,t)+2g(2t,t)=4K_t.\)
  • 若 \(n=2t+1(t\ge2)\)，则\(K_{2t+1}=2g(2t+1,t)+2g(2t+1,t+1)=2K_t+2K_{t+1}.\)

于是得到稳定序列递推：\(K_{2t}=4K_t,K_{2t+1}=2K_t+2K_{t+1} (t\ge2).\)

定义差分\(\Delta K_n=K_n-K_{n-1}(n\ge1).\)由上式可推出（对足够大的指标）：\(\Delta K_{2t}=2\Delta K_t(t\ge3),\Delta K_{2t+1}=2\Delta K_{t+1}(t\ge2).\)配合基值\(\Delta K_1=1,\Delta K_2=2,\Delta K_3=3,\Delta K_4=\Delta K_5=\Delta K_6=6,\)

归纳可得分块常值结构：\(\Delta K_n=3\cdot 2^{s}\)当且仅当\(3\cdot2^{s-1}<n\le 3\cdot2^{s}(s\ge1),\) 并且前三项是\(\Delta K_1=1,\Delta K_2=2,\Delta K_3=3.\)这正式上文的里程碑序列。因此

\[ \Delta K_n=B(n), K_n=\sum_{u=1}^{n}B(u). \]

回到一般的 \(g(m,n)\)。注意到对固定 \(m\)：\(0\le g(m,n)\le mn\Rightarrow0\le g(m,n)-g(m,n-1)\le m.\)也就是说，沿着 \(n\) 方向每增加一个候选，\(g\) 的增量最多为 \(m\)。

另一方面，当 \(m\) 足够大时增量就是稳定增量 \(\Delta K_n=B(n)\)。因此一般情形就是把这个增量按上界 \(m\) 截断：\(\Delta k^{(m)}_n=\min(m,\Delta K_n)=\min(m,B(n)),\)并累加得到 \(\displaystyle{g(m,n)=\sum_{t=1}^{n}\min(m,B(t)).}\)

最终（回到真实边界 \(p(m,1)=1/m\)）可以统一写成\(p(m,n)=\dfrac{g(m,n)}{mn}.\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from fractions import Fraction

M = N = 20
def g(m, n):
    prev = 0
    s = 0

    for ms in (1, 2, 3):
        d = ms if ms < m else m
        if n <= ms:
            return s + (n - prev) * d
        s += (ms - prev) * d
        prev = ms

    ms = 3
    while True:
        ms <<= 1
        d = ms if ms < m else m
        if n <= ms:
            return s + (n - prev) * d
        s += (ms - prev) * d
        prev = ms

def p(m, n):
    return Fraction(g(m, n), m * n)

ans = Fraction(0, 1)
for i in range(M + 1):
    mi = 7 ** i
    for j in range(N + 1):
        nj = 5 ** j
        ans += p(mi, nj)

print(f"{ans:.8f}")