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 , let be a function from the integers in to that satisfies the property, for all . If , then there exists an integer such that .

Note the similarity with the continuous version of this theorem:

For real numbers , let be a continuous function from to . If , then there exists a real number such that .

The discrete analog of continuity is the property that going from integer to , we make a jump of at most . 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 and let . We claim that .

Say . Then . This contradicts the fact that is an upper bound on . Say . This implies that (by “continuity”), which contradicts the fact that .

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

*Proof. *Let and let . We claim that .

Say . Pick a number such that (we can do so because of continuity of ). Then . This contradicts the fact that is an upper bound. Say, . Then there exists a such that for all (again by continuity). But, by the definition of supremum there exists an element satisfying . Then , which contradicts the fact that .

Here’s the combinatorial theorem where the discrete version showed up. Let be subsets of defined by . Then for every subset of cardinality there exists a such that .

*Proof. Define for . Then it’s easy to check that for all . In fact, we can define the function on as well by taking . Since has cardinality we have implies , and vice versa. Say . Then without loss of generality we may assume that . Then . Therefore, there exists a such that . *

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

### Like this:

Like Loading...

*Related*

##
About Anurag Bishnoi

A mathematician working at TU Delft.
I am broadly interested in combinatorics and finite geometry.

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.

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!