令函數 $f: \mathbb{N} \to (0,\infty)$,則下列等式成立 $$ \min_{0 \leq k \leq N} \frac{f(k)}{\max_{i\leq k}f(i)} = \min_{0\leq \ell \leq k \leq N} \frac{f(k)}{f(\ell)} $$ Proof: 令 $$\frac{f(k_0)}{f(\ell_0)} := \min_{0\leq k\leq N}\frac{f(k)}{ \max_{i\leq k} f(i)} $$ 其中 $\ell_0\leq k_0$ 使得 $\text{min}_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}\leq\frac{f(k_0)}{f(\ell_0)}$。 另一方面,令 $$\frac{f(k_1)}{f(\ell_1)}= \min_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)} $$ 且 $\ell_1\leq k_1$,則我們必定有 $$\frac{f(k_0)}{f(\ell_0)}\leq\frac{f(k_1)}{ \max_{i\leq k_1}\;f(i)}\leq\frac{f(k_1)}{f(\ell_1)}$$ 由上述結果,我們得到 $$ \frac{f(k_0)}{f(\ell_0)}=\frac{f(k_1)}{f(\ell_1)} $$ 亦即 $$\min_{0\leq k\leq N}\frac{f(k)}{ \max_{i\leq k} f(i)}= \min_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}$$ 至此得證。$\square$
If you can’t solve a problem, then there is an easier problem you can solve: find it. -George Polya