Project Euler 794

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

Project Euler 794

题目

Seventeen Points

This problem uses half open interval notation where \([a,b)\) represents \(a \le x < b\).

A real number, \(x_1\), is chosen in the interval \([0,1)\).

A second real number, \(x_2\), is chosen such that each of \(\left[0,\dfrac{1}{2}\right)\) and \(\left[\dfrac{1}{2},1\right)\) contains exactly one of \((x_1, x_2)\).

Continue such that on the \(n\)-th step a real number, \(x_n\), is chosen so that each of the intervals \(\left[\dfrac{k-1}{n}, \dfrac{k}{n}\right)\) for \(k \in \{1, \dots, n\}\) contains exactly one of \((x_1, x_2, \dots, x_n)\).

Define \(F(n)\) to be the minimal value of the sum \(x_1 + x_2 + \dots + x_n\) of a tuple \((x_1, x_2, \dots, x_n)\) chosen by such a procedure. For example, \(F(4) = 1.5\) obtained with \((x_1, x_2, x_3, x_4) = (0, 0.75, 0.5, 0.25)\).

Surprisingly, no more than \(17\) points can be chosen by this procedure.

Find \(F(17)\) and give your answer rounded to \(12\) decimal places.

解决方案

令\(N=17\)。固定某一步 \(t\)，设 \(x_1,\dots,x_t\) 排序后为\(y_1 < y_2 < \cdots < y_t.\)由于 \(t\) 个区间\(\displaystyle{\left[0,\frac1t\right),\left[\frac1t,\frac2t\right),\dots,\left[\frac{t-1}{t},1\right)}\)从左到右互不重叠，并且每个区间恰好有一个点，因此第 \(k\) 个区间中的点只能是第 \(k\) 小的点 \(y_k\)。于是必有\(\displaystyle{y_k\in \left[\frac{k-1}{t},\frac{k}{t}\right)(k=1,\dots,t).}\)

换句话说：只要知道 \(x_1,\dots,x_t\) 的相对大小顺序，就能确定它们在第 \(t\) 步必须分别落在哪个等分区间里。 用一个排列 \(p_1,\dots,p_t\) 表示排序关系：\(x_{p_1} < x_{p_2} < \cdots < x_{p_t},\)则立即得到对每个 \(k\) 的强制约束：\(x_{p_k}\in \left[\dfrac{k-1}{t},\dfrac{k}{t}\right).\)这条关系对所有 \(t=1,2,\dots,n\) 都必须同时成立。

核心难点在于：同一个 \(x_i\) 既要满足它在第 \(i\) 步加入时的分桶规则，也要在后续所有步继续满足新的更细分桶规则。

为此引入一种状态表示：隔离区间。在某一步 \(t\)，把当前 \(t\) 个点按从小到大排序。用 \(I_1,I_2,\dots,I_t\) 表示它们分别可能落入的区间范围，其中

  • 第 \(k\) 小的点必须落在 \(I_k\) 内；
  • \(I_k\) 总是某个半开区间；
  • 并且必有\(I_k\subseteq \left[\dfrac{k-1}{t},\dfrac{k}{t}\right).\)

初始 \(t=1\) 时，唯一的隔离区间就是\(I_1=[0,1).\)当 \(t\) 增加时，每一次都会引入新的等分区间约束，从而把已有的 \(I_k\) 进一步收紧为交集（或者导致不可行）。

假设在某一步 \(t\)，我们已经有排好序的隔离区间列表：\(I_1,I_2,\dots,I_t.\)下一步 \(t+1\) 会把 \([0,1)\) 切成 \(t+1\) 个新区间：\(J_j=\left[\dfrac{j}{t+1},\dfrac{j+1}{t+1}\right)(j=0,1,\dots,t).\)

要求新加入的 \(x_{t+1}\) 与原来的 \(t\) 个点一起，使得每个 \(J_j\) 中恰好一个点。由于区间按从左到右排列，等价于：

  • 在 \(J_0,J_1,\dots,J_t\) 中，恰好有一个区间将承载“新点”，其隔离区间就可以直接取为该 \(J_j\)；
  • 其余 \(t\) 个 \(J_j\) 必须各匹配一个旧点；
  • 每个旧点的隔离区间要被收缩为与对应 \(J_j\) 的交集。

关键在于：每个旧隔离区间 \(I_k\) 的长度不超过 \(1/t\)，而新格子的宽度是 \(1/(t+1)\)。对 \(t\ge2\) 有\(\dfrac1t < \dfrac{2}{t+1},\)因此一个 \(I_k\) 最多只能跨越两个相邻的 \(J_j\)，不可能跨过三格以上。这意味着旧点到底落左格还是右格最多产生很小的局部分支，可以用 DFS 快速枚举。

一旦某一步 \(t\) 的隔离区间列表 \(I_1,\dots,I_t\) 被确定，所有点的取值只需要满足\(y_k \in I_k.\)这些约束彼此独立（每个点只受自己所在区间限制），并且半开区间允许取左端点，因此在该状态下，使\(y_1+\cdots+y_t\)最小的选择就是\(y_k = \text{left}(I_k).\)

于是：\(F(n)\) 等于所有可行最终隔离区间列表中，左端点之和的最小值。 并且这些端点都是有理数（由 \(k/t\) 之类的分割点反复取交集得到），因此可以用分数精确计算。

我们用一个状态表示当前的隔离区间列表（按从小到大排序）：\(S_t=(I_1,\dots,I_t),\)其中每个隔离区间都是半开区间\(I_k=[L_k,R_k)\subseteq \left[\dfrac{k-1}{t},\dfrac{k}{t}\right).\)那么\(f(S_t)\) 表示：从该状态继续扩展到 \(N\) 时，能达到的最小左端点和。

先定义第 \(t+1\) 层的等分格子（按从左到右）为\(J^{(t+1)}_j=\left[\dfrac{j-1}{t+1},\dfrac{j}{t+1}\right) (j=1,2,\dots,t+1).\)

并定义区间交集运算：对任意两个半开区间 \([a,b),[c,d)\)，有

\[ [a,b)\cap[c,d)= \begin{cases} [\max(a,c),\min(b,d)) & \text{if }\quad \max(a,c)<\min(b,d),\\ \varnothing & \text{otherwise.} \end{cases} \]

从 \(S_t=(I_1,\dots,I_t)\) 到 \(S_{t+1}=(I'_1,\dots,I'_{t+1})\) 的一次合法转移，等价于选择：

  • 一个“新点落入的格子编号” \(r\in{1,\dots,t+1}\)；
  • 一个严格递增的注入映射（保持相对顺序）\(\sigma:{1,\dots,t}\to {1,\dots,t+1}\setminus\{r\}.\)

然后令新状态满足\(I'_r = J^{(t+1)}_r,\)以及对每个旧点 \(k=1,\dots,t\)，它被送到的新格子为 \(j=\sigma(k)\)，并发生交集收缩：\(I'_{\sigma(k)}= I_k\cap J^{(t+1)}_{\sigma(k)}.\)

这一转移是可行的充要条件是所有新隔离区间都非空：\(I'_j\ne\varnothing (j=1,\dots,t+1).\)把所有可以从\(S_t\)得到的下一层状态\(S_{t+1}\)组成集合，记为\(\mathcal{T}(S_t).\)

那么我们可以写出状态转移方程： \[ f(S_t)= \left \{\begin{aligned} &\sum_{k=1}^{N}L_k & & \text{if}\quad t=N \\ &\min_{S_{t+1}\in \mathcal{T}(S_t)} \{f(S_{t+1})\} & & \text{else if}\quad t<N \\ \end{aligned}\right. \]

第一个条件是边界条件，最终最小和就是所有左端点相加之和。

初始状态为\(S_1=([0,1)),\)因此最终答案就是\(F(N)=f(S_1).\)

代码

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
from fractions import Fraction
from functools import cache

N = 17

@cache
def f(state):
    isos = [(Fraction(a, b), Fraction(c, d)) for a, b, c, d in state]
    n = len(isos)
    if n == N:
        return sum(l for l, _ in isos)

    nexts = [(Fraction(i, n + 1), Fraction(i + 1, n + 1)) for i in range(n + 1)]
    best = None

    def rec(i, j, did_add, nisos):
        nonlocal best
        if i == n:
            if j == n + 1:
                new_state = tuple(
                    (l.numerator, l.denominator, r.numerator, r.denominator) for l, r in nisos
                )
                v = f(new_state)
                if v is not None and (best is None or v < best):
                    best = v
            elif not did_add:
                rec(i, j + 1, True, nisos + [nexts[j]])
            return

        if j == n + 1:
            return

        L, R = isos[i]
        a, b = nexts[j]

        if R <= b:
            if R <= a:
                return
            rec(i + 1, j + 1, did_add, nisos + [(max(L, a), R)])
            return

        if L >= b:
            if did_add:
                return
            rec(i, j + 1, True, nisos + [nexts[j]])
            return

        rec(i + 1, j + 1, did_add, nisos + [(max(L, a), b)])
        if not did_add:
            rec(i, j + 1, True, nisos + [nexts[j]])

    rec(0, 0, False, [])
    return best


ans = f(((0, 1, 1, 1),))
print(f"{ans:.12f}")