最近刷水好严重的。

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

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},$$

所以不可能大于了……