Discrete version of the Intermediate Value Theorem

While working on a combinatorial problem with Potu today I came up with an easy theorem that can be called a discrete version of the Intermediate Value Theorem. It can be stated as follows.

For integers $a < b$, let $f$ be a function from the integers in $[a, b]$ to $\mathbb{Z}$ that satisfies the property, $|f(i+1) - f(i)| \leq 1$ for all $i$. If $f(a) < 0 < f(b)$, then there exists an integer $c \in (a, b)$ such that $f(c) = 0$.

Note the similarity with the continuous version of this theorem:

For real numbers $a < b$, let $f$ be a continuous function from $[a, b]$ to $\mathbb{R}$. If $f(a) < 0 < f(b)$, then there exists a real number $c \in (a, b)$ such that $f(c) = 0$.

The discrete analog of continuity is the property that going from integer $i$ to $i + 1$, we make a jump of at most $1$. It turns out that the similarity of these two theorems extends to their proofs as well. Here’s a proof of the discrete version:

Proof. Let $S = \{x \in \mathbb{Z} \cap [a, b] : f(x) < 0\}$ and let $c = \max S + 1$. We claim that $f(c) = 0$.
Say $f(c) < 0$. Then $c \in S$. This contradicts the fact that $c-1$ is an upper bound on $S$. Say $f(c) > 0$. This implies that $f(c-1) \geq 0$ (by “continuity”), which contradicts the fact that $c - 1 \in S$. $\blacksquare$

And here’s the standard proof for the continuous version.

Proof.  Let $S = \{x \in [a, b] : f(x) < 0\}$ and let $c = \sup S$. We claim that $f(c) = 0$.
Say $f(c) < 0$. Pick a number $c' > c$ such that $f(c') < 0$ (we can do so because of continuity of $f$). Then $c' \in S$. This contradicts the fact that $c$ is an upper bound. Say, $f(c) > 0$. Then there exists a $\delta > 0$ such that $f(x) > 0$ for all $x \in (c - \delta, c + \delta)$ (again by continuity). But, by the definition of supremum there exists an element $c'' \in S$ satisfying $c - \delta < c'' < c$. Then $f(c'') > 0$, which contradicts the fact that $c'' \in S$. $\blacksquare$

Here’s the combinatorial theorem where the discrete version showed up. Let $S_1, \dots, S_{2n}$ be subsets of $\{1, \dots, 4n\}$ defined by $S_i := \{i, i + 1, \dots, i + 2n - 1\}$. Then for every subset $T \subset \{1, \dots, 4n\}$ of cardinality $2n$ there exists a $k$ such that $|S_k \cap T| = n$.

Proof. Define $f(i) = |T \cap S_i| - n$ for $i \in \{1, \dots, 2n\}$. Then it’s easy to check that $|f(i+1) - f(i)| \leq 1$ for all $i$. In fact, we can define the function on $i = 2n + 1$ as well by taking $S_{2n + 1} = \{2n + 1, 2n + 2, \dots, 4n\}$. Since $T$ has cardinality $2n$ we have $f(1) < 0$ implies $f(2n+1) > 0$, and vice versa. Say $f(1) \neq 0$. Then without loss of generality we may assume that $f(1) < 0$. Then $f(2n + 1) > 0$. Therefore, there exists a $k \in \{2, \dots, 2n\}$ such that $f(k) = 0$. $\blacksquare$

After I wrote this argument in my notes, I googled “discrete intermediate value theorem” and found out that someone has already written about this theorem. See this article by Richard Johnsonbaugh. He gives another cute application of this theorem. It’ll be fun to find more applications of this easy theorem.

Edit: As pointed out by Peter, a similar problem is discussed here: http://artofproblemsolving.com/community/c6h14981

Currently a maths PhD student at Ghent University working in the Incidence Geometry research group. I am broadly interested in combinatorics, finite geometry and group theory.
This entry was posted in Real Analysis and tagged . Bookmark the permalink.

3 Responses to Discrete version of the Intermediate Value Theorem

1. Debraj Chakrabarti says:

This “discrete IVT” also can be deduced quite simply from the usual IVT. Let $F:[a,b]\to \mathbb{R}$ be the function which coincides with the given $f$ on integers and is linear in between successive integers. Then this $F$ has a zero in $[a,b]$. If this zero were not achieved at an integer, the fact that $F$ takes integer values at integers means that the slope of the graph of $F$ would be strictly greater than 1 in absolute value, which contradicts the assumption that $|f(i)-f(i+1)|\leq 1$.