Dragomir Grozev

King Midas vs Medusa. Indonesia LuMaT 2019, Final.

An interesting piece, I came across browsing some combinatorial problems. The plot is connected with Greek mythology. Medusa was a monstrous creature, a winged human female with living venomous snakes in place of hair. Those who gazed into her eyes would turn to stone. King Midas ruled Phrygia, a Greek city. He had ability to turn everything he touched into gold. So, you see, it’s interesting to imagine what would happen if we place them both into the ring, one vs another! Here is the story.

Problem 8, 2nd day. King Midas and Medusa alternatively play on an infinite chessboard. Initially, all of the cells of the chessboard are made of stones. In each of his turn, Midas chooses three squares which are in the same column or row, and turns them into gold. In each of Medusa’s turn, she can choose any $2 \times 2$ grid square and turns its 4 cells into stone. King Midas wins if he can make a $2019 \times 2019$ grid square entirely of gold. Medusa wins if she can always prevent Midas doing so. Who wins?

Some observations and motivation.

I admit, at first I had read the problem very sloppy, and it seemed as if there was a $2019\times 2019$ grid board on which the action took place. So, it seemed a very easy problem then, since Midas cannot win, no matter of Medusa’s moves. Indeed, suppose Midas makes all cells of the table golden with his last move. But, in her previous move Medusa had stoned some $2\times 2$ square, and the king cannot make all of its 4 cells gold just in one move. I even looked up after the name of the competition wondering was it a kindergarten one! Anyway, this observation is helpful. It shows king Midas cannot choose some big square and make it golden. Medusa always wins in some local area. If it’s possible Midas to win, he must place multiple threats of making gold squares on many well apart areas. He should use his advantage of placing threats on 3 well apart areas at a time, while Medusa could eliminate only 2 of them.

The strategy of King Midas.

We prove King Midas always can make a $2019\times 2019$ gold square. Moreover, Midas, in a good mood can allow Medusa to stone any 4 cells, that are intersection of 2 rows and 2 columns.

Let $M$ be a large enough positive integer which will be determined later. The king chooses an infinite family $\mathcal Q$ of disjoint $2019\times 2019$ squares lined up in a row. In every move he turns into gold the upper-left cells of 3 different empty squares in $\mathcal Q$ . After $M$ turns, he marks the upper-left corner of $3M$ sets in $\mathcal Q$ and Medusa can erase at most $2M$ of them, since she can operate over no more than 2 sets in $\mathcal Q$ at a time. Once Medusa operates over a square in $\mathcal Q$ , Midas considers it as unusable and does not take any action on its cells.

Thus, after the first phase, we get $M$ squares in $\mathcal Q$ with golden upper-left cell. We denote the family of those $2019\times 2019$ squares as $\mathcal {Q}_1.$ Further, Midas aims at $M$ cells, each one in distinct set in $\mathcal{Q}_1$ , disposed at the same positions inside the big squares, and begins turning them into gold, 3 at a time. He manages to do it in $M/3$ moves, while Medusa can damage at most $2M/3$ sets in $\mathcal{Q}_1$ . At this moment we have $M-2M/3=M/3$ sets of $\mathcal{Q}_1$ with two goldean cells each, disposed at the same positions. Denote that subfamily of $\mathcal{Q}_1$ as $\mathcal{Q}_2.$

Midas proceeds in the same spirit obtaining each next phase a family $\mathcal{Q}_n$ of ${M}/{3^{n-1}}$ sets with $n$ golden squares each, disposed at the same positions. For $n=2019\cdot 2019$ there will be at fully golden $2019\times 2019$ square, providing we have chosen $M\ge 3^{2019\cdot 2019 -1}$ .

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

Multiple of Power of 2. Bulgarian TST, 2020, p2.

I’ve recently reviewed, in some previous posts, 3 of the problems given at the last Bulgarian team selection tests. Here is another problem. It’s pure NT and a good one in my humble opinion.

Problem 2 (Bulgarian TST, 2020, 1st day). Given two odd natural numbers $a,b$ prove that for each $n\in\mathbb{N}$ there exists $m\in\mathbb{N}$ such that either $a^mb^2-1$ or $b^ma^2-1$ is multiple of $2^n.$

Let us fix $n\in \mathbb{N}$ and consider the multiplicative group $G$ of odd residues modulo $2^n$ , i.e. $G=\left( \mathbb{Z}/2^n\mathbb{Z}\right)^{\times}.$ Clearly $|G|=\varphi(2^n)=2^{n-1}.$ It’s known $G$ is cyclic for $n=1,n=2$ and $G\cong C_2\times C_{2^{n-2}}$ for $n\geq 3$ , where $C_k$ denotes the cyclic group of order $k$ . Hereafter, we assume $n\ge 3.$ The small cases of $n$ are similar and easier. Consider the following cyclic subgroups of $G$ (we identify $a,b$ as elements of $G$ ).

$A:=\{a^j : j=0,1,\dots\}\,;\, B:=\{b^j : j=0,1,\dots\}$

Let $|A|=k, |B|=\ell$ and assume $k\leq \ell$ . In fact, $k\mid \ell$ since both $k,\ell$ are powers of $2$ (because their orders divide $2^n$ ). Using $G\cong C_2\times C_{2^{n-2}}$ , we represent $a,b$ as $a=(e_1, a_1), b=(e_2, b_1), e_1,e_2\in\{-1,1\}, a_1^k=1,b_1^{\ell}=1$ . Note that $b_1^{\ell/k}$ and $a_1$ generate subgroups of the same order in $C_{2^{n-2}}.$ But any two subgroups of a cyclic group which have the same orders are equal, hence

$\displaystyle b_1^{r}=a_1.$

for some $r$ . Since $e_2^r=\pm e_1$ , we can conclude $b^{2r}=a^2.$ That’s, $a^2\in B$ and choosing $m$ such that $b^m=a^{-2}\in B$ , we have $b^ma^2=1$ .
In the case $k>\ell$ we get $b^2\in A$ and $a^mb^2=1$ for appropriate $m$ .

Hamel Bases II. Application on Olympiad Problems. Romanian TST 1994.

In a previous post I have considered an interesting problem, which has a surprising solution using Hamel bases. Here, a similar but harder problem is presented.

Problem 1. (Romanian TST for IMO 1994, 3rd test) Let $p$ be a prime number. Suppose that real numbers $a_1, a_2,\dots, a_{p+1}$ have the property that, whenever one of the numbers is deleted, the remaining numbers can be partitioned into two classes with the same arithmetic mean. Show that these numbers must be equal.

Note that the numbers $a_1, a_2,\dots, a_{p+1}$ are real, which somehow rules out using NT ideas. Still, we can try and prove the claim in case those numbers are integers. Further, it easily can be extended in case the numbers are rational. Finally, the method shown allows us to extend the proof from rationals to reals. It is done by representing each real number of the given set as a linear combination of some Hamel basis. This linear combinations have rational coefficients. The key moment. Our property is transferred over each “vector” of the basis and since the corresponding coordinates are rationals we can apply the claim to each coordinate axis and make the final conclusion.

A more general environment.

This method can be applied in the following, more general, circumstances. Suppose we must prove that some property $P$ about a set $A$ of reals implies another property $Q$ of the same set. Suppose both properties $P$ and $Q$ involve only linear expressions over elements of $A$ that should be satisfied. Then, there is pretty good chance the described method to do the job.
Let us proceed with the details in this particular case.

I – The integer case.

Suppose, we have $p$ integers with sum $s$ , which can be partitioned into two groups with the same average: one – containing $k$ of them with sum $s_1$ , the other – containing $\ell$ numbers with sum $s_2$ . Then $s_1/k=s_2/\ell$ implying

$s_1\ell=s_2k$

Note that $\gcd(\ell,k)=1$ since $k+\ell=p$ and $p$ is prime. It yields $\ell\mid s_2, k\mid s_1$ thus $s_1=rk, s_2=r\ell$ where $r$ is integer. Finally, $s=rp$ . This observation can be worded as:

if a set of integers could be partitioned into two subsets with the same arithmetic mean, then their sum must be multiple of $p$ .

Using this fact for a set $a_1, a_2,\dots, a_{p+1}$ of integers satisfying the initial conditions, it yields all $a_i,i=1,2,\dots,p+1$ should have the same residue modulo $p$ . Another two observations

Adding the same number to all $a_1, a_2,\dots, a_{p+1}$ leaves intact the initial property.
Dividing (multiplying) all $a_i,i=1,2,\dots,p+1$ by the same number, yields a resulting set that also satisfy the given property.

Starting from a set of numbers $a_1, a_2,\dots, a_{p+1}$ complying to the problem requirement, we can make them all positive by adding to all of them some positive integer. Then, we conclude they have the same residue modulo $p$ . Subtracting that residue from all of them and then dividing by $p$ doesn’t change the property. This process should come to an end and at the final stage, the only possibility is all the numbers be zeroes. It means all numbers at the beginning are equal.

II – The rational case.

Suppose now the numbers $a_1, a_2,\dots, a_{p+1}$ are rational. We can multiply them by a common multiple of their denominators and get integer numbers satisfying the same property. By the previous section they should be equal.

III – The real case.

Let $a_i\in\mathbb{R}, 1\le i\le p+1$ be real numbers. Take a Hamel basis $B=\{b_i, i\in I\}$ of $\mathbb{R}$ as a vector space over $\mathbb{Q}$ . Here, $I$ is an index set (which is uncountable). Thus

$\displaystyle a_j=\sum_{i\in I}\lambda_{i,j} b_{i}\,;\, j=1,2,\dots,p+1$

where for any fixed $j, 1\le j\le p+1$ only finitely many $\lambda_{i,j} \in \mathbb{Q}$ are non zeros when $i$ runs through $I.$ Since $B$ is a basis, the original property holds for any coordinate $i\in I$ , i.e. for any fixed $i\in I$ , the $p+1$ numbers $\lambda_{i,j};j=1\dots, p+1$ satisfy the given property and since they are all rationals, they are equal. Thus, $a_j,j=1,2,\dots,p+1$ are equal.

References.
https://artofproblemsolving.com/community/c6h1508562p8944063
https://artofproblemsolving.com/community/c6t169f6h2126535s1_balanced_numbers

Pinch of Linear Algebra. A Bulgarian NMO 1977 problem.

I came across this problem again, a month ago, curious to see the problems given back in those years. The first time I saw this problem was on that same competition it was given at. In 8th grade then, and I hardly remember did I succeed or not on, most probably not! But still remember the taste of the problem, and it was delicious! It is too classical now, but it wasn’t then. So, here it is.

Problem 5 (Bulgarian NMO 1977, final round). Let $Q(x)$ be a non-zero polynomial and $k$ be a natural number. Prove that the polynomial $P(x) = (x-1)^kQ(x)$ has at least $k+1$ non-zero coefficients.

I am going to present two solutions, based on the same idea. The first one is a more direct one but uses a little bit linear algebra. This is a solution, I came up with when had to solve it somehow. I don’t remember the official solution, but most probably it was induction on $k$ and it’s the second solution presented. I think it’s the shortest possible. I posted the problem in AoPS, see [2], and it was the solution given there.

So, we have a polynomial, $P(x)$ , we even don’t know its degree. The only thing we know is it’s multiple of $(x-1)^k$ and it has to have some property, some minimal number of non zero coefficients. The key idea is to ensure some other way of testing is $(x-1)^k$ a factor of $P(x)$ or not. Of course, it’s equivalent to $P^{(j)}(1)=0, j=0,1,\dots,k-1$ .

First solution, a pinch of linear algebra.

For the sake of contradiction, we assume $P(x)$ has at most $k$ non zero coefficients. Hence

$\displaystyle P(x)=a_{n_1}x^{n_1}+a_{n_2}x^{n_2}+\dots +a_{n_k}x^{n_k}$

assuming $n_1>n_2>\dots>n_k\ge 0$ . All derivatives of $P$ , up to $k-1$ -th must vanish at the point $x=1.$ Thus, we get $k$ conditions $P$ must comply to.

$\displaystyle 0=P(1)=a_{n_1}+a_{n_2}+\dots+a_{n_k}\quad \quad (1)$
$\displaystyle 0=P^{(j)}(1)=n_1(n_1-1)\cdots(n_1-j+1)a_{n_1}+n_2(n_2-2)\cdots(n_2-j+1)a_{n_2}+\dots+n_k(n_k-1)\cdots(n_k-j+1)a_{n_k}\,,\,j=1,2,\dots,k-1$

We may look at the above $k$ conditions as a homogeneous system of $k$ linear equations with $k$ unknowns $a_{n_1},a_{n_2},\dots,a_{n_k}$ . It has to have a non zero solution, since not all of the coefficients $a_{n_j}$ are zeroes. The general theory says: if we are looking for solutions of a system like $(1)$ , we have to look to the determinant, constructed by its coefficients ( $a_{n_j}$ are the unknowns). In this case this determinant is

$D=\displaystyle \begin{vmatrix}1 & 1 & \ldots & 1\\{n_1} & {n_2} & \ldots & {n_k}\\n_1(n_1-1)&n_2(n_2-1)&\ldots & n_k(n_k-1)\\\vdots &\vdots & \ddots &\vdots&\\n_1\cdots(n_1-k+1)&n_2\cdots(n_2-k+1)&\ldots&n_k\cdots(n_k-k+1)\end{vmatrix}$

In case $D\ne 0$ the only solution of $(1)$ is the zero vector. It remains to prove $D\ne 0$ in order to get contradiction with the fact not all $a_{n_j}$ are zeroes.

Applying several times the rule: “adding a row of $D$ multiplied by a scalar to another row of $D$ , then the determinant will not change” starting from the upper rows of $D$ and moving down, it can be obtained

$D=\displaystyle \begin{vmatrix}1 & 1 & \ldots & 1\\{n_1} & {n_2} & \ldots & {n_k}\\n_1^2&n_2^2&\ldots & n_k^2\\\vdots &\vdots & \ddots &\vdots&\\n_1^{k-1}&n_2^{k-1}&\ldots&n_k^{k-1}\end{vmatrix}$

But this is exactly the Vandermonde determinant and

$\displaystyle D=\prod_{1\le i<j\le k} (n_j-n_i)\neq 0$

Hence, contradiction and the result follows.

A more classical solution.

Induction on $k$ . The claim is obviously true for $k=0$ . Let it’s true up to some $k$ and take a polynomial $P(x):=(x-1)^{k+1}Q(x)$ where $Q(x)$ is not identically zero. Seeking contradiction, suppose $P$ has at most $k+1$ non zero coefficients. We may assume $Q(0)\ne 0$ since otherwise we cancel the appropriate power of $x$ reducing it to a polynomial with the same number of non zero coefficients. Now, consider the polynomial $P'(x)$ . It has at most $k$ non zero coefficients and it can be represented as

$P'(x)=(x-1)^k Q_1(x)$

where $Q_1(x)\not\equiv 0$ . By the induction hypothesis $P'(x)$ has to have at least $k+1$ non zero coefficients, contradiction.

References.
[1] https://imomath.com/othercomp/Bul/BulMO477.pdf
[2] https://artofproblemsolving.com/community/c6t169f6h2203732s1_nonzero_coefficients_of_a_polynomial

A Family of Sets. Bulgarian TST for IMO 2020, p3.

We have considered in some previous posts two interesting problems from the recent Bulgarian team selection tests (problem 4, problem 5). Here is a combinatorial problem from the first day, which in my opinion was the most fascinating one (maybe along with the problem 5, a kind of characterization of almost additive functions). That’s why I’m including it here. It gave me pleasure to unravel it.

Problem 3. Let $\mathcal{C}$ be a family of subsets of $A=\{1,2,\dots,100\}$ satisfying the following two conditions.

Every $99$ element subset of $A$ is in $\mathcal{C}.$
For any non empty subset $C\in\mathcal{C}$ there is $c\in C$ such that $C\setminus\{c\}\in \mathcal{C}.$

What is the least posible value of $|\mathcal{C}|$ ?

Solution.

We consider the family $\mathcal{C}'$ of the sets that are complement to those in $\mathcal{C}'$ , i.e.

$\mathcal{C}'=\{A\setminus C : C\in\mathcal{C}\}$

Consider a directed graph $G$ with vertices in $\mathcal{C}'$ . For any $C_1,C_2\in \mathcal{C}'$ , $C_1C_2$ is a directed edge iff $C_2$ can be obtained by removing an element from $C_1$ . This graph has one vertex, call it the root vertex, which has only out-edges, and it’s the set $A\in \mathcal{C}'$ ( $A$ is in $\mathcal{C}'$ because $\emptyset\in \mathcal{C}$ ). It also has exactly $100$ vertices with only in-edges – the sets with only 1 element: $\{a\}, a\in A.$ We call these vertices end vertices. Since there is a directed path from the root to any end vertex, we can construct a directed tree $T$ in $G$ that contains the root and all end vertices. We can assume there are no other leaves in $T$ except the end vertices, since otherwise we can remove them. Thus, we can associate such a tree $T$ to every family $\mathcal{C}$ with the required properties and $|T|\le |\mathcal{C}|$ . On the other hand, any directed tree with vertices among the subsets of $A$ that contains the root (the set $A$ ) and all end vertices (the sets $\{a\}, a\in A$ ), can be represented as a collection of subsets with complements satisfying the problem’s initial conditions. Hence, we look for such a tree with minimum number of vertices.

Now, put $n$ instead of $100$ and let $T$ be a tree, as described above. We replace any path of consecutive vertices with degree $2$ with only one edge, so we obtain a tree (again denoted by $T$ ) any vertex of which has degree at least $3$ , except the root and the leaves (end vertices). To each vertex $v$ we assign a value $L(v)$ equal to the number of leaves that can be reached starting from $v$ , assuming $L(v)=1$ if $v$ is itself a leaf. See an example below, for $n=7$ .

We define

$\displaystyle f(T):= \sum_{\overrightarrow{uv}\in E(T)} (L(u)-L(v))$

where the summation is taken over all directed edges $\overrightarrow{uv}.$ For example $f(T)=20$ for the tree in figure 1. It’s easy to see $f(T)+1$ is exactly the number of the sets in the family $T$ is derived from. On the other hand, for any such tree with $n$ leaves one can construct a family of $f(T)+1$ sets, complying to the initial requirements.

Hereby, the problem boils down to construct a directed tree $T$ with $n$ leaves for which $f(T)$ is minimal. Along these lines, denote

$\displaystyle f(n)=\min_{T \text{ is a tree with n vertices} }f(T), n\ge 2\quad \quad (1)$

Lemma. The minimal value of $f(T)$ is attained when $T$ is a balanced binary tree, by which we mean:

Each vertex which is not a leaf has exactly two out-edges, so $T$ is a binary tree.
If $u$ is vertex, which is not a leaf and $u_1,u_2$ are its adjacent upper vertices, i.e. $\overrightarrow{uu_1},\overrightarrow{uu_2}\in E(T)$ then $L(u_1),L(u_2)$ are equal or almost equal.

Proof. To prove 1) let in a minimal tree $T$ there exist 3 out-edges $uu_1, uu_2,uu_3$ . We erase edges $uu_2,uu_3$ and put another vertex $u'$ between $u$ and $u_2,u_3$ with edges $uu'$ and $u'u_2,u'u_3$ thus obtaining a new tree $T'$ for which $f(T')<f(T)$ , contradiction.
To prove 2) we proceed by induction. Suppose it’s proved for all trees with $m$ leaves $m<n$ . Let $T$ be a tree with $n$ leaves and a root $u_0$ and $u_0u_1, u_0u_2$ be its out-edges.
Assume at first both $u_1,u_2$ are not end vertices. By our induction hypothesis, we can assume the two trees with roots $u_1,u_2$ are balanced. Let $u_1u_1',u_1u_1''$ and $u_2u_2', u_2u_2''$ be their root edges correspondingly, and $L(u_1')\le L(u_1''), L(u_2')\le L(u_2'')$ . We consider a new tree obtained by removing the edges $u_1u_1'', u_2u_2'$ and adding $u_1 u_2'', u_2u_1'$ . The new tree $T'$ is already balanced at the root vertex and $f(T')=f(T).$ Again, by the induction hypothesis we can make $T'$ balanced at all other vertices without increasing $f(T')$ .
It remains to consider the second case when one of the vertices $u_1,u_2$ is a leaf, say it’s $u_2$ . By the hypothesis, we may assume the tree $T_1$ starting from $u_1$ is a balanced one. Let $u_1'$ be a leaf of $T_1$ such that the path from $u_1$ to $u_1'$ is the shortest one. Its length is $\lfloor \log(n-1)\rfloor$ since $T_1$ is balanced. We remove the edges $u_0u_1,u_0u_2$ , then add two additional vertices, as leaves, and connect $u_1'$ to them making $u_1'$ a fork. This new tree $T_1'$ is a balanced one, and we have $f(T_1')=f(T)-n+\lfloor \log(n-1)\rfloor+2,$ hence $f(T_1')\le f(T)$ for $n\ge 3.$ $\blacksquare$

Using this lemma and the definition $(1)$ we get

$f(n)=n+2f(n/2)$ ; for $n$ even, $n\ge 4$
$f(n)= n+f(\lfloor n/2 \rfloor)+f(\lfloor n/2 \rfloor+1)$ ; for $n$ odd, $n\ge 5$

This recurrence formula yields $f(n)=n\log n$ when $n$ is a power of $2$ . For the other values of $n$ we consecutively get: $f(3)=5, f(6)=16, f(7)=20, f(12)=44, f(13)=49, f(25)=118, f(50)=286, f(100)=672.$
Thus, the minimal number of sets in a family satisfying the initial conditions is $672+1=673.$

Ivan plays tic-tac-toe. Bulgarian TST 2020, p4.

In a previous post I commented problem 5 of the Bulgarian TST 2020. Here is a very nice combo problem from the same team selection test. This is a kind of problem where the right interpretation solves it. So, indeed, the point of view does matter!

Problem 4 (Bulgarian TST,2020). Ivan plays a game on $n\times n$ chessboard. He consecutively places checkers on the board, each time complying to the following rule. The square, the checker is placed on, must be empty and there must be even number of checkers placed on the $2n-2$ squares lying on the same row and column. The game is over if Ivan cannot place a checker any more. Find the minimal number of checkers on the table after the game ends.

Solution. Consider a bipartite graph $G (R,C)$ with vertices being the rows and columns of the $n\times n$ table, thus $|R|=|C|=n.$ We may interpret an edge in $G$ , connecting $r\in R$ and $c\in C$ , as the square where $r$ and $c$ intersect. The game being played can be translate as follows.
Initially $G(R,C)$ has no edges. Each move connects a vertex $r\in R$ with a vertex in $c\in C$ providing the degrees of $r,c$ have the same parities. Find the minimum number of edges when the game is over.

The key observation. After each move (an edge being created) the number of vertices with even (odd) degrees in $R$ and $C$ is the same. Indeed, each new edge flips the parities of its incident vertices.
Suppose at the final position $R_0,R_1$ are the vertices with even, resp. odd degree in $R$ ; and $C_0,C_1$ – the vertices with even/odd degrees in $C$ . Denote $k:=|R_0|=|C_0|; \ell := |R_1|=|C_1|$ . We cannot add any edge, so all edges between $R_0$ and $C_0$ are drawn. The same holds for $R_1$ and $C_1$ . It means

$|E(G)|\geq k^2+\ell^2\,,\, k+\ell=n\quad (1)$

The minimum value of the RHS is attained when $k$ and $\ell$ are equal or almost equal. It remains a bit more work to be done in order to nail the right estimate. The parity of $n$ is essential, and we consider the two possible cases.

1) $n$ is odd, $n=2k+1$ . By $(1)$ it follows

$E(G)\ge k^2+(k+1)^2$

The estimate can be attained. Partition $R$ , resp. $C$ into two sets $R_0,R_1$ , resp. $C_0,C_1$ where $|R_0|=|C_0|=k, |R_1|-|C_1|=k+1$ . It’s enough to construct a valid sequence of edges leading to a final position where all vertices in $R_0$ are connected to all vertices in $C_0$ and all vertices in $R_1$ are connected to all vertices in $C_1$ and no more edges are drawn. Since $|R_0|, |R_1|$ have different parities, it’s a final position, no more edge can be drawn. To construct a valid sequence of moves leading to full bipartite graph $G(X,Y)$ , where $|X|=|Y|=\ell,$ we make $\ell$ steps. At each step $i=0,1,\dots,\ell-1$ we connect $x_s$ with $x_{s+i}\,,\,s=1,2,\dots,\ell$ where $s+i$ is taken modulo $\ell$ .

2) $n$ is even, $n=2k$ . The above construction is no more valid since $|R_0|,|R_1|$ have the same parity, no matter how $R$ is partitioned.
Let $G(R,C)$ be a final position, $R_0, C_0$ be vertices with even degrees, $R_1,C_1$ – the odd ones and $|R_0|=|C_0|=k+s, |R_1|=|C_1|=k-s, 0\le s\le k.$ Then, all edges between $R_0$ and $C_0$ are present and the same holds for edges between $R_1,C_1$ . There must exist additional edges, because the degrees of, say $R_1$ and $C_1$ , have to be increased with at least $1$ . Thus, there are at least $2(k-s)$ additional edges. Hence

$E(G)\ge (k+s)^2+(k-s)^2+2(k-s)=$
$=2k^2+2k +2s^2-2s\ge 2k^2+2k$

The equality is attained when $s=0$ or $s=1$ . The example is a bit harder than in the previous case. It’s possible to obtain a final configuration when $s=1$ .
We partition $R$ , resp. $C$ into two sets, $R_0, R_1$ , resp. $C_0,C_1$ with $|R_0|=|C_0|=k-1, |R_1|=|C_1|=k$ plus two additional vertices $r\in R, c\in C$ . We initiate a process of making full bipartite graphs $G_1(R_0,C_0), G_2(R_1,C_1)$ as shown above, and at each step switch $\{r,v\}$ to $G_1$ and $G_2$ . Finally, we obtain two full bipartite graphs $G_1(R_0,C_0)$ and $G_2'(R_1\cup\{r\}, C_1\cup\{c\})$ and moreover $r,c$ are connected to all vertices in $C_0$ resp. $R_0$ .

Bulgarian TST 2020, problem 3 >>

Bulgarian NMO 2020, Part III. Center of Gravity Estimate.

I’ve already commented on two problems from the Bulgarian NMO 2020 (problem 5 and problem 6). Here is another problem from the same competition.

Problem 2. Let $b_1, b_2,\dots,b_n$ be real numbers with sum $2$ and $a_0,a_1,\dots, a_n$ be real numbers satisfying: $a_0=a_n=0$ and $|a_i-a_{i-1}|\leq b_i, i=1,2,\dots,n.$ Prove that

$\displaystyle \sum_{i=1}^n(a_i+a_{i-1})b_i\leq 2$

Proposed by Nikolay Nikolov.

Very nice problem. An inequality, because many people still want their inequalities, but not a standard one. Not relying on some routine well known tricks! One must think it with his own head. I plan to give a solution, based on an idea, different from the two official ones. But let me first present two physics interpretations.

Center of Gravity interpretation.

We can write the inequality like

$\displaystyle \sum_{i=1}^n\frac{a_i+a_{i-1}}{2}b_i\leq 1 \quad (1)$

Now, interpret every interval $[a_{i-1},a_{i}], i=1,2,\dots,n$ as a piece of a stick with mass $b_i$ . Just for convenience, we can assume all $a_i,i=1,2,\dots, n$ are non negative, since making them positive increases the LHS of $(1)$ So, we obtain a stick $S$ , which may be folded multiple times in some places and with length $\ell=\max \{a_i:i=1,\dots,n\}\le 1$ . The center of gravity $c$ of $S$ is obtained as

$c=\displaystyle \frac{1}{b_1+b_2+\dots+b_n}\sum_{i=1}^n\frac{a_i+a_{i-1}}{2}b_i=\frac{1}{2}\sum_{i=1}^n\frac{a_i+a_{i-1}}{2}b_i$

But intuitively, $c\ge 1/2$ since we can move the center of gravity of $S$ to the right by shifting the pieces of $S$ folded more than 2 times to the right. So, $c$ is maximal when the stick has length exactly $1$ in which case $c=1/2$ . This is of course not a rigorous explanation, but it helped me to solve it the way presented at the last paragraph.

Another physics interpretation.

Actually, it’s a fully rigorous solution. Suppose a point $x=x(t)$ is moving along $Ox$ axis depending on time $t\in (0,2)$ . It moves with constant speed $v_i=(a_i-a_{i-1})/b_i$ between every two points $a_{i-1},a_i$ , thus it takes it time $\Delta t_i=b_i$ to do this. Let at the moments $t_0=0,t_1,\dots,t_n=2$ the point is at the positions: $x(t_0)=a_0=0,x(t_1)=a_1,\dots,x(t_n)=a_n=0.$ . Since $|a_i-a_{i-1}|\le b_i$ the speed $x'(t)$ of $x$ is at most $1$ at any moment $t\in[0,2].$ It easily follows

$\displaystyle \frac{x(t_{i-1})+x(t_i)}{2}(t_{i+1}-t_i)=\int_{t=t_{i-1}}^{t_i}x(t)\,dt$

Thus

$\displaystyle \sum_{i=1}^n\frac{a_i+a_{i-1}}{2}b_i=\int_0^2 x(t)\,dt\quad (2)$

Since $x(0)=x(2)=0$ , it follows $\displaystyle x(t)=\int_0^t x'(u)\,du=\int_{2}^t x'(u)\,du$ , hence we get

$\displaystyle \int_0^2 x(t)\,dt=\int_0^1\int_0^t x'(u)\,du\,dt+\int_1^2\int_2^t x'(u)\,du\,dt\le$
$\displaystyle \leq \int_0^1\int_0^t 1\,du\,dt+\int_1^2\int_t^2 1\,du\,dt=\int_0^1 t\,dt+\int_1^2(2-t)\,dt=1$

Omitting the phisics notion, it actually is a rigorous math solution.

Another solution.

Take any two points $a_{i-1},a_i$ and suppose $a_{i-1}\le a_i$ (the other case is the same). Let $a_{i-1}=x_0\le x_1\le\dots \le x_{k}=a_i$ be any additional points inside $(a_{i-1},a_i)$ and $b'_j, j=1,2,\dots,k$ satisfy

$\displaystyle b'_j=\frac{x_j-x_{j-1}}{a_{i}-a_{i-1}}b_i\,, \,j=1,2,\dots,k$

Then it easily follows

$\displaystyle \frac{a_i+a_{i-1}}{2}b_i = \sum_{j=1}^k \frac{x_{j}-x_{j-1}}{2}b'_j$

It means, we can add, if needed, additional points to the given $(a_i)$ ‘s obtaining a set $K$ of base knots $0=c_0<c_1<\dots<c_m$ and points $X= (x_i)_{i=0}^k, x_0=x_k=0,k>m$ such that $x_j\in K, j=0,1,\dots,k$ and if $x_j=c_s$ then either $x_{j+1}=c_{s+1}$ or $x_{j+1}=c_{s-1}$ . Moreover, the LHS of $(1)$ equals

$\displaystyle \sum_{i=1}^k\frac{x_i+x_{i-1}}{2}b'_i \quad (3)$

for some $b'_j\ge |x_j-x_{j-1}|,j=1,2,\dots,k$ . Suppose there exist $j\in [1..k]$ with

$x_j=c_s, x_{j+1}=c_{s-1},x_{j+2}=c_s\quad (4)$

Then we transform the sequence $X=(x_j)$ to another one $X'$ defined as

$x_0,x_1,\dots,x_j, x_{j+2},\dots, x_r=c_m, c_m+c_s-c_{s-1},c_m,x_{r+1},\dots,x_k$

and add one additional knot $c_m+c_s-c_{s-1}$ to $K.$ In this way, jumping from $X$ to $X'$ , we increase the LHS of $(1)$ . Thus, we can consecutively increase the LHS of $(1)$ till no such example $(4)$ exists, meaning $x_j$ increases (stepping on the knots ) from $0$ to its maximal value and then decreases back to $0$ . Further, we can increase the distance between each two adjacent knots, such that $|x _j-x_{j-1}|=b_j$ still increasing the LHS of $(1)$ . Finally, in this case, it easily follows

$\displaystyle \sum_{i=1}^k\frac{x_i+x_{i-1}}{2}|x_j-x_{j-1}| =1$

Almost additive function. Bulgarian TST 2020, p5.

A problem from the Bulgarian TST for IMO 2020, held 07/07/2020.

Problem 5 (second day). A function $f : \mathbb{R} \to \mathbb{R}$ is given, satisfying

$\displaystyle |f(x+y)-f(x)-f(y)|\le 1, \forall x,y\in\mathbb{R}$

Prove there exists unique function $g:\mathbb{R}\to\mathbb{R}$ such that

$\displaystyle g(x+y)=g(x)+g(y)\text{ and }|f(x)-g(x)|\le 1, \forall x,y\in \mathbb{R}$

We’ll call any such function $f$ , almost additive. The plan is as follows. We first prove existence of $g$ it in case the domain of $f$ is $\mathbb{Z}$ (instead of $\mathbb{R}$ ). In this case $g$ is linear. This is proved in the Lemma 1 below and it’s the first essential part. Then we extend it naturally to $\mathbb{Q}$ . At the final step a Hamel basis of $\mathbb{R}$ over $\mathbb{Q}$ is used to make the extension possible and here comes the second essential part. One must prove that after the extension, $g$ still sticks close to $f$ . The uniqueness of $g$ is easier.
A different approach is shown here [1].

Lemma 1. $f:\mathbb{Z}\to \mathbb{R}$ satisfies

$\displaystyle |f(x+y)-f(x)-f(y)|\le 1, \forall x,y\in\mathbb{Z}\quad (1)$

Then there exists a linear function $g:\mathbb Z\to\mathbb R, g=kx$ with

$|f(x)-kx|\le 1, \forall x\in \mathbb{Z} \quad (2)$

Moreover, $g$ is unique.

Proof of Lemma 1. For any fixed $x\in\mathbb{Z}$ let L(x) be the set of all linear functions that satisfy $(2)$ for that fixed $x$ . Thinking of a linear function $g=kx$ as of its coefficient $k\in\mathbb{R}$ we may interpret $L(x)$ as an closed interval $[k_1,k_2]$ where $k_1,k_2$ are determined from the conditions $k_1x=f(x)-1,k_2x=f(x)+1$ . We will prove every two closed intervals $L(x), L(y), x,y\in\mathbb{Z}$ intersect, see the picture. It would imply all of them have non empty intersection.

Any two sets of linear functions intersect.

Suppose, for the sake of contradiction, $L(x)\cap L(y)=\emptyset, x< y\in \mathbb{Z}$ . It means there exists a function $g(x)=kx$ such that for $\Delta_1:=f(x)-kx,\Delta_2:=f(y)-g(y)$ , we have $|\Delta_1|>1, |\Delta_2|>1$ and $\Delta_1,\Delta_2$ have different signs. Let $f_1(x):=f(x)-g(x)$ . Then $f_1$ is also almost additive function, and $f_1(x)=\Delta_1, f_1(y)=\Delta_2$ . Using $(1)$ for $y-x, x$ it easily follows $|f_1(y-x)|>1$ and $f_1(y-x)$ is with the same sign as $\Delta_1$ . Proceeding the similar way as in the Euclidean algorithm does, we obtain that $|f_1(d)|>1, |f_1(2d)|>1$ and $f_1(d),f_1(2d)$ are with different signs, where $d=\mathrm{gcd}(n,m)$ . Again using $(1)$ for $x=y=d$ we obtain contradiction.
Now, since any two intervals $L(x), L(y)$ have non-empty intersection, by Helly’s theorem and the finite intersection property of a family of compact sets, it follows there exists

$\displaystyle k\in \bigcap_{x\in\mathbb{Z}}L(x)$

It implies, $|f(x)-kx|\leq 1, \forall x\in\mathbb Z.$ The uniqueness part is easy. Indeed, if $g,h$ are two different linear functions we can make $|g(x)-h(x)|$ as large as we want, which rules out the possibility they both satisfy $(2)$ . $\blacksquare$

Further, we prove the same claim as in lemma 1, but in case the domain of $f$ is $\mathbb Q$ .

Lemma 2. $f:\mathbb{Q}\to \mathbb{R}$ satisfies

$\displaystyle |f(x+y)-f(x)-f(y)|\le 1, \forall x,y\in\mathbb{Q}$

Then there exists unique linear function $g:\mathbb Q\to\mathbb R, g=kx$ with

$|f(x)-kx|\le 1, \forall x\in \mathbb{Q}$

Proof of lemma 2. By Lemma 1, there exists $k\in \mathbb R$ satisfying $(2)$ . Let $\frac{p}{q}\in \mathbb{Q}$ . Consider the set $S:=\{k\cdot \frac{p}{q} : k\in \mathbb Z\}$ . We can again apply Lemma 2 over the set $S$ and find $g_1:= k_1x, k_1\in\mathbb R$ satisfying the same condition $(2)$ but over $S$ . Using $\mathbb Z\cap S=\{kp : k\in \mathbb Z\}$ it easily follows $k_1=k$ . The uniqueness argument is the same as in lemma 1. $\blacksquare$

At this point there are three possible ways to extend $g$ over all reals, and that extension may not be a linear function anymore. The first one is mapping $\mathbb R$ to some initial segment of ordinals, and using transfinite induction to construct the expansion. The second one is using the Zorn lemma, which is virtually the same argument. The third way is using a Hamel basis of $\mathbb R$ , which again is just another variation. In all of these ways the essential part is a consistency argument needed, in order $g$ still to stick close to $f$ . I’ll apply the third plan.

Let $B=\{b_i : i\in I\}$ be a Hamel basis of $\mathbb R$ , where $I$ is some index set (uncountable). For any $i\in I$ consider the set $S_i := \{r\cdot b_i : r\in \mathbb Q\}$ . Applying Lemma 2 over $S$ we obtain $k_i\in\mathbb R$ such that $|f(rb_i)-k_irb_i|\le 1, \forall r\in\mathbb Q$ . We define $g$ as

$\displaystyle g\left(\sum_i r_ib_i\right):= \sum_i k_ir_ib_i$

where the summation is over all finite subsets of $I$ . For any subset $J\subset I$ we have

$\displaystyle \left|f\left(\sum_{i\in J} r_ib_i\right)-g\left(\sum_{i\in J} r_ib_i\right)\right|\leq$
$\displaystyle \le \left|f\left(\sum_{i\in J} r_ib_i\right) -\sum_{i\in J} f(r_ib_i)\right| + \sum_{i\in J} \left| f(r_ib_i) -k_ir_ib_i \right|\le (2|J|-1) \quad (3)$

That’s, $g(x)$ cannot be too apart from $f(x)$ when $x$ is presented as a linear combination of some fixed number of basis vectors. It remains to prove

$|f(x)-g(x)|\leq 1, \forall x\in \mathbb{R}$

Suppose, for the sake of contradiction, it fails for some $x_0=\sum_{i\in J}r_ib_i$ , thus

$|f(x_0)-g(x_0)|>1 \quad (4)$

We consider the set $S:=\{rx_0 : r\in\mathbb R\}$ . Applying lemma 2, there exists a linear function $g_1 : S\to \mathbb{R}$ with $|f(s)-g_1(s)|\le 1, \forall s\in S$ . Using $(3)$ it yields

$|g(s)-g_1(s)| \le |g(s)-f(s)|+ |f(s)-g_1(s)|\le 2|J|-1+1=2|J|$

Note that $g$ is also a linear function over $S$ and $g\neq g_1$ because of $(4)$ . It means $|g(s)-g_1(s)|$ can be made as large as we want, contradiction. The uniqueness of $g$ follows as in Lemma 1.

Bulgarian TST 2020, problem 4. >>

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

Bulgarian NMO, 2020, part II.

In the previous post, we considered a problem from the Bulgarian NMO, 2020. Here comes the next problem – problem 6, which in my opinion is the most interesting one given on that competition. And maybe, the most difficult one (leaving alone the already commented problem 5), thou the idea behind it is not unusual.

Problem 6. Let $f(x)$ be a nonconstant real polynomial. The sequence $\displaystyle \{a_i\}_{i=1}^{\infty}$ of real numbers is unbounded and

$a_i <a_{i+1}<a_i+2020, \forall i\in\mathbb{N}$

The integers $\displaystyle \lfloor{|f(a_1)|}\rfloor , \lfloor{|f(a_2)|}\rfloor , \lfloor{|f(a_3)|}\rfloor, \dots$ are written consecutively one after another hereby their digits form an infinite sequence of digits $\displaystyle \{s_k\}_{k=1}^{\infty}, s_k\in\{0, 1, \dots, 9\}.$ Let $n$ be any natural number. Prove that every number of $n$ digits is present in the set $\displaystyle \{\overline{s_{n(k-1)+1}\,s_{n(k-1)+2}\,\cdots s_{nk}} : k\in\mathbb{N}\}$ .

Author: Aleksandar Ivanov.

The idea is that the sequence $b_i := \lfloor{|f(a_i)|}\rfloor, i=1,2,\dots$ doesn’t increase too fast, so for any pattern of $n$ digits there exists as many as we want consecutive terms of $(b_i)$ that begin with that pattern. The official solution also exploits a variation of that idea and is similar to the first post in [1].

Solution (rather an outline).

Let $\displaystyle b_i := \lfloor{|f(a_i)|}\rfloor, i\in\mathbb{N}.$ The following properties of the integer sequence $(b_i)$ clearly hold.

$\displaystyle \lim_{i\to\infty}\frac{b_{i+1}}{b_i}=1.$
$\displaystyle \{b_i\}_{i=1}^{\infty}$ is unbounded.

These two properties are enough to prove the claim. Let $n\in \mathbb{N}$ and $M:=\overline {d_1\,d_2\,\dots\,d_n},d_i\in\{0,1,2,\dots,9\}$ be any $n$ -digit number. Take some large enough $m\in\mathbb{N}$ and let

$\displaystyle M_1:=\overline{d_1\,d_2\,\dots\,d_n\,\underbrace{0\,0\,\dots\, 0}_{m\text{ 0's}}}$

$\displaystyle M_2:=\overline{d_1\,d_2\,\dots\,d_n\,\underbrace{9\,9\,\dots\, 9}_{m\text{ 9's}}}$

It follows for large enough $m$

$\displaystyle \frac{M_2}{M_1}=\frac{M10^m+10^{m+1}-1}{M10^m}>1+\frac{1}{2M}$

Because of 2), the sequence $(b_i)_{i=1}^{\infty}$ must cross any interval $[M_1,M_2].$ Because of 1) we can take $M_1$ large enough (making $m$ large enough), such that as many consecutive terms $b_i$ hit the interval $[M_1,M_2]$ as we want. It means that inside the sequence $\{s_i\}_{i=1}^{\infty}$ there exist $r$ consecutive patterns

$\displaystyle d_1\,d_2\,\dots\,d_n\,\underbrace{*\,*\,\dots\, *}_{m\text{ digits}}$

where $r\in\mathbb{N}$ depends on $m$ , but can be made as large as we want. At this point, we have a window of $n$ adjacent positions stepping along those $r$ consecutive patterns. It’s enough to take $m\equiv 1\pmod n$ to be sure the window hits $d_1\,d_2\,\dots\,d_n$ after passing along at most $n$ of the patterns.

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

Bulgarian NMO, 2020, part I.

The final round this year was held on July 29,30. Two months later than usual, due to that mass hysteria, called Covid-19. Nevertheless, better late than never! Good problems were presented, I think. Except just one. I intend to consider some of them here in 2-3 posts. Let’s begin with the bad one.

Problem 5 (Bulgarian NMO,2020). Given $n$ points in the plane, some of them connected with segments. Some of the segments are colored white, some others – black satisfying the following condition. There exist two cycles – one consisting of white segments, the other – of black ones, each of them passes through every one of the points exactly once.
It’s known $AB$ and $BC$ are white segments. Prove that all of the segments can be recolored with red and blue, such that: $AB$ and $BC$ be both red. Not all of the white segments are allowed to become red. There again exist one red and one blue cycle that pass through each point exactly once.

It looks promising and pleasant, but after half an hour efforts, I realized it was a hard problem. We have a 4-regular graph with two disjoint Hamiltonian cycles on it and want to prove there exists another 2 Hamiltonian cycles and moreover, with some additional condition. I searched for “Hamiltonian cycles in 4-regular graph” and 5 min. later found the theorem presented below. It still looked like a nice problem, because the problem was a very special case of that result, and there could exist some different approach to make it. In order to be more specific, I need to present that Thomason’s result. Two short definitions first.

Definitions. Given a $4$ -regular graph $G$ , we say $\{H_1,H_2\}$ is a Hamiltonian decomposition of $G$ if $H_1$ and $H_2$ are edge disjoint Hamiltonian cycles in $G$ . It implies $G=H_1\cup H_2$ . Let $P$ be the set of all Hamiltonian decompositions of $G$ ( $P$ may be empty). For any edges $w,w'\in E(G)$ by $P(w,w')$ we denote the set of Hamiltonian decompositions of $G$ for which both $w,w'$ belong to the same cycle. Analogously, $Q(w,w')$ denotes the set of Hamiltonian decompositions of $G$ for which both $w,w'$ belong to different cycles.

Theorem (A.G. Thomason, 1978). Let $G$ be a finite undirected $4$ -regular graph (multigraph) of order at least $3$ . Then

$|P(w,w')|$ is even for any $w,w'\in E(G)$ .
$|Q(w,w')|$ is even for any $w,w'\in E(G)$ .
The number of Hamiltonian decompositions of $G$ is even.

Thus, the claim of the problem is just the first entry 1) of the above result in the special case $w,w'$ are adjacent. Indeed, since there is one such decomposition, by 1) there must exist another one.
So, one may think that the proof of problem 5 should be easier than this theorem, since it’s just a very special corollary. The proposer of the problem was aware of the mentioned result and maybe he had found some simpler way of proving that special case!?
Finally, I gave up and looked at the official solution. I was amazed to see it was the same as Thomason’s proof. In order to prove the problem, one must prove all 1), 2), 3). In fact, the official solution just follows the Thomason’s proof.
As I see it now, Thomason wanted to prove 3). But as it appeared (as it always happens) he was forced to prove 1) and 2) and it was part of his play, pursuing the proof, and all 3 entries are strongly entangled. The proof goes by induction and depends on all of them. So, it’s easier to prove that theorem (as written) than problem 5 itself.

Here is a proof of the Thomason’s result, as presented in [1]. Very cute argument! But, my opinion is, problems like this one should never appear on math competitions. I’ll be glad if someone manages to prove this problem in a more straightforward manner.

Thomason’s result. (Decompositions of Graphs, Juraj Bosak.) see [1]

To the next part >>

References.
[1] Juraj Bosak, Decompositions of Graphs, Taylor & Francis, 1990; Lemma 11.46, p134.