TOAD 8 - Here comes Santa

最近刷水好严重的。

（其实主要是各种被抓苦力。）

Problem

是否存在一个 \(n \times n\) 矩阵 \(f\) ，使得每一行的和均为 1，且存在一组 \(p_{1, \dots, n}\) 满足 \(p_1 = 1, |p_i - p_{i - 1}| \leq 1\) 且 \[\sum_{i = 1}^n f_{i, p_i} > H_n = \sum_{i = 1}^n \frac{1}{n}\]

Solution

很显然存在一组等于的解： \[f_{i, j} = \begin{cases} \frac{1}{i} & i < j \\ 0 & i \geq j \end{cases}\] 但是怎么都凑不出一个大于的解，所以我就猜不存在了……

不过答案也是不存在。

证明……我只想到了方向，但是没能构出一个完整的解。大概是这样的：

首先这就是一条 \((1, 1)\) 到第 \(n\) 行的路径是吧，令 \(F_{i, j}\) 为最优解中 \((i, j)\) 的权， \(D_{i, j}\) 为到达 \((i, j)\) 的最小权值和。对于一个 \(i\) ，我们可以求得一个 \(j^{\prime}\) 满足 \(D_{i, j^{\prime}} \leq D_{i, j}\) 。令 \(S_i\) 表示到 \(\sum_{i =1}^i D_{i, j}\) ，我们可以得到：

1. 当 \(j \leq j^{\prime}\) 时， \(D_{i + 1, j} \leq D_{i, j} + F_{i, j}\)
2. 当 \(j > j^{\prime}\) 时， \(D_{i+1,j} \leq D_{i, j - 1} + F_{i, j}\)

枚举所有的 \(j\) ，加起来得： \[\sum_{j=1}^{i+1} D_{i+1, j} \leq \sum_{j=1}^{j^{\prime}} D_{i, j} + \sum_{j = j^{\prime}}^i D_{i, j} + \sum_{i=1}^{i+1}F_{i, j},\] 即 \[S_{i+1} \leq S_i + 1 + \frac{S_i}{i},\] 化开有： \[\frac{S_{i+1}}{i+1} \leq \frac{S_i}{i} + \frac{1}{i+1},\]

所以不可能大于了……