Discrete Continuity in Combinatorics

This blog post corresponds to my newest olympiad handout on discrete continuity.

The concept of discrete continuity is an extremely effective and versatile method in tackling a wide variety of combinatorics problems. This technique has been used extensively for many years especially in particular classes of problems. Here, after a quick recap of the basics we shall look at the solutions to some of the more interesting problems from the Practice Problems section of the handout.

The idea behind the notion of discrete continuity is that if an integer valued function changes by at most one at each step it must be surjective within its range.

A common style of problems which falls prey to this technique are number theory problems which ask you to show there exists a string of consecutive integers of which exactly satisfy a desired property for some choice of .

The recipe for these problems is quite simple – show there exists strings of consecutive integers with at least and at most integers which satisfy respectively, and use the discrete intermediate value theorem to win.

Here is Serbia 2014 Problem 4.

A natural number is said to be crazy if and only if there exists positive integers for which . Show that there exists a set of 2014 consecutive natural numbers of which exactly 2012 are crazy.

We look at the function which records the number of crazy integers in the set .

Let a number be called sane if it is not crazy. Note that since 1,2,3,4,5 are all sane due to size restrictions, . Furthermore, for all positive integers we have which is clearly crazy. Hence, .

Now comes the punchline – since (think about why this is true), and there must have been some point where was exactly equal to 2012.

Part of the reason why this method is so effective is that it is an existential technique. It guarantees the existence of objects satisfying the criteria you need without explicitly mentioning what they are. For example, in the above problem we don’t even have any idea about the size of the set of 2014 consecutive integers which work (except that it lies between the two extremes – 1 and .

Next, we shall look at an interesting problem which appeared on the 2004 Putnam.

Basketball star Yang Liu’s team statistician keeps track of the number, , of successful free throws he has made in his first attempts of the season. Early in the season, was less than 80% of , but by the end of the season, was more than 80% of . Was there necessarily a moment in between when was exactly 80% of ?

The key idea is to define the function .

Before we proceed, a natural question to ask is – ‘why this function?’. The answer is simple. It is zero precisely when was exactly 80% of . It is in a sense, a measure of how ‘close’ a moment is to being an 80% success rate.

Our hope is that would satisfy discrete continuity. Indeed, when Liu makes a successful throw both and increase by one, causing to increase by one as well. However, when Liu fails a throw, increases by one without changing causing to drop by four.

Clearly, does not satisfy discrete continuity, so are we cooked? Thankfully, no! In fact, we do not care how decreases. Since may only increase one at a time, and we know there is a moment when moves from below to above 80% of , must have been exactly zero at this moment.

An interesting thing to note is that this solution only worked since is the ratio of two consecutive integers. For example, if 80% were replaced by 60% the argument would break since the corresponding function would then be which does not satisfy discrete continuity when either increasing nor decreasing, so it is possible for to jump right over zero.

To finish things off we play with some windmills on Brazil 2018 Problem 6.

Consider a set of points in the plane, no three collinear, and the triangles with vertices in . Prove that some point in the plane lies in the interior of at least of these triangles.

What I like most about this problem is that at a glance discrete continuity is an idea that you would never come up with – even if you had 14 bottles of 34% w/w hydrochloric acid to drink last night. Global approaches like pigeonhole seem more promising.

However, experimenting with small cases we make an interesting observation – the ‘center’ of the distribution of points always seems to work. That is, if we consider two lines which divide the plane into four regions such that there are exactly points (note how the total number of points was conveniently set to ) in each quadrant of the plane.

The idea is that if we pick one point from each quadrant, the resulting quadrilateral has at least two triangles pick cover , simply because must lie strictly inside the quadrilateral. Thus, there exists at least,

triangles which cover the point .

With this observation in hand, we have suddenly turned the tides – this is simply a stronger version of Example 11 in the handout!

We first show that for any line in the plane, there exists a line which is parallel to and has exactly points on each side of it. This is clear since starting with a line parallel to not intersecting the convex hull of our set of points, we may push it along until we pass right through the convex hull.

We begin with points on each side of the line and end with implying that by the discrete intermediate value theorem, there exists some intermediate moment where the line split the set of points into two equal groups.

We can also tweak this argument to divide the plane into four quadrants. Simply fix a line and let a variable line start off as and rotate clockwise continuously until it makes a half rotation.

At any moment, and split the plane into four regions. We begin with the regions having exactly points each and end with them having points each implying that at some moment we must have had exactly points in each quadrant, which is exactly what we wanted.