## 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 ## About Anurag Bishnoi

A mathematician working at FU Berlin as a postdoc. I am broadly interested in combinatorics and finite geometry.
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$.

• Anurag Bishnoi says:

Indeed. Abhishek Khetan also pointed that out when I told him about this discrete IVT.

• Akash Kumar says:

Recently, I also became aware of a cute application this can be put to.

So, suppose I tell you that the number of prime numbers b/w 1 and N is t. Now I give you some new natural number s s (given in the problem statement)

Also, recall that the result that there are arbitrarily large gaps b/w primes. In particular observe that p( (N + 2) ! + 2) = 0.

By DIVT, the result follows!