随记 – 三月二十八日 – 介值定理

介值定理

若有连续函数$f: [a, b] \mapsto \mathbb{R}$，且不失一般性地，令$a< b, f(a)< f(b)$，则对于任意实数$x\in [f(a), f(b)]$，存在$c \in (a, b), f(c)=x$。

容易由实数完备性证明。直观理解，即可以画出一段连续曲线，其两端点分别为$(a, f(a)), (b, f(b))$，而笔不离开纸面。

离散函数值上的介值定理

若存在函数$f(x) \in \mathbb{Z}, x \in \mathbb{Z}$，且满足$|f(x)-f(x+1)|\leq 1$，则对于$a<b, f(a)<f(b)$，若有整数$x \in [f(a), f(b)]$，存在一个$c \in (a, b), f(c)=x$。

证明显然。

在OI中的实际意义？

我们常遇到这样一类函数：在某些数列上进行统计，邻项函数值之间的差为$\{-1, 0, 1\}$，如括号序前缀和（$\text{‘(‘} \rightarrow +1, \text{‘)’} \rightarrow -1$），则可以通过上述性质判断某两点之间函数值是否存在。

例如CF1695C – Zero Path，本质上路径上数字和是一个满足上述条件的整数离散函数。

再例如CF1658F – Juju and Binary String，可以将题意转化为一个函数$f(x) \in [0, n], x \in [0, n] \land \exists x_p, f(x_p) >0$，且满足上述性质；同时有函数$g(x)=x, x \in [1, n]$，则可以证明一定存在$x_0, g(x_0)=f(x_0)$。