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

Advertisements

About Anurag Bishnoi

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$.

    • 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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s