Dragomir Grozev

IMO 2021, Problem 2. A Controversial Inequality.

I’d like to discuss some of the problems given at this year’s International Mathematical Olympiad, held virtually in St. Petersburg, Russia. Let’s begin with the most controversial one – the inequality. By controversial I mean the most discussed one, with variety of opinions – from ardent supporters of this kind of problems to ardent opponents. I think, I know why, but let me first tell you that I like this inequality, it is somehow out of the box, and if this trend continues I might change my mind about whether inequalities should be given at math competitions. So, let me present some opinions from a popular math forum

A delightful problem, perhaps the best inequality in the history of IMO!
TelMarin

Not really. Just because is a nice problem it does not mean it is good for this competetion. And I can probably say this is the most inappropriate problem as a medium problem since it has solution which would be perfect as Undergraduate Olympiad
dangerousliri

Further, a guy, in order to back up the argument that it’s for Undergrad Olympiads, wrote

well you are not 15-17, are you? Cause when I first went to the IMO on 2018 I had not idea what concave or even continuous function even meant…
Hamel

Well, it’s not something to brag about that you went to IMO and had no idea what a continuous or concave function was, but well, I see the idea. By the way, in my country this stuff is taught in high school math program, so by no means it should be considered as undergraduate or rocket science. The only thing you need to solve this problem is that a concave function in some interval $[a,b]$ attains its minimum value either at $a$ or at $b.$ And that a sum of concave functions (in some interval) is also concave. That’s it, and this stuff is taught in high school.
Along these lines, I don’t see why Karamata’s or Jensen’s inequalities, for example, are appropriate for IMO, but this one is not. On the contrary, this fact about concave/convex function is much more intuitive than some of the mentioned.
The issue apparently is that this problem is somewhat out of the box. Many people are ok to apply heavy lines of manipulating standard inequalities, but when it comes to some fresh thinking, they are frustrated.
Moreover, the mere idea is not a stroke of genius. So, you subtract the LHS from the RHS one and get a function $f(x_1,x_2,\dots,x_n).$ You want to prove $f\ge 0.$ The first idea that comes into mind is to fix all the variables, except one, and to vary this one variable in order to see when $f$ gets its minimum. In this way, you may reduce the inequality to some special values of the variables. Sometimes, it is convenient to vary appropriately two of the variables and so on. In this particular case we shift all variables by some offset and calculate the value of the offset that makes $f$ minimal. I mean, this is not an unusual idea.
To be honest, the problem is not easy. I tried it, was pissed off at one point and saw the idea in the AoPS thread ([1], see post #7). I even considered the idea of shifting simultaneously all the variables, but somehow didn’t take into account (don’t know why) that the LHS didn’t change from that transformation. Ok, enough of this talk, here is the problem.

Problem 2, IMO 2021. Show that the inequality

$\displaystyle \sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i-x_j|}\leqslant \sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i+x_j|}$

holds for all real numbers $x_1,x_2,\dots,x_n.$

Solution. Denote the left hand side by $A(x_1,\dots,x_n),$ the right hand side by $B(x_1,\dots,x_n)$ and consider the function

$f(x_1,\dots,x_n):=B(x_1,\dots,x_n)-A(x_1,\dots,x_n).$

We must prove $f(x_1,\dots,x_n)\ge 0.$ The idea is to move (translate) the whole bunch of points $x_i,i=1,\dots,n$ and see when $f$ gets a minimum value. So, let $x'_i:=x_i+t, i=1,2,\dots,n, t\in\mathbb{R}.$ Note that $A$ does not change by this transformation, that is, $A(x'_1,\dots,x'_n)=A(x_1,\dots,x_n).$ We have

$\displaystyle B(t):= B(x'_1,\dots,x'_n)=\sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i+x_j+2t|}$

Consider the function $\phi_{i,j}(t):=\sqrt{|x_i+x_j+2t|}$ as a function of $t\in \mathbb{R}.$ It is a concave in each of the intervals $\displaystyle t\in \left(-\infty, -\frac{x_i+x_j}{2}\right)$ and $\displaystyle t\in \left(-\frac{x_i+x_j}{2},\infty\right).$ Taking into account that sum of concave functions (in some interval) ia also concave, we get that $B(t)$ is concave inside the intervals determined by the points $-(x_i+x_j)/2, i,j=1,2,\dots,n.$
Now, any function $B(t)$ that is concave in $t\in[a,b]$ takes its minimum value in $[a,b]$ either when $t=a$ or when $t=b.$ It means that $B(t)$ attains its minimum value either when $t=-(x_k+x_{\ell})/2$ for some $1\le k,\ell\le n$ or when $t=\pm\infty.$ But since $\displaystyle \lim_{t\to\pm\infty}B(t)=\infty,$ we obtained that the minimum value of $B(t)$ is attained when $t=-(x_k+x_{\ell})/2$ for some $k,\ell$ . In case $k=\ell$ it yields $x'_k=0$ and when $k\ne \ell$ we get $x'_k=-x'_{\ell}.$
To recap, as we move the entire ensemble of points $x_i,i=1,\dots,n$ along the real axis, the minimum of $B$ is attained either when some $x'_k$ hits $0$ or when some $x'_k,x'_{\ell},k\ne \ell$ are symmetric about $0.$
In both cases, all the terms of $f(x'_1,\dots,x'_n)$ that contain $x'_k$ (respectively $x'_k$ and $x'_{\ell}$ ) are canceled no matter of the other values $x'_i, i\ne k$ (resp. $x'_i, i\ne k \text{ and } i\ne \ell$ .) So, we remain with less variables and with a function $f$ with the same pattern. We do the same trick again and again and conclude that $f$ takes its minimum value when some values $x_i$ are zeroes and the others can be partitioned into symmetric pairs about $0.$ In this case $f=0$ and the result follows.

References.
[1] IMO 2021, problem 2, AoPS thread.

Edge Cover of a Bipartite Graph. Part 2.

We continue the previous blog post which relates the size of a minimum edge cover of a bipartite graph with the size of its maximum independent set. Let me briefly recall some of the terms used.
Let $G$ be any graph with vertex set $V$ and edge set $E.$ We call a subset $E_1$ of $E$ an edge cover of $G$ if for any vertex $v$ in $G$ there exists $e\in E_1$ that is incident to $v$ i.e. $e$ covers $v.$
Further we assume $G$ has no isolated vertices, because we cannot cover an isolated vertices with any edge. A subset $V_1$ of $V$ is called independent if there is no edge connecting two vertices of $V_1.$ Denote by $\rho(G)$ and $\alpha(G)$ correspondingly the size of a minimum edges cover and the size of a maximum independent set. We proved that the following inequality holds

$\alpha (G)\le \rho(G)\qquad (1)$

This is true for any graph without isolated vertices, we didn’t use that $G$ is bipartite. In case $G$ is bipartite, we actually have:

$\alpha(G)=\rho(G)\qquad (2)$

In the previous post we proved $(2)$ via Dilworth’s theorem, and here we apply another approach using Hall’s marriage theorem.

A proof using Hall’s marriage condition.

Let $G(A,B)$ be the corresponding bipartite graph with $A,B$ being the two parts of its vertices. We choose an independent set $V_1$ with $|V_1|=\alpha(G)$ and $V_1=A_1\cup B_1$ where $A_1\subset A, B_1\subset B.$ If we prove that there exists an edge cover $E_1$ with $|E_1|=|V_1|$ it would follow that $\alpha(G)\ge \rho(G)$ and taking into account $(1)$ we conclude that $(2)$ holds. Denote for brevity $A'_1:=A\setminus A_1$ and $B'_1:=B\setminus B_1.$

Fig. 1. $A_1\cup B_1$ is a maximum independent set.

Fig. 1. $A_1\cup B_1$ is a maximum independent set.

Claim. There is a perfect matching of $A'_1$ to $B_1$ and $B'_1$ to $A_1$ (see Fig.1).

Proof. The plan is to check that Hall’s marriage condition holds for the two bipartite graphs induced on $A'_1, B_1$ and $B'_1,A_1$ and correspondingly. Take the former one $G'(A'_1, B_1)$ . As usual, for any $S\subset A'_1$ we denote by $N(S)$ the set of all vertices in $B_1$ that have a neighbor in $S.$ Suppose, for sake of contradiction, $|N(S)|<|S|$ for some $S\subset A'_1.$ Consider then the set $V'_1:=A_1\cup (B_1\setminus N(S))\cup S.$ That is, we take $V_1=A_1\cup B_1$ , remove the set $N(S)$ and add the set $S.$ Apparently $V'_1$ is an independent set since there are no edges between $S$ and $B_1\setminus N(S).$ Moreover, $|V'_1|=|V_1|+|S|-|N(S)|>|V_1|$ which contradicts the maximality of $V_1.$ $\blacksquare$

Now, consider all the edges of the matching guaranteed by the above claim. For any vertex $v$ in $A_1$ or in $B_1$ that is unmatched, we add an arbitrary edge that is incident to $v.$ Thus, we obtain exactly $|A_1|+|B_1|$ edges that cover the vertices of the graph. Therefore

$\alpha (G)\ge \rho(G)$

and taking into account $(1)$ we proved $(2)$ holds.

<< To the previous post

Edge Cover of a Bipartite Graph. Part 1.

Here is a problem that connects two characteristics of a graph – its minimum edge cover and its maximum independent set. I was told it was given at a university exam, but it could be an Olympiad problem as well, for example as worded in the Problem 1 in the next section. There is nothing beyond the standard knowledge needed to succeed in any decent high school competition. In some two or three post three different approaches will be presented, using three fundamental results, respectively – Dilworth’s theorem, Hall’s marriage theorem and Max-flow min-cut theorem.
Let $G$ be any graph with vertex set $V$ and edge set $E.$ We call a subset $E_1$ of $E$ an edge cover of $G$ if for any vertex $v$ in $G$ there exists $e\in E_1$ that is incident to $v$ i.e. $e$ covers $v.$
Further we assume $G$ has no isolated vertices, because we cannot cover an isolated vertices with any edge. A subset $V_1$ of $V$ is called independent if there is no edge connecting two vertices of $V_1.$ Denote by $\rho(G)$ and $\alpha(G)$ correspondingly the size of a minimum edges cover and the size of a maximum independent set. Then it holds

$\alpha (G)\le \rho(G)$

It can be obtained easily by mapping each vertex to an edge that covers it. The details will be provided later. This inequality may be strict, for example when $G$ is a triangle with $3$ vertices, we have $\rho(G)=2$ and $\alpha(G)=1.$ Interestingly, in case $G$ is bipartite, it actually becomes an equality. We will present several approaches for proving this claim. The shortest one (I believe) is via Dilworth’s theorem. Another approach, I came up with, uses Hall’s marriage theorem and the third one – Max-flow min-cut theorem. So, you see, it’s interesting to see three different and basics results that are applicable to the same problem.
A possible Olympiad wordning of this claim follows.

Problem 1. There are two countries with certain number of airports in each. There are air lines between some pairs of the airports belonging to different countries. Every airport is an endpoint of an air line. A company $A$ wants to buy some of the air lines so that it operates at every airport. (We say that $A$ operates at an airport if there is an air line that $A$ owns with an endpoint at that airport) A company $B$ wants to buy some airports provided there are no two of them connected by an air line.
Prove that the minimum number of air lines $A$ can buy to achieve its goal equals the maximum number of airports $B$ could buy.

Translated into graph theory language it reads:

Claim. For any bipartite graph $G$ without isolated vertices we have

$\alpha(G)=\rho(G)\qquad (1)$

Let $E_1$ and $V_1$ be correspondingly a vertex cover and an independent set with $|E_1|=\rho(G)$ and $|V_1|=\alpha(G).$ For each vertex $v$ in $V_1$ choose a edge $e$ that is incident to (covers) $v.$ This is a mapping $V_1\to E_1.$ Suppose $v_1,v_2\in V_1$ are mapped to one and the same $e\in E_1.$ It means $e$ connects $v_1$ and $v_2$ but this is impossible since $V_1$ is independent set and no two vertices in $V_1$ are connected. Thus, we have an injection $V_1\to E_1$ therefore

$\alpha (G)\le \rho(G)\qquad (2)$

This is true for any graph without isolated vertices, we didn’t use that $G$ is bipartite.

A proof using Dilworth theorem.

Let $G(A,B)$ be the corresponding bipartite graph with $A,B$ being the two parts of its vertices. We define an order on $V=A\cup B$ . For any $v_1, v_2\in V$ it holds $v_1\preceq v_2$ if $v_1\in A, v_2\in B$ or if $v_1=v_2.$ It is straightforward to check $(V,\preceq)$ is a partial order. By Dilworth’s theorem the sizes of the largest antichain and the smallest chain decomposition are equal. It remains to see that any antichain in $(V,\preceq)$ is just an independent set in $G$ and any chain decomposition is a vertex cover in $G.$ Indeed, in the defined poset there are no chains with more than two elements. So, any chain is either a single vertex or a pair $v_1\prec v_2$ which can be viewed as the edge $v_1v_2.$ In the former case, since there are no isolated vertices, we can add to $v_1$ any vertex it is connected with and by doing so we obtain a edge cover of $V.$ On the other hand any vertex cover can be transformed to a chain decomposition in $(V,\preceq)$ thus these two notions are equivalent.

A proof using Hall’s marriage condition.

I will proceed with this approach in the next blog post, but let me give a concise outline. Let $V_1$ be an independent set with $|V_1|=\alpha(G)$ and $V_1=A_1\cup B_1$ where $A_1\subset A, B_1\subset B.$ If we prove that there exists an edge cover $E_1$ with $|E_1|=|V_1|$ it would follow that $\alpha(G)\ge \rho(G)$ and taking into account $(2)$ we conclude that $(1)$ holds.
The key idea is that there is a matching of $A\setminus A_1$ to $B_1$ and $B\setminus B_1$ to $A_1.$

To the next part >>

A Kind of Friendship Paradox.

I saw this problem in a chapter on some combinatorial techniques that a friend of mine has recently released (see [1], 1.8, problem 5). I don’t think the statement is paradoxical, the title was chosen for other reasons. Loosely speaking, the problem states that on a social network, the celebrities cannot be more than other users – the exact statement follows. As it turned out, it was posted in MathOverflow and one of the solutions there was by Terence Tao [2]. He also made a reference to a phenomenon, observed by sociologists, called friendship paradox. It states that most people have fewer friends than their friends have on average [3]. That was the reason for the title. I want to believe that Prof. Tao was just kidding, suggesting how to make the text more gender-neutral (more comments in the last section at the end). The problem is also tightly related to another one, I have already commented on in this blog, and all this together made me create this post. First things first, here is the text.

Problem 1. In a finite, simple graph $G$ with vertex set $V$ , we say that a vertex $v$ is a king if $\deg(v) > \deg(w)$ for each neighbor $w$ of $v.$ Let $\mathrm{Kings}(G)$ denote the set of all non-isolated kings of $G$ . Show that

$\displaystyle |\mathrm{Kings}\,(G)| <\frac{|V|}{2}.$

Give an example where one has $\displaystyle \lim_{|V|\to\infty} \frac{|\mathrm{Kings}\,(G)|}{|V|}=\frac{1}{2}$

The solution is based on the following lemma, which can be considered as a standalone problem. One may see a generalization of this lemma in a form given at Bundeswettbewerb Mathematik, 2020, II round.

Lemma. A bipartite graph without isolated vertices $G(A,B)$ is given with $|B|>|A|$ . Then there exist connected vertices $a\in A, b\in B$ such that $\deg(a)>\deg(b)$ .
Proof. Note that the word “connected”, which I intentionally bold, is the essential part of the statement that makes it non-trivial.

Let $|B|=n,|A|=m$ and $\big\{c_{ij}\big\}, i=1,2,\dots,m, j=1,2,\dots,n$ be a kind of adjacency matrix of $G.$ That is, we enumerate the vertices from $A$ as $a_1,a_2,\dots,a_m,$ the vertices from $B$ as $b_1,b_2,\dots,b_n$ and we set $c_{ij}=1$ if $a_i$ is connected with $b_j$ and $c_{ij}=0$ otherwise. We define another two matrices $a_{ij},b_{ij}, i=1,2,\dots,m, j=1,2,\dots,n$ as follows.

$\displaystyle a_{ij}:=\frac{c_{ij}}{\sum_{k=1}^m c_{kj} }$

$\displaystyle b_{ij}:=\frac{c_{ij}}{\sum_{k=1}^n c_{ik} }$

Clearly, $\sum a_{ij}=n, \sum b_{ij}=m$ , hence $\sum a_{ij}>\sum b_{ij}$ . It means there is a cell $(i,j)$ , with $a_{ij}>b_{ij}.$ By the definition of $a_{ij},b_{ij}$ it yields

$\displaystyle \sum_{k=1}^m c_{kj}< \sum_{k=1}^n c_{ik}$

which means $\deg(a_i)>\deg(b_j).$ $\blacksquare$

Back to the Problem 1. Let $B:= \mathrm{Kings}\,(G)$ and $A:=V\setminus \mathrm{Kings}\,(G) .$ Suppose for the sake of contradiction $|B|>|A|$ Note that any two kings cannot be connected with an edge, so there are not edges between any two vertices in $B.$ Let us consider the bipartite graph $G'(A,B)$ obtained by removing edges that connect vertices inside $A.$ By our Lemma, there exists $a\in A,b\in B$ with $\deg_{G'}(a)>\deg_{G'}(b).$ It means $\deg_G(a)>\deg_G (b),$ which is impossible, since $b$ is a king.

For the second part of the problem, it’s enough to consider a full bipartite graph $G(A,B)$ with $|A|=n-1, |B|=n.$ Then the set of kings is just $A$ since $\deg(a)=n,\forall a\in A$ and $\deg(b)=n-1,\forall b\in B.$

More comments.

The statement of the Lemma can be sharpened. It holds $\displaystyle \deg(a)\ge \frac{|B|}{|A|}\deg(b)$ for some connected vertices $a\in A, b\in B$ . As mentioned, this can be further generalized ([4]).
Another curious moment is the Terence Tao’s comment on the original MathOverflow thread ([2]). He wrote:

This bound can also be viewed as quantifying a variant of the “friendship paradox“. (Based on this connection, I propose “influencer” as a more modern and gender-neutral terminology alternative to “king”.)

I strongly believe that the highly respected mathematician was just joking about this modern “gender-neutral” hysteria. But, many others take it quite seriously. Can you imagine, for example, we have to change the names of some chess pieces. The king will be called “influencer”, but how to call the queen? Maybe a “birth giving influencer” ?! Or, all these good old tales about kings and princesses that are told to every child – they also need to be changed or simply cancelled!?

References.
[1] Illustrations from the standard toolbox.
[2] A MathOverflow thread.
[3] Friendship paradox.
[4] Bundeswettbewerb Mathematik, 2020, II round.
[5] A Korean NMO problem, AoPS thread.

Let’s count! Bulgarian NMO 1991.

The next problem involves some coloring. We have some set of objects colored in some set of colors. We are looking for a “good” configuration of objects, which means: (1) The objects in the configuration must comply with some geometric rule (rules); (2) All objects in the configuration must comply to some condition involving their colors, for example be of distinct colors.
The ideas used in problems like that may vary. One possible way is to choose a configuration that is almost good, for example that satisfy only (1). Then, if this configuration doesn’t comply with (2) we try to improve it by making some changes that decrease the number of “bad” instances, for example the pairs that are colored with one and the same color. Sometimes it works, but not in this particular problem. I’ll present another possible approach, but after the text of the statement. This problem interested me because I tried some ideas and failed and decided to look for the official solution because I thought there was some crafted idea involved. To my disappointment, it was a simple argument that I had already considered and rejected without any further calculation. But still, it’s an instructive idea. Let me first present the problem.

Problem (Bulgarian NMO, 1991, p2) Let $K$ be a cube with side length $n$ , where $n>2$ is an even integer. The cube $K$ is divided into $n^3$ unit cubes. Any set of $n^2$ unit cubes lying on a plane parallel to some face of $K$ is called a layer. All unit cubes are colored in $\frac{n^3}4$ colors, each of which is used for exactly $4$ unit cubes. Prove that we can always select $n$ unit cubes of distinct colors, no two of which lie on the same layer.

A more general idea is to view the cubes (cells) as vertices of a graph. Two vertices are connected if they belong to the same layer or if they are colored in the same color. So, we are looking for an independent set of $n$ vertices, i.e. no two of them connected. We know the maximum degree is something like $3n^2$ and the number of the vertices is $n^3.$ One could use Turan’s lemma that guarantees certain number of independent vertices, but unfortunately it yields something like $n/3$ which is not enough. Apparently, in this case the geometrical meaning of “layer” does matter.
Note that the problem does not hold for $n=2.$ Indeed, the statement fails for a $2\times 2\times 2$ cube, colored in two colors so that any two opposite cells are colored the same. This fact hints that the proof maybe involves some counting and an estimate that fails when $n=2$ but is true for larger values of $n.$

I’ll present the official solution. The idea is to count the possible configurations of $n$ unit cubes (cells) not two of which lie on the same layer. Then to estimate how many of them could be “bad”, i.e. that contain two cells of the same color. The crucial idea is that the number of possible pairs of cells colored in some fixed color does not depend on $n,$ in fact this number is exactly $\binom{4}{2}=6.$

Solution. Let $S$ be the family of all configurations of $n$ cells no two of them lying on the same layer. Let’s count how many elements $S$ has. We can choose the firs cell $c_1$ in $n^3$ ways. After removing all layers $c_1$ takes part in there remain $(n-1)^3$ cubes. So the next cell $c_2$ can be chosen in $(n-1)^3$ ways and so on. This way, every configuration in $S$ is counted $n!$ times, hence

$\displaystyle |S|=\frac{n^3\cdot (n-1)^3\cdots 2^3\cdot 1^3}{n!}=(n!)^2.$

Denote by $B$ the family of “bad” configurations of $n$ cells, no two of them in the same layer, in which there exists two identically colored cells. We can choose two cells of the same color by first choosing the color and then all possible pairs among the four cells colored in this color. Thus, we can choose two identically colored cells in $\displaystyle \frac{n^3}{4}\cdot \binom{4}{2}=3\frac{n^3}{2}$ ways. The remaining $n-2$ cells, no two of them in the same layer, can be chosen in $\big((n-2)!\big)^2$ ways. Therefore

$\displaystyle |B|\le 3\frac{n^3}{2} \big((n-2)!\big)^2 .$

Note that this inequality may be strict. For example it may happen a bad configuration consists of two pairs of identically colored cells. Then we count this configuration twice.
Further, it’s enough to show $|B|<|S|$ because then $S\setminus B$ could not be empty. Thus, it’s enough to prove that for $n\ge 4$ it holds

$\displaystyle 3\frac{n^3}{2} \big((n-2)!\big)^2 < (n!)^2.$

It is equivalent to $\displaystyle 3\frac{n}{2} < (n-1)^2$ and it can be easily checked that it holds for $n\ge 4.$

Further Generalization.

The same idea of the presented proof could be applied to the following more general construction.

Problem 2. Let $K$ be a cube with side length $n\in \mathbb{N}.$ The cube $K$ is divided into $n^3$ unit cubes. Any set of $n^2$ unit cubes lying on a plane parallel to some face of $K$ is called a layer. All unit cubes are colored in colors, each of which is used for exactly no more than $c$ unit cubes, where $c$ is given positive integer. Prove that for sufficiently large $n$ we can always select $n$ unit cubes of distinct colors, no two of which lie on the same layer.

Again, let $S$ be the family of all configurations of $n$ cells, no two of them in the same layer. As above, we have $|S|=(n!)^2.$ Denote by $B$ the “bad” configurations among $S$ – the ones that contain two cells of the same color. The possible pairs of cells colored in some fixed color are at most $c(c-1)/2.$ The number of colors obviously are no more than $n^3.$ It yields

$\displaystyle |B|\le \frac{c(c-1)}{2}n^3\big((n-2)!\big)^2.$

It remains to check

$\displaystyle (n!)^2> \frac{c(c-1)}{2}n^3\big((n-2)!\big)^2$

holds when $n$ is sufficiently large, which is pretty clear.

Bulgarian TST 2015. A Geometric Problem.

An interesting geometric problem, which I saw recently, was proposed on a Bulgarian team selection test. As the Bulgarian TST’s problems are not released officially, there are only two ways to see one of them – either by leaking in some way in forum websites like AoPS, or in books dedicated to Bulgarian competitions. In this particular case I saw it in a book [1] that а friend of mine, Emil Stoyanov, was so kind to send me. He is also the author of this problem and I was curious to try it. The method used is different from all presented in the AoPS thread [2] and in the mentioned book. I hope you would enjoy it!

Problem 1 (Bulgarian TST for IMO 2015, p5) A quadrilateral $ABCD$ is given with $AD \nparallel BC$ . Denote by $M$ and $N$ the midpoints of $AD$ and $BC$ correspondingly. The line $MN$ intersects the diagonals $AC$ and $BD$ in the points $K$ and $L$ , respectively. Prove that the circumcircles of $\triangle AKM$ and $\triangle BNL$ have common point on the line $AB$ .
Author: Emil Stoyanov.

Solution. Assume the circumcircle of $\triangle AKM$ intersects $AB$ at a point $X'.$ Then $\angle BAK=\angle X'MN$ (the red angles on figure 1). A similar fact is true if we take the intersection of $AB$ and the circumcircle of $\triangle BLN,$ denote it by $X'',$ then $\angle ABL=X''NL$ (the blue angles). Taking this into account, it is enough to prove a slight different version of this problem.

Problem 1′. With the notations of problem 1, let $X$ be the point that satisfies $\angle XMN=\angle BAK$ and $\angle MNX=\angle ABL$ and $X$ is in the same half-plane, determined by the line $MN,$ in which are also the points $A$ and $B.$ Prove that $X$ lies on $AB.$

Proof. We fix the points $A,B,D$ and begin to move the point $C',$ that initially coincides with $C,$ along the ray $AC.$ Then $N'$ , as a midpoint of $BC'$ moves along the line through the initial point $N$ and parallel to $AC.$ This line meets the segment $AB$ at its midpoint $Q.$
Note that $\displaystyle k:=\frac{MX'}{MN'}$ is constant, because the angles $\alpha, \beta$ are fixed. The point $X'$ is obtained from the point $N'$ by rotating $N'$ around the point $M$ (which is fixed) at an angle $\alpha$ and then by homothety with ratio $k.$ This means that $X'$ moves along a line that is parallel to $AB$ because it is obtained by rotating the line $QN$ at $\alpha$ and then by homothety. So, to prove that $X'\in AB$ it suffices to point out only one particular case for which $X'\in AB.$
Now, let’s see what happens when $N'\equiv Q.$ Since $\angle MQA=\beta,$ it follows that $N'X'$ lies on $AB,$ and in this particular case indeed $X'\in AB.$ Therefore, $X'\in AB$ for all $C'\in AC$ and the result follows.

References.
[1] Bulgarian Mathematical Competitions 2012-2015, P. Boyvalenkov, E.Kolev, O.Mushkarov, N. Nikolov, 2015. (in Bulgarian)
[2] The thread in AoPS.

Kangaroos Jumping on a Chessboard. Italian Training Camp.

I saw this problem four months ago. It was in a handout used to train the Italian IMO team in 2015. The problems there were structured in the same way as the IMO shortlists. This one was numbered as C4. After several unsuccessful attempts, I gave up and decided to post it on the AoPS forum [1]. No one solved it for the next 4 months. I don’t think the problem is that difficult, the reason is that it probably wasn’t of much interest to many. The main point was to prove we couldn’t do the job with less than $2n/3$ kangaroos (the statement is below). An example showing this number is enough is easy to find.
When a fake solution came up recently, it gave me a new impetus to reconsider my previous ideas, and this time the right approach appeared.
After this blog-post was released, a guy pointed out (see the comments section. Thanks!) that the same problem had appeared at a Turkey TST 2014 [2]. The solutions presented on AoPS thread are all flawed. So, maybe this problem is not easy after all.

Problem (C4, Italian training camp, 2015). There are several kangaroos disposed in the northwest and southwest corners of a $2015 \times 2015$ chessboard. Those placed in the northwest corner are of the SE type and can jump either on the adjacent south square or on the adjacent east square. Those in the southwest corner are of type NE and can jump to the next north or east squares. What is the minimum number of kangaroos needed to visit each square of the table?

Solution. Let us put $n$ instead of $2015.$ We will prove the minimum number is $\displaystyle \left\lceil \frac{2n}{3}\right\rceil.$ An example that this number is enough is sketched in the figure below for $n=9.$ The red dots represent the six kangaroos, enough to cover all cells of the board.

It remains to estimate a lower bound for this number. Suppose we have $a$ kangaroos of type SE and $b$ ones – NE that are enough to cover all squares of the chessboard. We will make an interpretation of the statement that allows us better visualization of what happens. Consider only the first column of the chessboard, where the kangaroos are initially disposed. Instead of dealing with the trajectories/routes of kangaroos, we just frame them on the first column. There are $n$ rounds. At each round a kangaroo either stays still or moves some squares up or down, depending of its type – NE or SE. The condition is that at each round the empty squares must be traversed. It is clear that we can start with $a$ kangaroos disposed at the top $a$ cells in the column, each on in a separate square, and $b$ ones at the bottom part of the column, in $b$ adjacent cells. The uppermost kangaroos move only downwards, the lower ones – only upwards. Kangaroos of the same type cannot be placed in the same cell, but this is allowed for those of different types. Each round consists of moves that traverse all the empty cells. We make $n$ rounds, just as many as the columns on the chessboard. So, if you want to see the trajectories of the kangaroos, you just arange vertically the positions on each column that corresponds to each round, one after another, left to right. If at the final ( $n$ -th) round there are kangaroos that still can jump – up or down – we make them move. So, finally, the kangaroos that were initially at the bottom are at the top of the column and vise versa.
It means each of the lower kangaroos (NE ones) steps exactly in $n-a$ squares and each of the SE ones steps exactly in $n-b$ cells. In each round there are $n-a-b$ empty squares that need to be stepped in (for some of them it may be done twice or more). There are also $ab$ moves when a NE kangaroo jumps over a SE one, or vise versa. Therefore

$\displaystyle a(n-a)+b(n-b)\ge n(n-a-b)+ab$

This inequality yields

$\displaystyle 2n(a+b)\ge n^2+a^2+b^2+ab=n^2+(a+b)^2-ab$

Using the well known inequality $ab\le (a+b)^2/4$ we get

$\displaystyle \frac{3}{4}(a+b)^2-2n(a+b)+n^2\le 0.$

Considering it as a quadratic inequality with respect to $a+b$ yields

$a+b\ge 2n/3.$

References.
[1] The thread on AoPS website
[2] Turkey TST 2014, day 3, p3

A Balanced set of points. Bulgarian NMO, 2021.

This post views yet another problem from the Bulgarian national Olympiad this year. It could be classified as combinatorial geometry. It’s about a set in the plane closed under certain kind of averaging operation. A nice problem, I am tuned to problems like that and will present two solutions here – the first one is the official one. Judging by the scores of the contestants it appeared to be the second hardest problem in this competition after the functional equation (problem 3, Bulgarian NMO,2021). Many of the students didn’t find the right idea. This would not have happen if they had encountered the following construction.

Warm-up. A set $A$ of $n$ real numbers is given. What is the minimum number of elements of the set $A+A:=\{x+y : x,y\in A\}$ ?

The idea is to point out as many distinct elements of $A+A$ as possible. We arrange $A$ in increasing order $a_1<a_2<\dots<a_n$ and consider the following sums

$a_1+a_1<a_1+a_2<a_1+a_3<\dots<a_1+a_n$

$a_1+a_n<a_2+a_n<a_3+a_n<\dots<a_n+a_n$

In this way, we constructed $2n-1$ distinct elements of $A+A$ arranged in increasing order. Therefore $|A+A|\ge 2n-1.$ It can be seen that in case $A$ is an arithmetic progression these are the only distinct elements of $A+A,$ that is, $|A+A|=2n-1.$ Pay attention how we have constructed $2n-1$ distinct elements of $A+A.$ $\blacksquare$

Problem 5 (of Bulgarian NMO, 2021). Does there exist a set $S$ of $100$ points in a plane such that the center of mass of any $10$ points in $S$ is also a point in $S$ ?
Proposed by Pavel Kozhevnikov.

First solution (the official one). Such set of points does not exist. Suppose on the contrary the points $P_1,P_2,\dots, P_{100}$ satisfy the requirement. Let $Oxy$ be any coordinate system on the plane and $P_i$ has coordinates $(x_i,y_i), i=1,2,\dots,100.$ Then the center of gravity $(x_G,y_G)$ of any points $P_{i_1},P_{i_2},\dots,P_{i_{10}}$ is determined as

$x_{G}=(x_{i_1}+x_{i_2}+\dots+x_{i_{10}})/10\,,\,y_G= (y_{i_1}+y_{i_2}+\dots+y_{i_{10}})/10$

The construction of the warm-up now comes into use. Assume just for a moment all $x_1,x_2,\dots,x_{100}$ are distict and are ordered as $x_1<x_2<\dots<x_{100}.$ Then, the sums of the $x$ coordinates of the following sets of $10$ points are strictly increasing:

$\{P_1,P_2,\dots,P_9,P_{10}\}, \{P_1,P_2,\dots, P_9,P_{11}\}, \dots, \{P_1,P_2,\dots, P_9,P_{100}\}$

$\{P_1,P_2,\dots,P_8,P_9,P_{100}\}, \{P_1,P_2,\dots, P_8,P_{10},P_{100}\}, \dots, \{P_1,P_2,\dots, P_8,P_{99},P_{100}\}$

They are altogether $181$ sets, and the center of mass of each of them has distinct $x$ coordinate. Therefore, we have at least $181$ distinct centers of mass, which is contradiction since these points should be among $P_1,P_2,\dots,P_{100}.$
There remains only one issue. Some of $x_1,x_2,\dots,x_{100}$ may coincide. But we have freedom to choose the coordinate system $Oxy$ and we can always choose it so that all $x$ coordinates of the points $P_1,P_2,\dots,P_{100}$ be distinct.

Second solution. Again, arguing by contradiction, assume $V:={v_i: i=1,2,\dots,100}$ is the corresponding set of distinct vectors and let $m:=\min{|v_i-v_j|: i\neq j}$ . Clearly $m>0$ . Suppose $m=|v_k-v_{\ell}|, k\neq \ell$ . Let $V_0\subset V$ be a set of $9$ vectors not equal to $v_k$ and $v_{\ell}$ . Then $\displaystyle v_i:=\frac{1}{10}\left(\sum_{v\in V_0}v+v_{k}\right)\in V$ and $\displaystyle v_j:=\frac{1}{10}\left(\sum_{v\in V_0}v+v_{\ell}\right)\in V$ and $v_i\neq v_j.$ We have

$\displaystyle |v_i-v_j|=\frac{|v_k-v_{\ell}|}{10}=\frac{m}{10}$

contradiction.

References.
Problem 3, Bulgarian NMO,2021
Problem 4, Bulgarian NMO,2021
Bulgarian NMO,2021, AoPS page

Interlaced Progressions. Bulgarian NMO,2021.

In the previous post we considered a functional equation given in the Bulgarian National Mathematical Olympiad, 2021. The next problem from the same contest was proposed by Aleksandar Ivanov. I commented on another of his problems given on the same competition last year (Bulgarian NMO, 2020, p6). The current one was the first problem of the second day and has a number theory taste. I misunderstood it upon reading it for the first time. I thought we were dealing with arbitrary sequences with some given property. So, I was a bit disappointed when got the correct statement, because the knowledge that a sequence is an arithmetic progression is very powerful information – there are only two parameters that determine it. However, the problem turned out to be pleasant, though not difficult. Here it is.

Problem 4 (of Bulgarian NMO,2021). Two infinite arithmetic progressions with positive integers are given:

$\displaystyle a_1<a_2<a_3<\cdots \,\,;\,\, b_1<b_2<b_3<\cdots$

It is known that there are infinitely many pairs of positive integers $(n,j)$ for which $n\leq j\leq n+2021$ and $a_n$ divides $b_j.$ Prove that for every positive integer $n$ there exists a positive integer $j$ such that $a_n$ divides $b_j.$
Proposed by Aleksandar Ivanov.

We know both sequences are arithmetic progression, so let $a_n=d_1n+a_0, b_n=d_2n+b_0, n\in \mathbb{N}$ where $d_1,d_2\in N, a_0,b_0\in \mathbb{Z}.$ The idea is simple. Since $b_{n+i}$ is not far away from $b_n$ when $i$ is small ( $0\le i\le 2021$ ) then $b_{n+i}/a_n$ is something around $d_2/d_1.$ That said, it’s quite possible the only option $b_{n+i}/a_n$ be an integer is when it is very close to the integer part of $d_2/d_1.$ Let us denote

$\displaystyle r:=\left\lfloor\frac{d_2}{d_1} \right\rfloor, \varepsilon := \frac{d_2}{d_1}-r.$

Clearly, $r\in \mathbb{N}, 0\le \varepsilon<1.$ We have

$\displaystyle ra_n=\left(\frac{d_2}{d_1}-\varepsilon\right)\left(d_1n+a_0\right)=d_2n+\frac{d_2}{d_1}a_0-\varepsilon(d_1n+a_0)=$

$\displaystyle = b_n -b_0+ \frac{d_2}{d_1}a_0-\varepsilon(d_1n+a_0)\qquad (1)$

In the same way we get

$\displaystyle (r+1)a_n=\left(\frac{d_2}{d_1}+(1-\varepsilon)\right) \left(d_1n+a_0\right) =$

$\displaystyle =b_n -b_0+ \frac{d_2}{d_1}a_0+(1-\varepsilon)(d_1n+a_0)\qquad (2)$

It was all we need for the final cut. Suppose $\varepsilon \ne 0.$ Then according to $(1)$ it follows

$ra_n<b_n \qquad (3)$

for sufficently large $n.$ According to $(2),$

$(r+1)a_n-b_{n+2021}=b_n-b_{n+2021}-b_0 +\frac{d_2}{d_1}a_0+(1-\varepsilon)(d_1n+a_0)$

Note that $b_n-b_{n+2021}$ is a constant not depending on $n,$ hence for sufficiently large $n$ we get $(r+1)a_n-b_{n+2021} >0,$ that is

$(r+1)a_n>b_{n+2021}\qquad (4)$

holds for sufficienly large $n.$
Now, both $(3)$ and $(4)$ imply that for large $n$ there is no way $b_{n+i}, i=0,1,\dots,2021$ to be multiple of $a_n$ which contradicts the initial condition. Therefore, $\varepsilon=0,$ that is, $\boxed{d_2=rd_1}.$ Let us put $\varepsilon =0$ back into $(1)$ . It yields

$ra_n=b_n-b_0+ra_0\qquad (1')$

Since $(4)$ still holds for sufficiently large $n,$ the only possibility $b_{n+i}$ to be multiple of $a_n$ for some $0\le i\le 2021$ is the right hand side of $(1')$ be equal to $b_{n+i}$ for some sufficiently large $n$ and some $i, 0\le i\le 2021$ ( $i$ may depend on $n$ ). This yields $ra_0-b_0=id_2,$ therefore $i$ does not depend on $n$ and

$ra_n=b_n+d_2i=b_{n+i}\qquad (1'')$

is satisfied for infinitely many $n$ . It just means $(1'')$ holds for every $n\in\mathbb{N}$ and the result follows.

References.
Bulgarian NMO, p.4, A thread in AoPS.

A Functional Equation for the Win. Bulgarian NMO, 2021.

This year the finals of the Bulgarian National Mathematical Olympiad were on time – on May 15 and 16. Most of the Covid-19 restrictions here in Bulgaria have been already dropped, so it was time for math. Six problems were given. Two of them were purely geometric, one combinatorial geometry, one combinatorics, one number theory and one functional equation. I think they were comparatively easy, except maybe for problem 3. A total of 6 students had a perfect score of 42 points. Judging by the scores obtained for each of the problems, the functional equation (problem 3) was the most difficult one. It was proposed by Nikolai Nikolov, however, actually it was given about 9 months ago in another competition and was posted on the AoPS website [1]. So, this is not a good practice, but what has been done has been done. By the way, at least 3 solutions out of 4 attempts are fake in the thread in AoPS (see [1]). They miss the most essential part of the idea. Anyway, this problem is nice. Unlike most of the functional equations, it has an idea and needs careful consideration.
I will try to comment on at least four of the problems in this competition and I decided to start with the most difficult one – this functional equation for the win.

Problem 3 (of Bulgarian NMO, 2021). Find all $f:R^+ \rightarrow R^+$ such that

$f(x) f(y+f(x) ) = f(xy + 1)\,, \ \forall x, y \in R^+\qquad (1)$

Proposed by Nikolai Nikolov.

Solution. The full solution is based on several observations. Let $x$ and $y$ vary, complying with $x=xy+1.$ Since $f$ cannot vanish, putting it in $(1)$ we get $f(y+f(x))=1.$ The restriction $x=xy+1$ yields $y=(x-1)/x, x>1,$ thus we get

Observation 1. $\displaystyle f\left( 1-\frac{1}{x}+f(x)\right)=1, \forall x>1$

Playing a bit with $(1)$ leads us to a strong suspicion that $f(1)=1.$ Then the observation 1 most probably implies that either $1-\frac{1}{x}+f(x)=1, \forall x>0$ or $f(x)=1,\forall x>0.$ Indeed $f(x)=1/x$ and $f(x)=1$ both satisfy $(1).$ So, it’s reasonable to believe no other solutions exist.
Let now vary $x$ and $y$ such that they comply with

$y+f(x)=xy+1\qquad (2)$

which is equivalent to $f(x)-1=y(x-1).$ It means if there exists $x>1$ with $f(x)>1$ then the restriction $(2)$ is satisfied for $y:=(f(x)-1)/(x-1)>0$ and putting it into $(1)$ we would get $f(x)=1$ which contradicts the assumption $f(x)>1.$ The same argument shows that there does not exist $0<x<1$ with $f(x)<1.$ Thus, we get the following

Observation 2. It holds $f(x)\le 1, \forall x>1$ and $f(x)\ge 1,\forall x<1.$

Suppose we have $f(x_0)=1$ for some $x_0>0.$ Observation 1 shows there exists at least one such $x_0.$ Putting it into $(1)$ we get $f(y+1)=f(x_0y+1).$ Thus, we have done the following

Obervation 3. For any $x_0$ satisfying $f(x_0)=1$ we have $f(y+1)=f(x_0y+1),\forall y>0.$

Taking into account Observation 2, suppose $f(x^*)<1$ for some $x^*>1.$ Let $c:=f(x^*)<1.$ Putting $x^*$ into $(1)$ we arrive at the following

Observation 4. Let $x^*>1$ and $f(x^*)<1.$ Denote $c:=f(x^*)$ . Then $f(y+c)>f(x^*y+1),\forall y>0.$

Now we are ready to prove two crucial final observations. They show that if $f(x)=1$ for some $x\neq 1$ then the only possibility is $f(x)\equiv 1.$ If so, then Observation 1 will unravel the problem.

Observation 5. If there exists $x_0>1$ with $f(x_0)=1$ then $f(x)=1,\forall x>1.$
Proof. Suppose, for the sake of contradiction, this is not true. It means, there exists $x^*>1$ with $f(x^*)<1$ (according to the Observation 2). By Observation 4, it yields

$\displaystyle f(y+c)>f(x^*y+1),\forall y>0 \qquad (3)$

where $c:=f(x^*)<1.$ Further, Observation 3 gives us

$\displaystyle f(y+1)=f(x_0y+1), \forall y>0\qquad (4)$

The idea is to choose appropriate values of $y$ such that $(3)$ and $(4)$ would be inconsistent. That is, we search for $y_1,y_2>0$ such that $y_1+c=y_2+1$ and $x^*y_1+1=x_0y_2+1.$ If such values $y_1,y_2>0$ do exist then plugging them respectively into $(3)$ and $(4)$ we would get contradiction.
It remains to see when the corresponding system of equations has a solution with $y_1>0, y_2>0.$ Ok, from $y_1=y_2+1-c$ we obtain $(x_0-x^*)y_2=x^*(1-c)$ (note that $0<c<1$ ). It means, if $x_0>x^*$ then we are done, we get contradiction which proves the Observation 5. Fortunately, there exists as larger $x_0$ as we want with $f(x_0)=1.$ Indeed, putting $y:=x_0-1$ into Observation 3, we consecutively get that every member of the sequence $x_{n}=x_{n-1}(x_{n-1}-1)+1, n=1,2,\dots$ satisfies $f(x_n)=1.$ It can be seen easily that $\{x_n\}$ is strictly increasing and $\displaystyle \lim_{n\to\infty}x_n=\infty.$ The current observation is proved. $\blacksquare$

Observation 6. If there exists $x_0, 0<x_0<1$ with $f(x_0)=1$ then $f(x)=1,\forall x, 0<x<1.$
Proof. The proof follows the same idea as in the previous observation. For the sake of contradiction, assume there exists $x^*, 0<x^*<1$ with $c:=f(x^*)>1$ (taking into account Observation 2). Putting $(x^*,y)$ into $(1)$ we obtain

$\displaystyle f(y+c)<f(x^*y+1),\forall y>0\qquad (5)$

As above, Observation 3 implies

$\displaystyle f(y+1)=f(x_0y+1),\forall y>0\qquad (6)$

Again, we want to find $y_1,y_2>0$ satisfying $y_1+c=y_2+1$ and $x^*y_1+1=x_0y_2+1.$ If so, then $(5)$ and $(6)$ would contradict each other. We eliminate $y_2$ as $y_2=y_1+c-1$ and it yields $(x^*-x_0)y_1=x_0(c-1).$ This equality always has a positive solution with respect to $y_1$ when $x^*>x_0.$ It just means that if there exists $x^*\in (x_0,1)$ with $f(x^*)>1$ it immediately brings us to contradiction. Therefore, $f(x)=1,\forall x\in (x_0,1).$ By Observation 3, we get

$\displaystyle f(y+1)=f(xy+1),\forall y>0, \forall x\in (x_0,1)$

From this it can easily be concluded that $f(x)=\mathrm{const}$ when $x>1$ and this constant must be $1.$ By $f(x)=1,\forall x>1,$ according to $(1)$ we get $f(x)=1,\forall x, 0<x<1.$ $\blacksquare$

Now, assume there exists $x>0, x\neq 1$ with $f(x)=1.$ By the last two observations, it follows that $f(x)\equiv 1$ on the corresponding frame ( $x<1$ or $x>1$ ). Using $(1)$ it follows $f(x)=1,\forall x>0.$ Let us consider the case when $f(x)\neq 1, \forall x>0, x\neq 1.$ Since the function $f$ takes the value $1$ (by Observation 1) we obtain that $f(x)=1$ only when $x=1.$ Applying Observation 1 again, we get $\displaystyle f(x)=\frac{1}{x},\forall x>1.$ Plugging any $x, 0<x\le 1$ and $y=1$ back into $(1)$ yields $\displaystyle f(x)=\frac{1}{x},\forall x>0.$