A life lesson & cool problems

October 25, 2021

While learning olympiad math in my country I learned relatively little theory compared to what contestants from other countries learned and that was especially the case in combinatorics. I think it's a good thing to know the names of some techniques in combinatorics, even though they can't be labbeled as nicely as in geometry. I want to dedicate this section to a specific problem. Not so long ago this problem appeared on the Bosnian and Herzegovinian IMO Team Selection Test as the first, easiest problem:

This here is an arbitrary example in the case $n=5$. Notice the diametrically opposite points with value $3$.

Before I start explaining the solution to the above problem, let me showcase some other problems with similar flavour:

1. Prove that all roots of the polynomial
   $P(x)=x(x-2)(x-4)(x-6)+(x-1)(x-3)(x-5)(x-7)$
   are real.
2. (Serbia MO 2014) Call a positive integer $n$ crazy if and only if there exist positive integers $a,b>1$ such that $n=a^b+b$. Prove that there exist $2014$ consecutive positive integers such that there are exactly $2012$ crazy numbers among them.
3. (USAMO 2005) Suppose $2n$ points are given in the plane, no three of which are collinear. Suppose $n$ of them are colored blue and the other $n$ are colored red. A line in the plane is called a balancing line if it passes through one blue and one red point and, for each side of the line, the number of blue points on that side is exactly equal to the number of red points on the same side. Prove that there exist at least two balancing lines.

...and the respective outlined solutions:

Problem 1

Look at the polynomials at the inputs $x=0,1,2,3,4,5,6,7$. Pay particular attention to the sign of the value you get. What can you conclude with the information that $P(0) > 0$ and $P(1) < 0 $?

Problem 2

Notice that the first $2012$ numbers aren't all crazy and then note that by shifting an interval of $2014$ consecutive numbers we change the number of crazy numbers in the interval by no more than 1 thus we can hit all values if there exist $2014$ consecutive integers from which more than $2011$ of them are crazy.

Problem 3

Look at the convex hull. Try moving the line and see what changes and by how much.

The point

All three of these problems share the same vibe. They all rely on some sort of continuity. But what does it mean to be continuous? A function is said to be continuous at the point $a$ if the following conditions hold:

First condition

The function at $a$ is defined, i.e. $f(a)$ is defined.

Second condition

The limit at that point exists, i.e. $\lim_{x\to a} f(x)$ exists (i.e. there exists an $L \in \mathbb{R}$ such that for all $\varepsilon > 0$ there exists a $\delta > 0$ such that whenever $|x-a|<\varepsilon$ then $|f(x)-L|<\delta$).

Third condition

Finally, the "most important" condition: $\lim_{x\to a} f(x) = f(a)$ (i.e. exactly $L=f(a)$ in the above expression).

So a functions is said to be continuous on an interval if it is continuous at every point in that interval. Examples of continuous functions are all the "normal" functions we deal with in most of math (for example, all polynomials are continuous). So when is a function not continuous, i.e. discontinuous? Here is an illustration of the types of discontinuity:

A particularily interesting discontinuous function is the Dirichlet Function:

This function is discontinuous at every point in $\mathbb{R}$. For every $p \in \mathbb Q$ and every open interval $(p-\varepsilon, p+\varepsilon)$ there exists an irrational $q \in (p-\varepsilon, p+\varepsilon) $ (not hard to show, this is the statement that the irrationals are dense on $\mathbb R$) so $f(q)=0$ while $f(p)=1$. Similar reasoning shows that all irrational points are also points of discontinuity.

Generalization

As in most things in math, the notion of continuity can be generalized. We can generalize the notion of continuous functions to metric spaces (and topological spaces):

The Intermediate Value Theorem (IVT)

Proof

The proof is a classic real analysis proof and you can find one proof of it here for example. Essentially you abuse the continuity fact with the completeness axiom: every bounded set, finite or infinite, has a supremum/infimum (the smallest/greatest element greater/smaller than all of the elements in that set).

Another cool proof is using a Divide and Conquer approach like Binary Search. Define $a_0=a, b_0=b$ and consider the function value at $\frac{a_n+b_n}{2}$ and adjust the new $a_{n+1}, b_{n+1}$ accordingly. Note that $a_n \leq b_n$ always and $a_n, b_n$ both monotonic sequences so a limit exists. Not hard to show that this limit is the desired $\xi$.

Usually in olympiads continuity for discrete sets is most useful, i.e. for integers (although some specific functional equations might be an exception). Now I present the solution of the introductory problem in two steps:

Solution:

• The antipode of a vertex in a regular $n$-gon is either a midarc (when $n$ is odd) or a vertex (when $n$ is even). Similar holds for the midarcs (vertex - midarc respectively)
• Notice that for $n=2k+1$ (odd) we can just place the numbers $0,1,2 \ldots k-1,k,k,k-1, \ldots ,1,0$ as the vertices. Now there can't be any antipodal points with the same value since one of them is a midarc (which is not an integer) and one of them is a vertex (which is an integer). Therefore, $n$ isn't odd. In the illustration below, black points are vertices of the polygon while the red points are the midpoints of the arcs between the vertices.


The only integer value at a midarc is the red $4$, but it's antipode is $0$ and the rest are not integers.

• For $n=2k$ we prove there always must exist two antipodal points of equal value. Assume there aren't two antipodal points that have equal value. Place a pencil in the middle and keep its tip pointing to the bigger number always. Start rotating it clockwise. At one point the pencil must flip since if it doesn't that would mean it came back to the starting position but in the reverse direction. This can't be since we keep the pencil pointed to the bigger number. This would mean that at that point the numbers are equal but this can't be by our assumption. But when the pencil flips, the midarc between the place it flipped must be the pair of points we're looking for. Thus our assumption is wrong and there must exist two antipodal points of equal value.


When the pencil flips, the midarc between those two points have equal value, hence we're done. $\blacksquare$

These remarks suffice to solve the problem.

Borsuk-Ulam theorem

Formal definition

If $f:S^{n}\to \mathbb {R} ^{n}$ is continuous then there exists an $x\in S^{n}$ such that: $f(-x)=f(x)$.

Bonus: Wobbly table

If you're perchance sitting on a four-legged wobbly chair or sitting at a four-legged wobbly table, you're in luck. Here's how to steady your table or chair without any propping up with papers or similar.

Turn the table around its center in such a way that three legs (label them $A,B,C$) always stay on the surface (the floor).
The distance of the fourth leg to the surface is a function $f(x)$ which depends on the angle $x$ of rotation around the center.
If $f(0)$ (the starting position) is positive, then $f(\pi/2)$ is negative and if $f(0)$ is negative then $f(\pi/2)$ is positive.

Now, the Intermediate Value Theorem assures that there is an angle, where the fourth leg is also on the surface i.e. the table is steady.
You can see the full argument in more detail here, here and here

Practice problems

Introductory

Problem 1

Do there exist $1000$ consecutive positive integers containing exactly $100$ prime numbers?

Problem 2

The polynomial $x^2+13x+5$ is written on a blackboard. Every second Bob changes one of the coefficients of this polynomial by $\pm 1$, such that after some number of seconds the polynomial $x^2+5x+13$ remains. Is it possible that the polynomial on the blackboard was never reducible? (We say that the polynomial $P(x)$ is reducible if it can be expressed as a product of degree $1$ polynomials with integer coefficients)

Problem 3

Define the function $f(n)$ as the sum of the exponents of the canonical represantation of a positive integer $n$. Prove that there exist $2021$ consecutive positive integers, such that exactly $1000$ of them have $f > 11$

Problem 4

Suppose that $1000$ students are standing in a circle. Prove that there exists an integer $k$ with $100 \leq k \leq 300$ such that in this circle there exists a contiguous group of $2k$ students, for which the first half contains the same number of girls as the second half.

Intermediate

Problem 1

Polynomials $F$ and $G$ satisfy: \[ F(F(x)) > G(F(x)) > G(G(x)) \] for all real $x$. Prove that $F(x) > G(x)$ for all real $x$.

Problem 2

Call a positive integer $n$ crazy iff there exist positive integers $a,b>1$ such that $n=a^b+b$. Prove that there exist $2014$ consecutive positive integers such that there are exactly $2012$ crazy numbers among them.

Problem 3

Given is a cyclic $50$-gon whose vertices divide the circle in arcs of lengths $1,2,3, \ldots ,50$ in some order. Every two opposite arcs differ by at least $25$. Prove that the $50$-gon contains two parallel sides.

Problem 4

Find all continuous functions $f:\mathbb R \to \mathbb R$ such that$$f(x)+f(y)=f(x+y)+f(x)f(y)$$for all $x,y\in \mathbb R.$

Advanced

Problem 1

Suppose $2n$ points are given in the plane, no three of which are collinear. Suppose $n$ of them are colored blue and the other $n$ are colored red. A line in the plane is called a balancing line if it passes through one blue and one red point and, for each side of the line, the number of blue points on that side is exactly equal to the number of red points on the same side. Prove that there exist at least two balancing lines.

Problem 2

Given any positive integer $c$, denote $p(c)$ as the largest prime factor of $c$. A sequence ${a_n}$ of positive integers satisfies $a_1>1$ and $a_{n+1} = a_n+p(a_n)$ for all $n\geq 1$. Prove that there must exist at least one perfect square in the sequence ${a_n}$.

Problem 3

Each edge of a complete graph with $101$ vertices is marked with $1$ or $-1$. It is known that the absolute value of the sum of numbers on all edges is less than $150$. Prove that the graph contains a path visiting each vertex exactly once such that the sum of numbers on all edges of this path is zero.

Problem 4

Find all functions $f: (0, \infty) \to (0, \infty)$ such that \begin{align*} f(y(f(x))^3 + x) = x^3f(y) + f(x) \end{align*}for all $x, y>0$.