Project Euler 770

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

Project Euler 770

题目

Delphi Flip

A and B play a game. A has originally \(1\) gram of gold and B has an unlimited amount. Each round goes as follows:

  • A chooses and displays, \(x\), a nonnegative real number no larger than the amount of gold that A has.

  • Either B chooses to TAKE. Then A gives B \(x\) grams of gold.

  • Or B chooses to GIVE. Then B gives A \(x\) grams of gold.

B TAKEs \(n\) times and GIVEs \(n\) times after which the game finishes.

Define \(g(X)\) to be the smallest value of \(n\) so that A can guarantee to have at least \(X\) grams of gold at the end of the game. You are given \(g(1.7) = 10\).

Find \(g(1.9999)\).

解决方案

令\(X=1.9999\)。设某一时刻 A 的黄金量为 \(G\)。A 展示 \(x\) 等价于展示比例\(r=\dfrac{x}{G}\in[0,1].\)

  • 若 B 选 TAKE，A 失去 \(x\)，黄金量变为 \((1-r)G\)；
  • 若 B 选 GIVE，A 得到 \(x\)，黄金量变为 \((1+r)G\)。

因此策略只与比例 \(r\)有关，初始黄金量的缩放不会改变最优决策结构。

令 \(c(a,b)\) 表示：当未来还剩 TAKE \(a\) 次、GIVE \(b\) 次时，A 能保证的“最终黄金量/当前黄金量”的最大倍数（A 目标最大化，B 目标最小化）。

边界显然为：

\[ c(a,0)=1, c(0,b)=2^b. \]

这是因为，若没有 GIVE 机会（\(b=0\)），无论 A 怎么选 \(x\)，B 都会 TAKE，A 只能选择 \(x=0\) 才不会变差，因此保证倍数为 \(1\)； 若没有 TAKE 风险（\(a=0\)），A 每轮都可选 \(x=G\)（即 \(r=1\)），每次 GIVE 都翻倍，总倍数为 \(2^b\)。

当 \(a,b>0\) 时，A 选定 \(r\) 后，B 会在两种结果中取更坏的一种，因此

\[ c(a,b)=\max_{0\le r\le 1}\min((1-r)c(a-1,b),(1+r)c(a,b-1)). \]

在最优点上，A 会让对手所进入的状态无差别，即令两项相等：\((1-r)c(a-1,b)=(1+r)c(a,b-1).\)解得最优比例\(r=\dfrac{c(a-1,b)-c(a,b-1)}{c(a-1,b)+c(a,b-1)}.\)代回可得递推为调和平均形式：

\[ c(a,b)=\frac{2c(a-1,b)c(a,b-1)}{c(a-1,b)+c(a,b-1)}. \]

这一形式基于论文的推导而来。

令\(d(a,b)=\dfrac{1}{c(a,b)}.\)则边界变为\(d(a,0)=1, d(0,b)=2^{-b},\)而递推变成极其简单的平均：

\[ d(a,b)=\frac{d(a-1,b)+d(a,b-1)}{2}. \]

定义\(D(a,b)=2^{a+b}d(a,b),\)则递推化为\(D(a,b)=D(a-1,b)+D(a,b-1)\)，边界为\(D(a,0)=2^a, D(0,b)=1.\)

我们断言闭式为

\[ D(a,b)=\sum_{i=0}^{a}\binom{a+b}{i}. \]

验证：

  • 当 \(b=0\)，有 \(\displaystyle{D(a,0)=\sum_{i=0}^{a}\binom{a}{i}=2^a}\)；
  • 当 \(a=0\)，有 \(D(0,b)=\dbinom{b}{0}=1\)；
  • 递推利用帕斯卡恒等式 \(\dbinom{n}{i}=\dbinom{n-1}{i}+\dbinom{n-1}{i-1}\)，有：\(\displaystyle{\sum_{i=0}^{a}\binom{a+b}{i}=\sum_{i=0}^{a}\binom{a+b-1}{i}+\sum_{i=0}^{a}\binom{a+b-1}{i-1}=\sum_{i=0}^{a}\binom{a+b-1}{i}+\sum_{i=0}^{a-1}\binom{a+b-1}{i}.}\)右侧正是 \(D(a,b-1)+D(a-1,b)\)。

因此

\[ d(a,b)=\frac{\sum_{i=0}^{a}\binom{a+b}{i}}{2^{a+b}}, c(a,b)=\frac{2^{a+b}}{\sum_{i=0}^{a}\binom{a+b}{i}}. \]

这也与论文中在定理2给出的闭式一致。

题目需要 \(a=b=n\)：\(\displaystyle{d(n,n)=\dfrac{\sum_{i=0}^{n}\binom{2n}{i}}{2^{2n}}.}\)注意对称性 \(\dbinom{2n}{i}=\dbinom{2n}{2n-i}\)，因此\(\displaystyle{\sum_{i=0}^{n}\binom{2n}{i}=2^{2n-1}+\frac{1}{2}\binom{2n}{n}.}\)于是\(d(n,n)=\dfrac{1}{2}+\dfrac{\binom{2n}{n}}{2^{2n+1}}.\)

令\(e(n)=\dfrac{\binom{2n}{n}}{2^{2n}}=\dfrac{\binom{2n}{n}}{4^{n}},\)则\(d(n,n)=\dfrac{1}{2}+\dfrac{e(n)}{2},c(n,n)=\dfrac{1}{d(n,n)}=\dfrac{2}{1+e(n)}.\)

按照\(c\)的定义，可得

\[ g(X)=\min\{n:\ c(n,n)\ge X\}. \]

由\(c(n,n)\ge X\iff\dfrac{2}{1+e(n)}\ge X\iff e(n)\le \dfrac{2}{X}-1.\)

因此目标变成求最小 \(n\) 使得\(e(n)=\dfrac{\binom{2n}{n}}{4^n}<\dfrac{2}{X}-1.\)

由于 \(e(n)\) 严格单调递减（可知有\(\dfrac{e(n+1)}{e(n)}=\dfrac{2n+1}{2n+2}\)），所以可对 \(n\) 二分查找。

直接计算 \(\dbinom{2n}{n}\) 会溢出，因此比较\(\log e(n)=\log\dbinom{2n}{n}-n\log 4=\log\Gamma(2n+1)-2\log\Gamma(n+1)-n\log 4.\)和\(\log \left(\dfrac{2}{X}-1\right)\)的大小即可。

用高精度库 mpmath 的 loggamma 即可稳定判断，然后二分得到最小 \(n\)。

代码

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
import mpmath as mp

X = 1.9999
def g(x) -> int:
    mp.mp.dps = 80
    X = mp.mpf(x)
    thr = mp.mpf(2) / X - 1
    log_thr = mp.log(thr)

    def ok(n: int) -> bool:
        nonlocal log_thr
        n = mp.mpf(n)
        loge = mp.loggamma(2 * n + 1) - 2 * mp.loggamma(n + 1) - n * mp.log(4)
        return loge < log_thr

    approx = int(mp.ceil(1 / (mp.pi * thr * thr)))

    l, r = 0, max(1, approx)
    while not ok(r):
        r *= 2
    while l < r:
        mid = (l + r) // 2
        if ok(mid):
            r = mid
        else:
            l = mid + 1
    return r

print(g(X))