Project Euler 366

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

Project Euler 366

题目

Stone Game III

Two players, Anton and Bernhard, are playing the following game.

There is one pile of \(n\) stones.

The first player may remove any positive number of stones, but not the whole pile.

Thereafter, each player may remove at most twice the number of stones his opponent took on the previous move.

The player who removes the last stone wins.

E.g. \(n=5\)

If the first player takes anything more than one stone the next player will be able to take all remaining stones.

If the first player takes one stone, leaving four, his opponent will take also one stone, leaving three stones.

The first player cannot take all three because he may take at most \(2\times 1=2\) stones. So let’s say he takes also one stone, leaving \(2\). The second player can take the two remaining stones and wins.

So \(5\) is a losing position for the first player.

For some winning positions there is more than one possible move for the first player.

E.g. when \(n=17\) the first player can remove one or four stones.

Let \(M(n)\) be the maximum number of stones the first player can take from a winning position at his first turn and \(M(n)=0\) for any other position.

\(\sum M(n)\) for \(n\le100\) is \(728\).

Find \(\sum M(n)\) for \(n\le10^{18}\).

Give your answer modulo \(10^8\).

解决方案

我们把局面扩展成更一般的形式（局面 \((N,m)\)）：

  • 当前剩余 \(N\) 颗石子；
  • 当前玩家本步最多可取 \(m\) 颗（当然也不能超过 \(N\)）。

若本步取走 \(x\) 颗，则下一步对手面对状态 \((N-x,2x)\)。初始局面是 \((n,n-1)\)（因为第一步不能取光）。因此，某个第一步取法 \(x\) 是否必胜，等价于对手在 \((n-x,2x)\) 是否必败。

注意到对固定的 \(N\)，状态 \((N,m)\) 对 \(m\) 具有单调性：若在上限 \(m\) 下存在必胜策略，则把上限放宽只会增加可选行动，不可能把必胜变成必败。于是对每个 \(N\)，都存在一个由游戏本身诱导出的阈值 \(T(N)\)，使得当 \(m\ge T(N)\) 时，\((N,m)\) 为必胜态，而当 \(m<T(N)\) 时为必败态。

接下来要做的，是理解这个阈值究竟由什么结构决定。由于规则把“下一步的最大可取数”固定为 \(2x\)，一种非常自然的制胜思路是：在本步取走 \(x\) 之后，把对手送入一个“怎么走都不舒服”的区间——更具体地说，希望对手下一步的上限 \(2x\) 严格小于剩余局面中某个“不可回避的最小结构块”。如果能做到这一点，对手就连触碰该结构块的资格都没有，局面会被锁死在对己不利的一侧。

这提示我们去寻找一个“局面内禀的最小块”函数 \(u(\cdot)\)，使得通过取走 \(u(N)\) 可以触发如下强约束：\(2u(N)<u(N-u(N)).\)也就是说，取掉最小块后，剩余局面的最小块应当至少“跳跃”到原来的两倍以上。为了让这种“跳跃超过两倍”的现象稳定出现，最紧致、最自然的增长骨架正是斐波那契序列：它恰好提供了“两步跳跃超过两倍”的基本事实。

因此引入 Zeckendorf 表示所使用的斐波那契数列\(F_0=1, F_1=2, F_k=F_{k-1}+F_{k-2}\ (k\ge2).\)在第 \(297\) 题中我们介绍过 Zeckendorf 定理：任意正整数 \(n\) 都能唯一表示为若干个互不相邻的 \(F_k\) 之和。记\(\displaystyle{n=\sum_{j=1}^t F_{i_j}, i_1>i_2>\cdots>i_t, i_{j+1}\le i_j-2.}\)这里“互不相邻”正是为了保证相邻层级之间存在空隙，从而形成我们需要的“跳跃”。

斐波那契数列满足关键不等式\(F_{t+2}=F_{t+1}+F_t>2F_t.\)这意味着：若某个局面的最小块是 \(F_t\)，并且由于“不相邻”约束，下一块至少是 \(F_{t+2}\)，那么你取走 \(F_t\) 之后，对手的上限变为 \(2F_t\)，却仍然严格小于 \(F_{t+2}\)，即对手连下一块的门槛都够不着。这正是前面“希望 \(2x<\) 次小块”的不变式在数值层面的具体落实。

于是，“让最小块与次小块之间至少隔一个下标”的分解体系就自然浮现出来——这恰恰就是 Zeckendorf 分解的特征。换言之，为了让“翻倍上限”与“卡在下一块之前”的机制完美咬合，最自然的刻度体系就是 Zeckendorf 分解；而在这种分解之下，局面的“最小块”也就自然而然地定义为 Zeckendorf 表示中的最小项。记\(z(N)=F_{i_t},\)它就是 \(N\) 的 Zeckendorf 表示里最小的那一块，也将成为后续刻画阈值 \(T(N)\) 的核心量。

首先证明定理：状态 \((N,m)\) 是必败局面 当且仅当\(m<z(N).\)核心证明内容是能不能拿到最小块。

现在证明若 \(m\ge z(N)\)：一定能走到必败态。设 \(z(N)=F_t\)。因为 \(m\ge F_t\)，当前玩家可以取走 \(F_t\)。

看剩余数：\(N-F_t = F_{i_1}+ \cdots + F_{i_{t-1}},\)其中所有项的下标都至少是 \(t+2\)（因为 Zeckendorf 表示不允许相邻下标，既然最小是 \(t\)，下一项最小只能到 \(t+2\)）。

因此剩余的 Zeckendorf 最小项满足\(z(N-F_t)\ge F_{t+2}.\)而 Fibonacci 有\(F_{t+2}=F_{t+1}+F_t>2F_t.\)对手下一步的最大可取数是 \(2F_t\)，于是\(2F_t < z(N-F_t).\)这正是“对手处在必败态”的形式：\((N-F_t,2F_t)\) 满足最大可取数小于最小块。

所以，\(m\ge z(N)\) 时当前玩家必胜。

现在证明，若 \(m<z(N)\)：无论怎么取都会把对手送进必胜态。

此时当前玩家只能取 \(x\le m<z(N)\)。要证明对手必胜，只需证明对手的新状态 \((N-x,2x)\) 满足\(2x \ge z(N-x),\)因为这意味着对手“够得着” \(z(N-x)\)，从而能按上面的那部分走到必败态。

关键在于：当你从 \(N\) 中减去一个比最小块还小的 \(x\) 时，Zeckendorf 归一化会在低位产生更小的 Fibonacci 块，使得新的最小块不会超过 \(2x\)。更具体地说，把 \(x\) 写成 Zeckendorf 形式，设其中最大项为 \(F_j\)，则 \(F_j\le x<F_{j+1}\)，从而\(F_{j+1}\le 2F_j \le 2x.\)

而从 \(N\) 减去 \(x\) 时，必然要“拆借”原来最小块 \(z(N)=F_t\)（因为 \(x<F_t\)，低位没有可直接抵消的块），拆借过程只会生成下标不超过 \(j+1\) 的块，因此得到\(z(N-x)\le F_{j+1}\le 2x.\)于是对手确实满足 \(2x\ge z(N-x)\)，是必胜。

综上，\(m<z(N)\) 时当前玩家必败。定理得证。

由于初态是 \((n,n-1)\)。根据定理，必败当且仅当\(n-1<z(n).\)而 \(z(n)=n\) 当且仅当 \(n\) 本身就是某个 Fibonacci 数（Zeckendorf 只有一项）。此时条件变成 \(n-1<n\) 恒成立，于是这些 \(n\) 全必败。

反之，若 \(n\) 不是 Fibonacci，则存在 \(k\) 使得 \(F_k\le n<F_{k+1}\) 且 \(k\ge 1\)，并且有 \(z(n)\le F_{k-1}\le n-1\)，因此 \(n-1\ge z(n)\)，先手必胜。

所以：必败局面正好是 Fibonacci 数，并且 \(M(F_k)=0\)。

接下来求 \(M(n)\) 的 Fibonacci 分块递推取 \(n\) 的最大 Fibonacci 前缀：设\(n\)满足\(F_k \le n < F_{k+1}, n = F_k + y, 0\le y < F_{k-1}\)（因为 \(F_{k+1}=F_k+F_{k-1}\)，这里 \(k\ge 1\)）。记\(t=\left\lfloor \dfrac{F_k-1}{2}\right\rfloor.\)

当 \(1\le y\le t\)时，考虑首步取 \(x=y\)，剩余变为 \(F_k\)，对手最大可取数为 \(2y\)。由于 \(F_k\) 是必败数，且 \(z(F_k)=F_k\)，对手必败当且仅当\(2y < F_k.\)这正好等价于 \(y\le \left\lfloor \dfrac{F_k-1}{2}\right\rfloor = t\)，成立。

而在这些 \(n=F_k+y\) 中，取 \(y\) 已经把剩余压到区间下界 \(F_k\)，显然没有比 \(y\) 更大的“仍能保证必胜”的首步（取更大就会让对手能直接取光或进入可取到最小块的状态）。因此

\[M(F_k+y)=y, 1\le y\le t.\]

当 \(t< y < F_{k-1}\)时，此时若首步取 \(x\ge y\)，剩余 \(F_k+y-x \le F_k\)，且因为 \(y>F_k/2\) 会使 \(2x\ge F_k\)，对手可以直接取光剩余而胜，因此必胜首步必须满足 \(x\le y-1\)，从而剩余写成 \(F_k + (y-x), (1\le y-x < F_{k-1}).\)

由于 \(y-x < F_{k-1}\)，Zeckendorf 表示里不会用到 \(F_{k-1}\)，因此\(z(F_k+(y-x)) = z(y-x).\)对手处于必败态当且仅当\(2x < z(F_k+(y-x)) = z(y-x),\)这与“从规模为 \(y\) 的初态出发，首步取 \(x\) 是否把对手送入必败态”的判据完全一致（因为那时对手状态是 \((y-x,2x)\)）。

因此在这一段里，\(F_k+y\) 与 \(y\) 的“可行必胜首步集合”相同，最大值也相同： \[ M(F_k+y)=M(y), t<y<F_{k-1}. \]

因此，对任意 \(k\ge 1\)、\(0\le y<F_{k-1}\)，有 \[ M(F_k+y)= \begin{cases} 0, &y=0,\\ y, & 1\le y\le \left\lfloor\dfrac{F_k-1}{2}\right\rfloor,\\ M(y), & \left\lfloor\dfrac{F_k-1}{2}\right\rfloor<y<F_{k-1}. \end{cases} \]

这正解释了为什么 \(M(n)\) 在两个相邻 Fibonacci 数之间会出现“先是一段连续整数，再复制更小尺度的图样”。

为求\(\displaystyle{\sum_{n\le N} M(n), N=10^{18}.}\)按上面的分块递推：当 \(n\) 落在同一个区间 \([F_k, F_{k+1}-1]\) 时

  • 前半段 \(M(F_k+y)=y\)，直接用等差数列求和；
  • 后半段 \(M(F_k+y)=M(y)\)，把求和“平移”到更小区间继续算。

代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
from bisect import bisect_right

N = 10**18
MOD = 10**8


def build_fibs(limit: int):
    # F_0=1, F_1=2 (0-based), then F_k=F_{k-1}+F_{k-2}
    f = [1, 2]
    while f[-1] <= limit:
        f.append(f[-1] + f[-2])
    return f

F = build_fibs(N)

def gauss_between(a: int, b: int, mod: int) -> int:
    # sum_{x=a..b} x (a<=b) modulo mod
    if a > b:
        return 0
    n = b - a + 1
    s = a + b
    # divide by 2 safely (mod not prime)
    if n % 2 == 0:
        n //= 2
    else:
        s //= 2
    return (n % mod) * (s % mod) % mod

def sum_M_range(x1: int, x2: int, mod: int = MOD) -> int:
    # sum_{n in [x1,x2]} M(n) mod mod
    if x1 > x2:
        return 0

    i1 = bisect_right(F, x1) - 1
    i2 = bisect_right(F, x2) - 1

    if i1 != i2:
        res = 0
        res = (res + sum_M_range(x1, F[i1 + 1] - 1, mod)) % mod
        for i in range(i1 + 1, i2):
            res = (res + sum_M_range(F[i], F[i + 1] - 1, mod)) % mod
        res = (res + sum_M_range(F[i2], x2, mod)) % mod
        return res

    base = F[i1]
    if x2 == base:
        return 0

    t = (base - 1) // 2

    y_min = x1 - base
    y_max = min(t, x2 - base)

    res = 0
    if y_min <= y_max:
        res = (res + gauss_between(y_min, y_max, mod)) % mod

    if y_max == x2 - base:
        return res

    # tail: M(base+y)=M(y)
    return (res + sum_M_range(y_max + 1, x2 - base, mod)) % mod


# check sample: sum_{n<=100} M(n) = 728
# print(sum_M_range(1, 100) % MOD)

ans = sum_M_range(1, N, MOD) % MOD
print(ans)
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
N = 10 ** 18
mod = 10 ** 8
mp = {0: 0, 1: 0, 2: 0}


def S(n):
    if n in mp.keys():
        return mp[n]
    a, b, c = 1, 1, 2
    s = 0
    while True:
        if c > n:
            c = n + 1
        m = (b - 1) >> 1
        if b + m <= n:
            s += m * (m + 1) // 2 + S(a - 1) - S(m)
        else:
            k = n - b
            s += k * (k + 1) // 2
        if c == n + 1:
            break
        a, b, c = b, c, b + c
    mp[n] = s
    return s


ans = S(N) % mod
print(ans)