January 2020 – A Point of View.

Herediterily sigma-compact space means countable. Miklos Schweitzer 2019, problem 1.

The first problem of the last Miklos Schweitzer contest has a very short statement.

Problem 1 (Miklos Schweitzer 2019). Prove that if every subspace of a Hausdorff space $X$ is $\sigma$ – compact, then $X$ is countable.

Seeking for a contradiction, suppose on the contrary $X$ is not countable. Since $X$ is $\sigma$ – countable itself, it can be represented as countable union of compact sets. One of those sets, say $X_1$ , is also non countable. Clearly, $X_1$ has the same property as $X$ – it is Hausdorff and every its subspace is $\sigma$ compact. Hereafter, we forget about $X$ and all considerations will be with respect to $X_1$ . The proof is based on the following claims.

Claim 1. Let the compact and Hausdorff topological space $X$ be a disjoint union of two everywhere dense sets $Y,Z$ . Then either $Y$ or $Z$ is not $\sigma$ -compact.

Proof. Suppose on the contrary both $Y,Z$ are $\sigma$ -compact and let $Y=\bigcup_{i=1}^{\infty}Y_i, Z=\bigcup_{i=1}^{\infty}Z_i$ where $Y_i,Z_i$ are compact. Note that $Y_i,i\in \mathbb{N}$ are nowhere dense sets, since they are free of points of $Z$ and $Z$ is dense in $X$ . In the same way, $Z_i$ are also nowhere dense. Hence,

$X=\displaystyle \left(\bigcup_{i=1}^{\infty}Y_i\right)\bigcup \left(\bigcup_{i=1}^{\infty}Z_i \right)$

where $Y_i,Z_i$ are closed (compact) nowhere dense sets. But $X$ , as being Hausdorff and compact, has Baire property (see [3]) and cannot be represent as a countable union of closed nowhere dense sets, a contradiction. $\blacksquare$

Definition. Given a topological space $X$ which can be represent as disjoint union of two everywhere dense subspaces, we call $X$ a resolvable topological space.

Claim 2. Every compact Hausdorff topological space $X$ without isolated points is resolvable.

It is a known result. I think due to Edwin Hewitt [1] (not sure), who had introduced the notion of resolvability. It has many generalization, e.g. it’s true for any locally compact Hausdorff space (see [2], Theorem 3.7). $\blacksquare$

Back to the problem. Let $A_0$ be the set of all isolated points of $X_1$ . In case $A_0$ is uncountable, we are done. Indeed each point of $A_0$ is an open set, and $\bigcup_{a\in A_0}\{a\}$ is a cover of $A_0$ , which doesn’t have a countable subcover. It contradicts with the fact $A_0$ being $\sigma$ -compact, is a Lindelof space. Thus, $A_0$ is at most countable.
Let $\omega_1$ be the first uncountable ordinal. We construct a family of countable sets $A_{\alpha}\subset X_1, \alpha<\omega_1$ using the transfinite induction as follows. $A_0$ is as constructed above. Suppose $A_{\beta}, \beta<\alpha$ have been already chosen. Consider $X_1':=X_1\setminus \left( \bigcup_{\beta<\alpha} A_{\beta}\right)$ . It is non empty set, since $X_1$ is uncountable and $\bigcup_{\beta<\alpha} A_{\beta}$ – at most countable. There are two cases:

$X_1'$ has no isolated points. Then the same holds for $\overline{X_1'}$ . Using Claim 2 for $\overline{X_1'}$ we can find two everywhere dense subsets of it and by Claim 1, one of them is not $\sigma$ -compact, a contradiction.
In the other case let $A_{\alpha}\neq \emptyset$ be the set of all isolated points of $X_1'$ . The same argument as above shows $A_{\alpha}$ cannot be uncountable, otherwise it wouldn’t be $\sigma$ -compact.

By transfinite induction, the construction of the family $A_{\alpha}, \alpha<\omega_1$ is completed. Further, we choose points $a_{\alpha}\in A_{\alpha},\forall \alpha<\omega_1$ . Since $a_{\alpha}$ is an isolated point of $X_1\setminus \left( \bigcup_{\beta<\alpha} A_{\beta}\right)$ , there exists an open set $U_{\alpha}$ (in $X_1$ ) such that $U_{\alpha}$ is free of points of $\left( X_1\setminus \left( \bigcup_{\beta<\alpha} A_{\beta}\right)\right)\setminus \{a_{\alpha}\}$ . In particular, $a_{\beta} \notin U_{\alpha}, \forall \beta, \alpha<\beta<\omega_1$ . Let $X':=\{a_{\alpha}:\alpha<\omega_1\}$ . Since $X'$ is Lindelof as being $\sigma$ -compact and $\{U_{\alpha}: \alpha<\omega_1\}$ is a cover of $X'$ , there exists a countable subcover $\{U_i : i\in I\subset \omega_1\}$ . Let $\alpha := \sup I+1$ . Then $\alpha<\omega_1$ and $i< \alpha, \forall i\in I$ . It means $a_{\alpha}\notin U_{i},\forall i\in I$ , a contradiction.

About motivation.

The interval $[0,1]$ is Hausdorff, compact and uncountable. So, why it is not herediterily $\sigma$ -compact? Because the set of irrational numbers inside $[0,1]$ is not $\sigma$ -compact. The proof of it exploits the Baire category theorem. If the irrationals can be represented as a countable union of compact sets, these sets are nowhere dense, since the rationals are dense. Hence, $[0,1]$ can be represented as countable union of compact, nowhere dense sets – those compact sets plus all the points $\{q\}, q\in\mathbb{Q}\cap [0,1]$ . It contradicts the Baire category theorem.

So, the same approach can be applied for a compact, Hausdorff space, which is separable and does not have isolated points. After some unsuccessful tries, I realized that the existence of a countable dense set can be replaced by existence of two disjoint dense sets, the base space can be partitioned into. That’s how Claim 1 came. I searched the net when a topological space can be partitioned like that and was surprised to find there is a spacial name for such cases. And indeed, the compact Hausdorff spaces without isolated points are resolvable.

But having isolated points is a big problem. For example, any isolated point is not nowhere dense set. So, imagine you have a compact Hausdorff space $X$ with countably many isolated points which are dense in $X$ . Then we cannot apply the Baire theorem like the described case of $[0,1]$ , since any isolated point $\{a\}$ is not nowhere dense.

Thus, we try to remove the isolated points, but the space that remains may also have isolated points. The process of “nibbling” the isolated points was the final obstacle.

References:
[1] A problem of set-theoretic topology by E. Hewitt, Duke Math J., 1943
[2] On resolvability of topological spaces, Oleg Pavlov. Theorem 3.7
[3] Baire category theorem. https://en.wikipedia.org/wiki/Baire_category_theorem

A Bulgarian Winter Competition, 2020. Part II

Problem 11.4. A connected graph $G$ with $N\ge 3$ vertices is given. For any cycle $v_1,v_2,\dots,v_m$ in $G$ there exist three vertices $v_i,v_j,v_k$ which also form a cycle. Two players $A,B$ play the following game. At first, $A$ enumerates the vertices of $G$ with distinct natural numbers from $1$ to $N$ . Then $B$ chooses two natural numbers $N>a>b\ge 1$ and places a white token in the vertex numbered as $a$ and a black token in the vertex numbered as $b$ . After that the players play in turn, starting from $B$ . At each move, $B$ marks some (possibly zero) of the vertices adjacent to the black token and moves the token to an adjacent vertex not yet marked and with a bigger number assigned. At each turn, $A$ moves the white token in an adjacent unmarked vertex. If it’s not possible, the token stays still.
$B$ wins if reaches the vertex numbered with $N$ before $A$ reaches $N$ or any vertex adjacent to $N$ .
Determine whether $B$ has a winning strategy.

Some comments and motivation. Taking the a complete graph as $G$ it easily follows $B$ cannot win in this particular case. So, the answer should be “NO”, $B$ doesn’t have a winning strategy. Apparently, it was not intended as an argument. But, for sure it rules out the possibility the answer were “Yes”. So, most probably, $B$ cannot win, no matter of the graph $G$ and we are expected to prove it.
I mean, the way the question as asked, implies the answer. But had the question been “Determine whether $A$ can always prevent $B$ from winning”, there would be no hint revealed, and the two possible cases – “No”, “Yes” need non-trivial argument.
Anyway, a nice problem!

As a motivation for the following solution, consider $G$ be a tree. Then $A$ can enumerate the vertices, starting from some root, an labeling downwards each level in some order. Thus, $B$ cannot place its token closer to the root than that of $A$ .
In case $G$ has a cycle, we can also construct a spanning tree (by breadth-first-search algorithm (BFS) to label each level by contiguous numbers, tagging the root by $N$ and enumerating downwards the levels. But, this time, there may be cross edges and $B$ could lock the vertices on the tree on the levels closer to the root and prevent $A$ from catching up with $B$ . But BFS algorithm as a bonus constructs a tree $T$ with a good property, often used. Any edge in of the graph that is not in $T$ is a cross edge between vertices either in the same level or in two consecutive levels of $T$ . This fact would allow us to control better the possible moves of the players between levels of the spanning tree. Playing with it by putting edges on the skeleton $T$ , it could be seen an additional effort is needed to enumerate the vertices on the same level in a way not allowing $B$ to hinder $A$ on her way to the root.

Solution.

The idea is to construct a spanning tree using the breadth-first-search algorithm, with an additional criterion of ordering the vertices at each level. We take a vertex $v_0$ and label it with $N$ . This is the level $L_0$ .

The spanning tree/enumeration algorithm. Suppose we have already labeled all vertices up to some level $L_k$ and proceed finding (and labeling at the same time) vetices in the next level $L_{k+1}$ , which is empty at that moment. We start from the vertex $v_1$ with the greatest label in $L_k$ . Assume we are at $v_i\in L_k,i\ge 1$ . We take the set $N_i$ of all neighbours of $v_i$ not already in the tree. We start the following subroutine.
$(*)$ Calculate for each $u\in N_i\setminus L_{k+1}$ the value

$f(u):=\displaystyle \sum_{v\in N(u)\cap (L_k\cup L_{k+1}) }2^{\ell(v)}$

where $\ell(v)$ is the label of $v$ and $N(u)$ is the set of all neighbours of $u$ in $G$ . Take the vertex $u$ with the maximal $f(u)$ , label it with the greatest label not yet used and put it into $L_{k+1}$ . Then again apply the subroutine $(*)$ till exhaust all vertices in $N_i$ .
After all vertices in $N_i$ has been labeled, we proceed to the next vertex in $L_k$ not yet processed and with the greatest label, till finally we have run through all vertices in $L_{k}$ and have filled and labeled the next level $L_{k+1}$ . Thus, we constructed and labeled a spanning tree $T$ $\square$

You see, it’s actually the breadth-first-search algorithm (BFS), but when finding the children of a vertex, we take care of labeling them appropriately, not just randomly. In fact that ordering is a lexicographic one, for a vertex $u$ we arrange $N(u)$ that are already labeled in decreasing order of their labels and choose a vertex with the maximal such string.
BFS guarantees the edges of $G$ not in $T$ can only be cross edges between vertices either in the same level or in two consecutive levels. Moreover a vertes $x\in L_k$ can only be connected with a vertex $y\in L_{k+1}$ which predecessor $x' \in L_k$ has a greater number than $x$ . It’s because $x'$ is processed before $x$ .

For briefness of explanation, visualize the tree $T$ as its root $v_0$ being at the top, its levels $L_0,L_1, \dots$ are placed top to bottom. At each level left to right are arranged the vertices with decreasing labels. We will prove at each move $A$ can place her token in the vertex with label not less than that of $B$ .

Initially, $B$ is at the same level or below $A$ . If $B$ is below $A$ , nothing can prevent $A$ from going up the tree till reaches $v_0$ . So, suppose $A,B$ are initially at the same level, say $L_{k}$ . By $\ell(A)$ resp. $\ell(B)$ we denote the label of the current position of $A$ , resp. $B$ . Note that if $B$ decides to go up, $A$ can do the same, because if $\ell(A)\ge \ell(B)$ there exists a neighbour of $A$ in the upper level, which isn’t marked/locked and with a greater or the same label as that of $B$ ‘s.
Actually, the only way $B$ can prevent $A$ from going up the tree is in case $N(A)\cap L_{k-1}=N(B)\cap L_{k-1}$ and $B$ decides to lock all her neighbours in $L_{k-1}$ and walk on the level $L_k$ . Let’s consider this case.

Suppose, $A$ jumps from a vertex $v_1\in L_k$ to a vertes $v_2\in L_k$ but with a greater label.
We claim

$N(v_1)\cap L_{k-1}\subset N(v_2)\cap L_{k-1}\quad (1)$ .

Indeed, assume there is a vertex $v_1'$ in $L_{k-1}$ which is a neighbour of $v_1$ but not of $v_2$ . Then there also exists a vertex $v_2'$ in $L_{k-1}$ which is a neighbour of $v_2$ but not of $v_1$ , since otherwise the label of $v_2$ would be less than that of $v_1$ . Consider the cycle $v_1v_2v_2'\dots v_0\dots v_1' v_1$ (from $v_2'$ we go up along the tree to $v_0$ and then down to $v_1'$ ). Since $v_1,v_2$ are not connected to levels upper than $L_{k-1}$ (property of BFS algorithm) and $v_1v_2', v_2v_1'$ are not edges, it contradicts with $G$ being a chordal graph. (here is the only place that property of $G$ is used).

Hence, $(1)$ is established. Now, $A$ jumps from $u_1$ to $u_2\in L_k\cap N(u_1)$ with the greatest label. Such one does exist, since otherwise $\ell(u_1)<\ell(v_1)$ . Moreover, $\ell(u_2)\geq \ell(v_2)$ with the same argument. The only case, $B$ can prevent $A$ from escaping to the uper level along the tree is again when $N(u_2)\cap L_{k-1}=N(v_2)\cap L_{k-1}$ due to $(1)$ and $\ell(u_2)\geq \ell(v_2)$ . In this case $B$ must lock again all vertices in $N(v_2)\cap L_{k-1}$ . Proceeding like that, either $A$ escapes on the upper level, on a vertex with a greater label than that of $B$ or both players move along the level $L_k$ till exhaust all their neighbours.

A Bulgarian Winter Competition, 2020. Part I

The annual Bulgarian winter competition was held this year on January 18, 2020 in Yambol, a city in Bulgaria. Each grade, 8 to 12, was given a different set of 4 problems. I plan to post some of the most interesting problems, in my opinion, given at grades 10, 11, 12. Here we begin with the problem 12.4, a pleasant combinatorial one of finding a monochromatic structure in the lattice points colored with two colors.

Problem 12.4. A function $f:\mathbb{N}\times \mathbb{N}\to\{0,1\}$ is given. Prove that there exists an infinite sequence $\{a_i\}_{i=1}^{\infty}$ of strictly increasing natural numbers satisfying

$f(a_i,a_{i+1})=f(a_{i+1},a_{i+2}),\forall i\in\mathbb{N}$

Solution. We may think of the function $f$ as the lattice points $\mathbb{N}\times \mathbb{N}$ being colored with one of the two colors “ $0$ ” and “ $1$ “. The sequence $a_1<a_2<\dots$ we are looking for can be interpret as sequence of monochromatic points $P_1(a_1,a_2), P_2(a_2,a_3), \dots$ (see Figure 1).

Consider the sets of lattice points $Q_n=\{(n,m): m>n,m\in \mathbb{N}\}, n=1,2,\dots$ . In case for all sufficiently large $n$ , each $Q_n$ contains a point colored in “ $0$ “, then we start from any point $P_1$ colored in “ $0$ “, which $x$ coordinate is sufficiently large, and then consecutively hit points $P_2,P_3,\dots$ of the same color.
If the previous case doesn’t hold, it means there are infinitely many $Q_n$ containing only points of color “ $1$ “. In this case, starting from some such $Q_n$ , we construct in a similar way points $P_1,P_2,\dots$ all of color “ $1$ “. $\blacksquare$

It’s also possible to solve the problem using the infinite version of Ramsey’s theorem. Consider the complete graph $G$ with vertices in $\mathbb{N}$ . We color the edge $n\,m, n<m$ with the same color as the value $f(n,m)$ . By Ramsey, there exists an infinite set of vertices $a_1<a_2<\dots$ such that all edges $a_i\,a_j, i<j$ are of the same color, which means the values $f(a_i,a_j),i<j$ are the same.
In the same way, the claim also holds when $f(x,y)$ takes only finitely many values.

A notice on Riemann rearrangement theorem.

A mostly used trick when dealing with series, which is absolutely convergent, is rearranging it in order to estimate it. We are sure the sum of the series doesn’t change. If the series is not absolutely convergent, like $1-\frac{1}{2}+\frac 13-\frac 14+\dots$ , we cannot generally do it. Riemann showed any such series could be rearranged to either be non convergent or to converge to arbitrary limit.

As a result, when dealing with conditionally convergent series (convergent but not absolutely convergent) we avoid to rearrange its terms, it’s like a taboo we don’t like to break. But Riemann’s theorem doesn’t say rearranging such series will spoil it. It just says there exists a rearrangement that spoils the series.
For example, if we swap two terms, obviously the sum of the series remains the same. As a rule, the same is true if we apply some not very wild permutation.

I am trying to say (using so many words) it isn’t prohibited rearranging conditionally convergent series, only we must justify it when doing so. The justification usually is simple, using only definition and some estimates. Here is an example given at SEEMOUS 2019 , I present only part (b), one may see the full statement in [1].

Problem 4, SEEMOUS, 2019. (b) Calculate $\displaystyle \sum_{n=0}^{\infty}(-1)^n\left(\frac{1}{(n+1)^2}-\frac{1}{(n+2)^2}+\frac{1}{(n+3)^2}-\dots \right)$ .

Assume, just for a moment we do not care about rearrangement of terms. See that for some fixed $s\in \mathbb{N}$ there are many therms $\frac{1}{s^2}$ coming from different terms in brackets. Actually, their number is exactly $s$ and their signs are the same: $(-1)^{s+1}$ . That’s, we can formally write the series (I borrowed it from here) as:

$\displaystyle-\sum_{n=0}^{\infty} (-1)^n \sum_{k=1}^{\infty} \frac{(-1)^k}{(n+k)^2}=-\sum_{n \ge 0,k \ge 1} \frac{(-1)^{n+k}}{(n+k)^2}=$

$=\displaystyle -\sum_{s=1}^{\infty} (-1)^s \frac{s}{s^2}=-\sum_{s=1}^{\infty} \frac{(-1)^s}{s}=\ln 2$

We see, the sum of the series most probably is $\ln 2$ . What remains is to justify such rearrangement. An attempt to prove the series is absolutely convergent fails, since it is not.

$\displaystyle \sum_{j=n+1}^{\infty} \frac{1}{j^2}\sim \frac{1}{n}$

and $\sum \frac{1}{n}$ is not convergent. So, we represent the series

$\displaystyle -\sum_{n=0}^{\infty} (-1)^n \sum_{k=1}^{\infty} \frac{(-1)^k}{(n+k)^2}$

as the sum of its first $N$ terms

$S:=\displaystyle -\sum_{n=0}^{N} (-1)^n \sum_{k=1}^{\infty} \frac{(-1)^k}{(n+k)^2}\quad (1)$

and the rest of the terms (its tail).

$\widetilde{S}:=\displaystyle -\sum_{n=N+1}^{\infty} (-1)^n \sum_{k=1}^{\infty} \frac{(-1)^k}{(n+k)^2} \quad (2)$

Each of the $N+1$ terms in $(1)$ can be further split into two parts – the first one, up to $\frac{1}{N^2}$ (with its sign) and and the other part – all the summands after that. So, $S=S_0+S_1$ where

$S_0:= \displaystyle -\sum_{n=0}^{N} (-1)^n \sum_{k<N-n}^{\infty} \frac{(-1)^k}{(n+k)^2} \quad (3)$

$S_1:=\displaystyle -\sum_{n=0}^{N} (-1)^n \sum_{k=N-n}^{\infty} \frac{(-1)^k}{(n+k)^2} \quad (4)$

We can also write $S_0$ as

$\displaystyle S_0=-\displaystyle \sum_{s<N}\sum_{n+k=s}\frac{(-1)^{n+k}}{(n+k)^2}=-\sum_{s<N}(-1)^ss\frac{1}{s^2}=-\sum_{s<N}(-1)^s\frac{1}{s}$

Consider a term in $(4)$

$\displaystyle \sum_{k=N-n}^{\infty} \frac{(-1)^k}{(n+k)^2}$

Summing two consecutive elements yields something $\sim \frac{1}{n+k}^3$ , since they have different signs, and the above sum is something $\frac{1}{N^2}$ . Hence

$\displaystyle S_1=O(\frac{1}{N})$

With the same argument we can estimate $\widetilde{S}$ as

$\displaystyle \widetilde{S}=O(\frac{1}{N})$

and finally

$S_0+S_1+\widetilde S=\displaystyle -\sum_{s<N}(-1)^s\frac{1}{s}+O(\frac{1}{N})$

The result follows.

References.
[1] https://artofproblemsolving.com/community/c7h1804961

Tiling the Plane by a Polygon.

I’ve met the following problem, given at a Bulgarian international math competition, Sozopol 2015, [1]. It gives some sufficient condition when the lattice points on the plane can be covered by certain pattern. At first, one may wonder how it should be attacked, because the information about the pattern (polygon) is very general. But, as sometimes happens, the more general is the condition, the less difficult is the solution.
Anyway, I liked it and had a pleasure solving it. A nice problem. Here is the statement.

Problem. (a Bulgarian math competition) The plane is cut into unit squares, which are colored in $n$ colors. A polygon $P$ is composed of $n$ unit squares, its boundary lying on their sides. It is known that any cell polygon, obtained by translating $P$ , covers $n$ unit squares of distinct colors. Prove that the plane can be covered with copies of $P$ , such that each cell is covered exactly once.

Solution. Consider a coordinate system, such that each square has coordinates $(x,y), x,y\in\mathbb{Z}$ . WLOG, assume the square $(0,0)$ is black and $(0,0)\in P$ where by $P\subset \mathbb{Z}^2$ we denote the set of all squares inside the given polygon. For any $v\in\mathbb{Z}^2$ by $v+P$ we denote the translation of $P$ by vector $v$ , i.e. the set $\{ v+p: p\in P\}$ .
Denote by $B$ the set of all black squares in the plane and consider the family of polygons $\mathcal{P}:= \{b+P : b\in B \}$ .

Claim. The sets of the family $\mathcal{P}$ cover $\mathbb{Z}^2$ as required.

Proof. First, we prove any two distinct sets $P_1,P_2\in \mathcal{P}$ are disjoint. Let $P_1=b_1+P,P_2=b_2+P$ . Suppose on the contrary $\mathbb{Z}^2 \ni z_0\in P_1\cap P_2$ . Consider the set

$X:= \{b_1+v : v\in \mathbb{Z}^2, z_0\in v+P_1 \}.$

Note that $X$ is a translation of $P$ , i.e. there exists a vector $v\in\mathbb{Z}^2$ with $X=v+P$ (a picture would be helpful). It easily follows, $b_1,b_2\in X$ , a contradiction since both $b_1,b_2$ are black squares.

Now, let’s see there isn’t uncovered square by the family $\mathcal{P}$ . Seeking a contradiction, suppose it not true, i.e. there exists $z_0\in\mathbb{Z}^2$ such that $z_0\notin P', \forall P'\in\mathcal{P}$ . Consider the set

$Y:= \{ b_1+v : v\in\mathbb{Z}^2, z_0\in v+P_1\}.$

Again, $Y$ is some translation of $P$ . Then, there exists a black square $b\in Y$ . But $z_0\in b+P$ , a contradiction. $\blacksquare$

References
[1] https://artofproblemsolving.com/community/c6t309f6h1984212s1_problem_4_of_fourth_round

On an Extremal Property of the Chebyshev Polynomials.

The first thing that occurs to me hearing “Chebyshev polynomial” is the fact it oscillates wildly and neatly in $[-1,1]$ . This is the only fact that justifies the special name it has. Its extremal properties and the role it plays in the uniform approximation with polynomials are also based on that fact.

One well known extremal property is that among all polynomials $P$ of degree $n$ with senior coefficient $1$ (i.e. monic polynomials), the calibrated Chebyshev polynomial $2^{-n+1}T_n(x)$ has the smallest maximal magnitude in $[-1,1]$ , i.e. $\max_{x\in[-1,1]} |P(x)|$ is smallest when $P=T_n$ .

Another extremal property, I want to discus here, is that among all polynomials of degree $n$ and with magnitude at most $1$ in $[ -1,1]$ , the Chebyshev one has the greatest magnitude outside $[-1,1]$ . More precisely

Theorem 1. Let $P(x)$ be a polynomial of degree $n$ with $|P(x)|\leq 1, \forall x\in[-1,1]$ and $T_n(x)$ be the Chebyshev polynomial of degree $n$ . Then

$|P(x)|\leq |T_n(x)|, \forall x\notin [-1,1].$

This claim allows us when knowing the behavior of a polynomial in some interval (i.e. its maximal absolute value) to predict its magnitude outside that interval. I think, it was first discovered by P. Chebyshev, but not quite sure. Although it may seem to involve hard calculations, in fact its proof is short and pleasant.

Proof. Suppose on the contrary there exists $x'\notin [-1,1]$ such that $|P(x')|>|T_n(x')|$ . Let $x_k:=\cos\left(\frac{k\pi}{n} \right), k=0,1,\dots,n$ . Apparently $T_n(x_k)=\pm 1, k=0,1,\dots,n$ , moreover $T_n(x)$ takes alternatively values, $1,-1$ at the knots $1=x_0>x_1>\dots >x_n=-1$ .

We may assume $|P(x)|<1$ in $[-1,1]$ , otherwise we may consider $cP(x)$ instead of $P(x)$ , where $0<c<1$ is close to $1$ and such that $c|P(x')|>|T_n(x')|$ also holds.
Suppose WLOG $x'>1$ . We also may assume $P(x')>T(x')$ , otherwise we would take $-P(x)$ . Consider now the polynomial $Q(x):= T_n(x)-P(x)$ . It changes its sign alternatively at $x_0,x_1,\dots,x_n$ , hence there exist $n$ points $\xi_k\in (x_k,x_{k+1}),k=0,1,\dots,n-1$ where $Q(x)$ vanishes. There also exists a point $\xi_n$ inside $(1,x')$ with $Q(\xi_n)=0$ , since $Q(1)>0, Q(x')<0$ . Thus, we have found $n+1$ distinct roots of $Q(x)$ (which is of degree $n$ ) implying $P(x)\equiv T_n(x)$ , a contradiction. $\blacksquare$

We’ll consider some applications of this property.

Problem (PFTB, handouts, etc.). Let $a_0, a_1,\dots, a_n$ be real numbers such that $| a_nx^n +a_{n-1}x^{n-1}+\dots+a_0| \leq 1$ for all $x \in [-1,1]$ . Prove that $| a_0x^n +a_{1}x^{n-1} + \dots+a_n| \leq 2^{n-1}$ for all $x \in [-1,1]$

Proof. Denote $P(x):= a_nx^n +a_{n-1}x^{n-1}+\dots+a_0$ . Applying Theorem 1 we get

$P(\frac{1}{x})\leq T_n(\frac{1}{x}), \forall x\in [-1,1],x\ne 0.$

It yields

$|a_0x^n+a_1x^{n-1}+\dots+a_n|\leq x^n T_n(\frac{1}{x}),\forall x\in[-1,1]$

It is well known $T_n(y)=\frac{1}{2}\left( y-\sqrt{y^2-1}\right)^n +\frac{1}{2} \left(y+\sqrt{y^2-1}\right)^n$ for $|y|\ge 1$ . Hence

$x^nT_n(\frac{1}{x})=\frac{1}{2}\left( 1-\sqrt{1-x^2}\right)^n +\frac{1}{2} \left(1+\sqrt{1-x^2}\right)^n,\forall x\in [-1,1].$

But $(1-t)^n+(1+t)^n$ attains its maximum in $[0,1]$ when $t=1$ , thus the RHS of the above inequality is at most $2^{n-1}$ and the result follows. $\blacksquare$

The above theorem can be generalized.

Teorem 2. Let $P$ be a polynomial of degree $n$ and

$|P(x)|\leq M, \forall x\in I$ ,

where $I\subset \mathbb{R}$ is some interval, and $M>0$ . Then for any $x\notin I$ and at distance $\delta>0$ from $I$ holds:

$\displaystyle |P(x| \leq M\cdot \frac{1}{2}\left[\left(1+\frac{2\delta}{|I|}-\sqrt{ \left(1+\frac{2\delta}{|I|}\right)^2-1} \right)^n + \left(1+\frac{2\delta}{|I|}+\sqrt{ \left(1+\frac{2\delta}{|I|}\right)^2-1} \right)^n \right]$

Indeed, we may transform $I$ into $[-1,1]$ , apply Theorem 1 and transform the estimate back to the interval $I$ .

Problem (Komal A. 654) Let $p(x)$ be a polynomial of degree at most $n$ such that $|p(x)|\le\cfrac{1}{\sqrt{x}}$ for $0<x\le 1$ . Prove that $|p(0)|\le 2n+1$ .

I didn’t manage to prove the stated estimate (which btw is sharp) using the method described. I only managed to prove $|p(x)|< 3n$ . Nevertheless, decided to include it here just as an illustration. One can see a beautiful solution using the Markov’s inequality in [3].

We apply the above estimate for our polynomial $P(x)$ in the interval $I=[1/(kn^2), 1]$ and $x=0$ , where $k\geq 1$ is a constant not yet fixed. For this case $\delta=1/kn^2\,,\, M=\sqrt{k}n$ . Making some rough calculations, we arrive at:

$|P(0)| \leq \frac{1}{2}\sqrt{k}n \left(1+ \left(1+\frac{2}{kn}\right)^n \right) \leq \frac{\sqrt{k}}{2}\left(1+e^{2/k} \right)n$

Setting $k=3$ , it can be obtained the RHS is less than $3n$ , hence $|P(0)|<3n$ .

References:
[1] https://artofproblemsolving.com/community/c6h1776644
[2]https://artofproblemsolving.com/community/c6t169f6h1980765_bounding_reciprocal_polynomial
[3] Komal, A.654, https://artofproblemsolving.com/community/c7h1370903

Ore-Gale-Ryser Theorem. Olympiad Application.

I’ll present an interesting method about $f$ – factoring of a given bipartite graph and two olympiad problems it successfuly applies to. The theorem below is a generaliztion of the Hall’s marage theorem.

First some terminology. Suppose we have a biparite graph $G(A,B)$ and some function $f:A\cup B\to \mathbb{Z}_{\ge 0}$ satisfying $f(v)\leq \deg(v), \forall v\in A\cup B$ . The question is: Can we delete some edges of $G$ , such that the degree of any vertex $v\in A\cup B$ equals $f(v)$ ? In other words, is it possible by deleting some edges to obtain some prescribed degrees?
If it’s possible, we say $G$ allows $f$ – factoring. Here is a characterization when it happens.

Theorem (Ore-Gale-Ryser). $G$ allows $f$ – factoring if and only if the following two conditions hold.

$(i)\quad \displaystyle \sum_{a\in A}f(a)= \sum_{b\in B}f(b)$

$(ii)\quad \displaystyle \sum_{x\in X} f(x)\leq \sum_{y\in B\setminus Y}f(y)+m(X,Y)$
for any $X,Y; X\subset A, Y\subset B$ , where $m(X,Y)$ denotes the number of edges connecting $X$ and $Y$ .

Suppose $G$ is $f$ – factorable. The first equality is obvious. The second inequality is also simple. Just remove from the RHS the edges that are between $B\setminus Y$ and $A\setminus X$ , and we obtain the LHS.
So the essential point is these two conditions are sufficient $G$ to be $f$ – factorable. I’ll omit for now being the proof, maybe I would include it on a post about max flow – min cut theorem. There are two approaches known to me – one by induction, and the other – as presented in [1] (7.16) – uses the mentioned max flow – min cut theorem.
Note that in case $f(v)=1, \forall v\in A\cup B$ , $f$ being $f$ – factorable means exactly there is a full matching. Setting in (ii) $Y:= B\setminus N(X)$ we obtain $|X|\leq |N(X)|$ , since $m(X,Y)=0$ . This is exactly the Hall’s marriage theorem condition. Now, time to get hands on applications.

Flipping coins. Indian TST 2019 , see [4].
There are $2019$ coins on a table. Some are placed with heads up and others tails up. A group of $2019$ persons perform the following operations: the first person chooses one coin and then turns it over, the second person chooses two coins and turns them over and so on and the $2019$ -th person turns over all the coins. Prove that no matter which sides the coins are up initially, the $2019$ persons can come up with a procedure for turning the coins such that at the end of the operations all of the coins have the same side up.

A natural idea is to use induction on odd number of coins, which leads to a pleasant straightforward solution, see [4].
To apply Ore-Ryser, we consider the full bipartite graph $G(A,B)$ on the set of persons – $A=\{A_1,A_2,\dots,A_{2019}\}$ and coins – $B=\{B_1,B_2,\dots,B_{2019}\}$ . Suppose $b=(b_1,b_2,\dots,b_{2019})$ is any ordered sequence of bits $b_i\in \{0,1\},i=1,2,\dots,2019$ . We want to show existence of $f$ – factoring of $G$ , where $f$ satisfies: $f(A_i)=i, f(B_i)\equiv c_i \pmod{2}, i=1,2,\dots,2019$ where the binary sequence $c=(c_1,c_2,\dots,c_{2019})$ is either $b$ or the negation $\overline{b}$ of $b$ .
We choose $c$ to be the one among $b, \overline{b}$ which consists of even number of $1$ ‘s and let that number is $2r, 0\le r\le 1009$ . We define $f$ over $B$ as follows

$f(B_i):= 1011,i=1,2,\dots,r$
$f(B_i):=1009, i=r+1, r+2,\dots, 2r$
$f(B_i)=1010, i=2r+1,2r+2,\dots,2019$ .

As said $f(A_i)=i,i=1,2,\dots,2019$ . We prove now, $G$ has a $f$ factor. The first condition of Ore-Ryser holds by definition of $f$ since $\sum_{a\in A}f(a)=2019\cdot 1010$ . So, for any $X\subset A, Y\subset B$ we have to check the second condition:

$\displaystyle \sum_{x\in X}f(x)\le m(X,Y)+ \sum_{y\in B\setminus Y} f(y)\quad (1)$

Denote $|X|=n, |Y|=m; 0\le n,m\leq 2019$ . Clearly $m(X,Y)=nm$ . The maximal possible value of the LHS of (1), as $n$ being fixed, is in case $X=\{2019,2018,\dots, 2019-(n-1)\}$ and then $\sum_{x\in X}f(x) =n(2019-(n-1)/2)$ .

Let’s first consider the case $m\ge 1010$ . Then $2019-m \le 1009$ . A lower bound of $\sum_{y\in B\setminus Y} f(y)$ is $1009(2019-m)$ . Hence, it’s enough to check

$n(2019-(n-1)/2)\le mn + 1009(2019-m)$

$n(2019-(n-1)/2)\le m(n-1009)+1009\cdot 2019$

Two cases are possible: 1) $n<1009$ and 2) $n\ge 1009$ . For the first case it’s enough to check it for $m=2019$ , since it’s the worst scenario for the RHS. For the second case the worst scenario is $m=1010$ . The calculation is straightforward.

Now, the case $0\le m\le 1009$ . Then $2019-m\geq 1010$ . There are $2019-m$ terms in the sum $\sum_{y\in B\setminus Y} f(y)$ , so a lower bound of it (as $m$ being fixed) is achieved when as many as possible terms are equal to $1009$ . Hence $\sum_{y\in B\setminus Y} f(y)\ge 1009\cdot 1009 +1010 +(2019-m-1010)\cdot 1011$ . Putting it into $(1)$ and after short calculations it boils down to check

$n(2019-(n-1)/2)\le m(n-1011)+1009\cdot 2020+1010$

Here are two cases to be considered. 1) $n<1011$ and 2) $n\geq 1011$ . In the firs case the worst case for the RHS is $m=1009$ . For the second case, it is $m=0$ . A calculation shows the inequality holds for the both cases, in the second one an equality is achieved.
Thus, the second condition of Ore-Ryser is established.

Regular subgraph existing, Mongolia TST, see[3].
Let $n$ and $d$ be positive integers satisfying $d<\dfrac{n}{2}$ . There are $n$ boys and $n$ girls in a school. Each boy has at most $d$ girlfriends and each girl has at most $d$ boyfriends. Prove that one can introduce some of them to make each boy have exactly $2d$ girlfriends and each girl have exactly $2d$ boyfriends. (If a girl has a boyfriend, she is his girlfriend as well and vice versa).

This problem can be found in the excellent book [1] of Laszlo Lovasz – “Combinatorial Problems and Exercises”- chapter 7, problem 18. The solution there is also based on Ore – Ryser approach. We consider the grap $G(A,B)$ (girls $A$ , boys $B$ ) that is complementary to the given bipartite graph. Clearly $d_{G}(v)\le n-d, \forall v\in A\cup B$ . We want to delete some edges of $G$ and obtain a regular $n-2d$ subgraph, that’s a $f$ – factor, where $f(v)=n-2d$ .
It is enough to check the second condition (ii) of Ore-Ryser. A straightforward calculation shows it’s true, and the result follows.

References:
[1] Laszlo Lovasz, Combinatorial problems and Exercises, 2-nd ed. 1992.
[2] O. Ore, Theory of Graphs, Amer. math. Soc. Coll. 1962.
[3] Mongolia TST 2011 Test 3 #3 https://artofproblemsolving.com/community/c6h444063
[4] Indian TST, test 2, p.3 https://artofproblemsolving.com/community/c6h1893477