A Point of View.

BMO 2023 Shortlist, A4. Each Bounded Sequence has Closely Spaced Elements.

In the previous post I considered a combinatorial problem from Balkan Math Olympiad (BMO) 2023 shortlist. Here we continue with a problem from the same shortlist – a problem that I proposed to BMO 2023.

Problem (BMO SL 2023, A4). Prove that there exists a real number $c<1$ such that for each sequence ${x_n}_{n=1}^{\infty}, 0\le x_n\le 1, \forall n\in\mathbb{N}$ , there are infinitely many pairs $n,m\in \mathbb{N}, n<m$ such that

$\displaystyle |x_n-x_m|\le \frac{c}{m}\qquad (1).$

2) Prove that the above statement holds for $c=3/4.$
(Dragomir Grozev)

This was the exact wording I proposed to BMO 2023. The text that appeared in the shortlist was changed a bit. It wants to show that it holds for some constant $c<3/4$ . In fact, the official solution in the shortlist shows that $c=2\log_22$ works. It uses a bit (just a bit) of calculus. We discussed this problem in the Bulgarian BMO 2024 camp and during the lecture Marin Hristov (BGR 1 and gold medal from BMO 2024) also solved it using an estimate of the partial sum of harmonic series. His solution is easier than mine. It yields $c=2\log_22$ .

So, I’ll present my original solution with a remark how it can be improved a bit to get $c<3/4$ . By the way, I think that any constant $c>1/2$ works ( $c=1/2$ doesn’t), but I don’t know how to prove it.

Solution. Let $c=3/4$ and $(x_n)$ be any sequence as in the statement. Arguing by contradiction, suppose that there only finitely many pairs $(n,m), n<m$ that satisfy $(1).$ Fix some $N\in \mathbb{N}$ and view on the process of consecutively choosing the first $N$ points $x_1,x_2,\dots, x_N$ in $[0,1]$ as being a tree with a root $r$ which represents the interval $[0,1]$ and each next point subsequently splits some interval into 2 subintervals – see fig.1 (the left graph is $T$ and $T'$ is on the right side).

In this way we obtain a binary tree $T.$ Its leaves (each one ends with an arrow) are the final intervals the interval $[0,1]$ is split into, after $N$ steps. Let us delete those edges $\overrightarrow{ab}$ of $T$ that are terminal edges, that is, no other directed edge starts from $b.$ Let the remaining tree is $T'.$ There are three types of vertices in $T'.$ The ones that have degrees $3, 2$ and $1$ (we don’t count the root $r$ ). Denote the corresponding sets as $V_3,V_2$ and $V_1$ respectively. Let $k_3=|V_3|, k_2=|V_2|, k_1=|V_1|.$ We have

$\displaystyle 3k_3+2k_2+k_1=2N-1.$

The edges we have deleted from $T$ in order to get $T'$ are just the ones that represent the final intervals that $[0,1]$ is partitioned into. Hence,

$\displaystyle 2k_1+k_2=N+1$

This yields

$\displaystyle 3k_3+2k_2+k_1 + 3= 4 k_1+2k_2.$

Thus, $k_3=k_1-1.$ Each vertex $x\in V(T')$ corresponds to some $x_n, n\in[1..N]$ for which $x\equiv x_n.$ Denote this correspondence as $n=n(x).$ For each $x\in V_2$ there is only one directed terminal edge $\displaystyle \overrightarrow{xx'}$ that starts from $x.$ It corresponds to an interval $i(x).$ For $x\in V_1,$ there are two terminal edges that originate from $x.$ Let us denote the corresponding intervals as $i'(x),i''(x)$ and let $i(x)=i'(x)\cup i''(x).$ Except for finitely many (exceptional) vertices $V_e$ , it holds

$\displaystyle n(x)>\frac{c}{|i(x)|}\,,\, \forall x\in V_2$

$\displaystyle n(x)>\frac{c}{\min\left(|i'(x),i''(x)|\right)}\ge \frac{2c}{|i(x)|}\,,\,\forall x\in V_1$

Therefore

$\displaystyle \sum_{x\in V(T')} n(x)=\sum_{x\in V_1} n(x)+\sum_{x\in V_2} n(x)+\sum_{x\in V_3} n(x)$

$\displaystyle \ge \sum_{x\in V_1} \frac{2c}{|i(x)|} + \sum_{x\in V_2} \frac{c}{|i(x)|}+\sum_{x\in V_3} n(x)-\sum_{x\in V_e\cap(V_1\cup V_2)} \frac{2c}{|i(x)|}$

$\displaystyle\ge \frac{2c k_1^2}{I_1}+\frac{ck_2^2}{I_2}+\frac{k_3(k_3+1)}{2} -C$

where we used Bernstrom’s (or AM-HM) inequality and denoted:

$\displaystyle I_1:=\sum_{x\in V_1}|i(x)|$

$\displaystyle I_2:=\sum_{x\in V_2}|i(x)|$

$\displaystyle C:=\sum_{x\in V_e\cap(V_1\cup V_2)} \frac{2c}{|i(x)|}.$

We have estimated $\displaystyle \sum_{x\in V_3} n(x)$ with $k_3(k_3+1)/2$ because the worst-case scenario is when the set $\{n(x): x\in V_3$ \} consists of the first $k_3$ smallest numbers. This is where an improvement can be made. If it is indeed the situation for the first $N$ vertices, it would be not like that if we put, say, some additional $N$ vertices.
Now, note that $I_1+I_2=1$ and $C$ does not depend on $N$ because $|V_e|$ is bounded as $N\to \infty.$ Since $\sum_{x\in V(T')} n(x)=\frac{N(N+1)}{2}$ and $k_3=k_1-1$ it further yields,

$\displaystyle\frac{N(N+1)}{2}\ge \frac{2c k_1^2}{I_1}+\frac{ck_2^2}{I_2}+\frac{k_3(k_3+1)}{2} -C$

$\displaystyle \frac{N(N+1)}{2}\ge \frac{2c k_1^2}{I_1}+\frac{ck_2^2}{I_2}+\frac{k_1(k_1-1)}{2} -C.$

sing again Bergstrom’s inequality we get

$\displaystyle \frac{a^2}{c}+\frac{b^2}{d}\ge \frac{(a+b)^2}{c+d}$

and since $I_1+I_2=1,$ we obtain

$\displaystyle \frac{N(N+1)}{2}\ge c\left(\sqrt{2}k_1+k_2\right)^2 + \frac{k_1(k_1-1)}{2} -C$

$\displaystyle \frac{N(N+1)}{2}\ge 2ck_1^2 +2\sqrt 2 c k_1k_2 +ck_2^2 +\frac{k_1(k_1-1)}{2} -C$

Next, we eliminate $k_2$ using $k_2=N+1 -2 k_1.$

$\displaystyle \frac{N(N+1)}{2}\ge 2ck_1^2 +2\sqrt 2 c k_1(N+1 -2 k_1) +c(N+1 -2 k_1)^2 +\frac{k_1(k_1-1)}{2} -C$

$\displaystyle \frac{N(N+1)}{2}\ge \left(5-3\sqrt 2\right)k_1^2 -\left(3-\frac{3}{2}\sqrt 2\right)k_1\left(N+1\right)+\frac{3}{4}(N+1)^2-\frac{k_1}{2}-C\qquad(2)$

Denote the right hand side as $\displaystyle f(k_1), k_1\in \left[0,(N+1)/2\right].$

$\displaystyle f'(k_1)=\left(10-6\sqrt 2 \right)k_1 - \left(3-\frac{3}{2}\sqrt 2\right)\left(N+1\right)-\frac{1}{2}$

This implies $f'(k_1)\le 0, \forall k_1\in \left[0,(N+1)/2\right],$ which means $f(k_1)$ decreases in $[0,(N+1)/2],$ so its minimum value is attained when $k_1=(N+1)/2.$ From $(2),$ it follows

$\displaystyle \frac{N(N+1)}{2}\ge \frac{(N+1)^2}{2} -\frac{N+1}{4} -C$

which holds for all $N\in \mathbb{N},$ but it is not true when $N$ is large enough, contradiction.

BMO 2023 Shortlist, C3

Here is a nice combinatorial problem that was given in the Bulgarian team selection tests for RMM 2024. It was from BMO 2023 shortlist

Problem (BMO 2023 Shortlist, C3). In a given community of people, each person has at least two friends within the community. Whenever some people from the community sit on a round table such that each adjacent pair of people are friends, it happens that no non-adjacent pair of people are friends. Prove that there exist two people of this community such that each has exactly two friends and they have at least one common friend.

I’ll present two solutions – the official one and another solution I came up with that uses a spanning tree constructed through BSF algorithm. Let’s start with the latter.

A spanning tree comes to help.

We use graph language; a graph $G(V,E)$ is given, without chords and $\deg(v)\ge 2, \forall v\in V.$ We want to prove the following statement

(*) There exist two vertices $v_1,v_2\in V, v_1\ne v_2$ with $\deg(v_1)=\deg(v_2)=2$ which have a common neighbour.

Assume on the contrary it’s not true. Let us partition the vertices into two groups – $V_0$ be the set of all vertices of degree exactly $2$ and $V_1$ be the set of vertices with degree $3$ or more. Here are some observation based on our assumption.

$V_0$ does not contain a path of length 2. Indeed, if $v_1,v_2,v_3\in V_0$ and $v_1v_2\in E, v_2v_3\in E$ then $v_1,v_3$ would satisfy (*).
Each vertex of $V_1$ is connected to at most one vertex in $V_0.$

Thus, the configuration of edges that are incident to $V_0$ are like on fig. 1. Further we can assume that the graph is connected, because otherwise each connected component will satisfy the same condition. We choose a vertex $u\in V_1$ (see fig. 1) as a root and start constructing a spanning tree of $G$ using $DFS$ algorithm. Every time we hit a vertex, say $u_i\in V_1$ that is connected to a vertex in $V_0$ we go to $u_{i+1}$ and bach to $u_{i+2}\in V_1$ in case $u_{i+1}$ has two neighbours in $V_1$ or $u_j a_{j+1}u_{j+2}u_{j+3}$ in case $u_{j+1}$ is connected to another vertex $u_{j+2}\in V_0.$
This way, it cannot happen that a leaf of the resulting spanning tree is from $V_0.$ This is what we will exploit.

After the spanning tree $T$ is constructed, we take a leef $u'.$ Since $u'\in V_1$ we have $\deg_G(u')\ge 3$ and thus $u'$ is connected (in $G$ ) to at least two vertices $u_1, u_2.$ Since we used DFS algorithm, the vertices $u', u_1,u_2$ are comparable in $T$ , i.e. $u_2$ and $u_1$ lie on the (unique) path from $u'$ down to the root $u.$ But then $u'u_2$ is a chord in the cycle $u_1\dots u_2\dots u'u_1,$ contradiction.

Upside Down. Bulgarian NMO 2024, Problem 2.

Here is an interesting geometrical problem given in the recently held Bulgarian National Math Olympiad (NMO) 2024. It is actully a converse version of a well-known fact, which makes it curious. Here it is.

Problem (Bulgarian NOM 2024, p2). A triangle $ABC$ is given. The points $M$ and $P$ are respectively on $AB$ and $BC$ such that $AM=BC$ and $CP=BM.$ Let $O=AP\cap CM$ and $\angle ABC=2\angle AOM.$ Find $\angle ABC.$
(Nikolay Nikolov, Aleksander Ivanov)

Solution.

Answer: $90^{\circ}.$ Denote $\alpha:= \angle ABC$ . We interpret the configuration as follows see fig. 1. Thanks to Nevena for the nice drawing! We have an isosceles triangle $\triangle BA'C$ with $BC=BA'=a$ and $\angle A'BC=\alpha.$ Initially $P\equiv C, M\equiv B, A\equiv A'.$ Then, the three points $P, M,A$ start moving with equal velocities, that is, $CP=BM=A'A.$ It ends when $P$ reaches $B$ ( $M$ reaches $A'$ ).
We will prove something sharper – the following claim.

In case $\alpha<90^{\circ}$ the angle $\angle AOM$ is greater or equal to $90^{\circ}-\alpha/2$ . That is, $2\angle AOM\ge 180^{\circ}-\alpha>\alpha$ . The minimum value of $\angle AOM$ is attained in only two cases – when either $P\equiv C (M\equiv B)$ or when $P\equiv B (M\equiv A')$ .
In case $\alpha>90^{\circ}$ the angle $\angle AOM$ is less or equal to $90^{\circ}-\alpha/2$ . That is, $2\angle AOM\le 180^{\circ}-\alpha<\alpha$ . The maximum value of $\angle AOM$ is attained in only two cases – when either $P\equiv C (M\equiv B)$ or when $P\equiv B (M\equiv A')$ .

So, the only case when $2\angle AOM=\alpha$ is possible is $\alpha=90^{\circ}$ . In this case, it’s easy to see that $2\angle AOM=\alpha$ holds for any location of the moving points.

We prove the claim only in the first case – when $\alpha<90^{\circ}$ – the other case is absolutely similar. Let us denote $x=CP=BM=A'A.$ Clearly $0\le x\le a.$ We construct additional points $D, M'$ and $P'$ – see fig. 1 – such that: $BA'DC$ is a rhombus, $AM'\parallel MC, A'M=MC$ and $PP'\parallel DC, PP'=x.$ In fact, we translate $MC$ to $A'M'$ and $AP$ to $A' P'.$
Now, $\angle AOM=\angle M'A'P'$ . Denote $\angle 1:=DA'M'$ and $\angle 2:=CA'P'$ . It’s enough to prove $\angle 1\le \angle 2.$ In order to do it we prove $\tan\angle 1\le \tan\angle 2.$ It easily follows that $\angle P'CA' =90^{\circ}.$ Let $M'H\perp A'D.$ A bit of calculation needed. We have $M'H=x\sin\alpha, DH=x\cos \alpha ,$ so it follows

$\displaystyle \tan\angle 1=\frac{x\sin \alpha}{a-x\cos \alpha}.$

From $A'C=2a\sin \alpha/2$ and $CP'=2x\cos \alpha/2$ we get,

$\displaystyle \tan\angle 2=\frac{x}{a}\frac{\cos \frac{\alpha}{2}}{\sin\frac{\alpha}{2}}.$

This yields

$\displaystyle \tan\angle 1=\frac{2x \sin{\frac{\alpha}{2}} \cos{\frac{\alpha}{2}}}{(a-x)\cos \alpha +a(1-\cos \alpha)}=\frac{ 2x \sin{\frac{\alpha}{2}} \cos{\frac{\alpha}{2}} }{(a-x)\cos \alpha +2a\sin^2 {\frac{\alpha}{2}} }$

$\displaystyle \le \frac{x}{a}\frac{ \cos{\frac{\alpha}{2}} }{\sin{\frac{\alpha}{2}} } =\tan\angle 2$

because $(a-x)\cos \alpha\ge 0$ ( $\alpha<90^{\circ}$ ). Note that the equality is attained only if $x=0$ or $x=a.$ $\square$

So, we proved that the only possible value for $\alpha$ is $\alpha=90^{\circ}.$ It can be easily proved (with the same technique as above) that in this case $\angle 1=\angle 2,$ that is, $\angle AOM=\angle M'A'P'=45^{\circ}.$ By the way, you don’t need to worry about it. You only need just one example for which the configuration is valid, and it is obviously true when $M\equiv B$ or $M\equiv A'.$

King Arthur’s List. Bulgarian TST for BMO 2024.

I want to comment here on a problem I gave to Bulgarian TST for BMO 2024. Here is the story of this problem. About two years ago I came across a problem, (I don’t remember it’s statement – it was about a bipartite graph) and my idea was to delete its edges one by one, so that when one deletes an edge incident to a vertex, one has to delete another edge incident to the same vertex within a certain number of steps, say $k$ . It was interesting to estimate the minimum $k$ (as a function of the number of vertices $n$ ). Of course it depends on the given graph. For example, if you have a complete graph of $n$ vertices, it’s not difficult to see that $c_1n\le k\le c_2n$ for some constants $c_1,c_2.$ The point is that in this case, starting from an edge, you can reach any other edge passing through at most one intermediate edge. So, it’s more interesting to see what happens when the graph has fewer edges, for example if it is a tree. This is an interesting question, and it turns out that in this case $k\asymp n/\log n$ . The next problem is a version of this question asked for a complete binary graph. Note that the lower bound is not hard. The main difficulty is to construct a list in case $k$ is something like $n/\log n$ .

Problem (BGR TST 2024, p8). Let $n$ be a natural number. King Arthur has invited $2^n-1$ knights to an audience in Camelot. Merlin the Magician arranged the knights in a list numbered from $1$ to $2^n-1$ . It turned out that any two knights with numbers $a,b, a<b$ are friends if and only if $0\le b-2a\le 1$ . The king chose a natural number $k$ and ordered Merlin to make a new list with the following requirement. For each $1\le i\le 2^n-k-1$ , all friends of the knight with sequence number $i$ (in the new list) must be in positions among $1,2,\dots,i+k$ . Prove that the smallest $k$ , for which Merlin can fulfil Arthur’s wish, satisfies the condition

$\displaystyle \frac{1}{100}\cdot \frac{2^n}{n}\le k \le 100\cdot\frac{2^n}{n}.$

(Dragomir Grozev)

Solution

Let us construct a graph $T$ with vertex-set which is the set of all knights, numbered as in the first list. Two vertices are adjacent if the corresponding knights are friends. It can be seen that $T$ is a fully balanced binary tree – see fig. 1. We label each vertex with the knight’s number in the first list. Let us assume the vertices can be arranged in a row $i_1,i_2,\dots i_m$ as King Arthur requested, where $m=2^n-1$ and $i_j$ refers to the label of the corresponding vertex. There is a unique path in $T$ , $i_1=v_1 v_2 \dots v_{\ell}=i_m$ that connects the vertex labeled as $i_1$ and $i_m$ . Clearly, $\ell\le 2(n-1)+1$ , because the longest path in $T$ has length $2(n-1)$ . Note that the distance between the positions of $v_i$ and $v_{i+1}$ in the new list, is at most $k$ . This means that $(\ell-1)k\ge m-1$ which yields

$\displaystyle k\ge \frac{2^n-2}{2n-2}> \frac{2^n}{4n}$

which proves the lower bound for $k$ .

Now we will arrange the vertices of $T$ in a list. Let $\ell$ be a natural number which will be determined later. Denote by $v_1,v_2,\dots,v_{s}, s:=2^{\ell}$ the vertices of $T$ on the $\ell$ -th level, and let $T(v_1),T(v_2),\dots,T(v_s)$ be the subtrees with roots in these points – see fig. 1. Each of them has exactly $2^{n-1-\ell}$ leaves.

We successively put in a list the vertices of $T$ as follows. First, we place the last level of vertices of $T(v_1)$ , that is, its leaves. Then we put down the second to last level of $T(v_1)$ and the last level of $T(v_2)$ . At the $i$ -th step we place the $i$ -th level of $T(v_1)$ , counting from the bottom up (fig. 1), then the $i-1$ -th level of $T(v_2)$ (from the bottom up) and so on, and finally – the last layer of $T(v_i)$ (i.e. its leaves). The number of vertices we place at the $i$ -th step $i=1,2,\dots,s-\ell-1$ is equal to

$\displaystyle \sum_{j=0}^{i-1}2^{n-1-\ell-j}\le 2^{n-\ell}.$

We follow these steps until one of the two events happens.

We reach the root $v_1$ of $T(v_1)$ .
We place in the list the leaves of $T(v_s)$ .

The first event will happen after $n-\ell$ steps and the second one – after $s=2^{\ell}$ steps. To ensure that the second event occurs first we choose $\ell$ to be the largest positive integer for which $s=2^{\ell}\le n-\ell$ .

In this situation, at the $s$ -th step we have put the leaves of $T(v_s)$ in the list. On the $s+1$ -th step we put in the list the remaining vertices of $T$ . The number of all vertices in $T(v_s)$ without its last level does not exceed $2^{n-\ell-1}$ . The number of vertices in $T(v_{s-1})$ without its last two layers does not exceed $2^{n-\ell-2}$ and so on. Adding the vertices of $T$ up to its $\ell$ -th level, we obtain that the number of the vertices ordered at the last step is at most

$\displaystyle 2\cdot 2^{\ell} + 2^{n-\ell} \le 2\cdot 2^{n-\ell}\le 8\cdot \frac{2^n}{n}$

since $2^{n+2}\ge n$ . Clearly, for any vertex $v$ , placed at position $j$ in the first $s$ steps, all of its neighbours in $T$ , that are placed after it, are in positions with numbers not exceeding $j+2\cdot 2^{n-\ell}\le j+8\cdot \frac{2^n}{n}$ . Taking into account the number of vertices added in the last step, we get that in the constructed list the condition imposed by the king holds for

$\displaystyle k:= \left\lceil 16\cdot \frac{2^n}{n}\right\rceil.$

This proves the upper bound.

Romanian Master of Mathematics, 2024. NT problems!

Two nice number theory (NT) flavored problems were given at the recent RMM (Romanian Master of Mathematics) competition. The only needed knowledge of NT that one has to have in order to solve them consists of the following two facts. For any prime $p,$ 1) If $n_i\not\equiv 0\pmod p, i=1,2$ then $n_1n_2\not\equiv 0\pmod p.$ 2) For any integers $r,n_1,n_2$ with $n_1\not\equiv n_2\pmod p$ we have $n_1+r\not\equiv 0\pmod p$ or $n_2+r\not\equiv 0\pmod p.$
Yes, a fifth grader knows it. Still the problems are not so easy. Some people want strict boundaries between different subjects in math competitions. They want for example some “pure” NT problems. Of course, mathematics has different subjects. But they share common methods and technique called Math. Take for example the Euler’s theorem about the totient function.

$\displaystyle a^{\varphi(n)}\equiv 1\pmod n\text{ if } (a,n)=1\qquad(1).$

The proof of it goes like that. One takes the set $A$ of all residues $\{r_1,r_2,\dots,r_m\}$ modulo $n$ that are coprime with $n$ . Then one takes $a\in A$ and considers the set $A':=\{ar_1,ar_2,\dots,ar_m\}.$ It follows from very basic facts that all these numbers give distinct residues modulo $p$ and all of them are coprime with $n.$ This allows us to conclude $A=A'$ , that is, the second system of residues is just a permutation of the first one. Multiplying the elements in $A$ and the elements in $A'$ (the same sets modulo $p$ ), we get

$\displaystyle a^m\cdot r_1r_2\cdots r_m\equiv r_1r_2\cdots r_m\pmod p.$

Since $m=\varphi(n)$ (by the definition of $\varphi$ ), the result in $(1)$ follows.
One might argue that there is very little NT stuff in this proof – you take a set, multiply each of its elements and get a permutation – this could be seen as combinatorics! But it is still a number theory theorem. I thinks it’s silly to argue whether a problem is combinatorics or number theory, or something else. They all intertwine.
Let’s continue with the two mentioned NT problems from RMM 2024.

RMM 2024, Problem 2. Consider an odd prime $p$ and a positive integer $N < 50p$ . Let $a_1, a_2, \ldots , a_N$ be a list of positive integers less than $p$ such that any specific value occurs at most $\frac{51}{100}N$ times and $a_1+a_2 + \cdots + a_N$ is not divisible by $p$ . Prove that there exists a permutation $b_1, b_2, \ldots , b_N$ of the $a_i$ such that, for all $k = 1, 2, \ldots , N$ , the sum $b_1 + b_2 + \cdots + b_k$ is not divisible by $p$ .
(Will Steinberg, United Kingdom)

The following solution is similar to the official one, but it emphasizes on a constructive algorithm. Suppose we initially have a multiset $A$ of residues modulo $p$ (we allow $0\in A$ ) that satisfies the condition

$\displaystyle \text{Each value in }A\text{ occurs at most } \left\lceil \frac{|A|}{2}\right\rceil \text{ times.}\qquad(1)$

Then $A$ can be arranged in a row $b_1,b_2,\dots,b_N, N:=|A|$ that satisfies the problem’s condition. This arrangement can be done via a greedy algorithm with a little bit common sense. Here it is.
Because of condition $(1)$ there are at least two distinct values in $A$ . So, we start putting the elements of $A$ in a row, each time picking a residue that avoids a certain residue, i.e. it avoids the sum of the already arranged residues taken with a negative sign. Assume at some moment, we have a multiset $A'$ such that some of its values, say $r$ occurs exactly $\left\lceil {|A'|}/{2}\right\rceil$ times. We try to pick this value, and if we cannot do this, because we would hit $0$ , then we pick another residue $r_1\neq r$ , put it in the row and we put $r$ immediately after $r_1$ . Thus, we comply with the given condition and we are at position with a multiset $A''$ that consists of $|A'|-2$ elements. The point is that $A''$ still satisfies $(1)$, so we can continue with the same algorithm.

It remains to see what to do when initially some value $r$ in $A$ occurs $k$ times and $k>\left\lceil {|A|}/{2}\right\rceil$ times. This time we want $0\notin A$ . So,

$\displaystyle \left\lceil {|A|}/{2}\right\rceil < k<\frac{51}{100}|A|\qquad (2).$

Now, we put all the elements equal to $r$ , but no more than $p-1$ of them, one after another in a row. Any partial sum of this row is not $0$ , since $0\notin A$ . Because of $(2)$ and the fact that $|A|<50p$ , it easily follows that the remaining elements form a multiset $A'$ that satisfies $(1)$ . Further, we proceed with the above algorithm, avoiding a certain residue each time. $\square$

The next problem is problem 4 from the same competition.

RMM 2024, problem 4. Fix integers $a$ and $b$ greater than $1$ . For any positive integer $n$ , let $r_n$ be the (non-negative) remainder that $b^n$ leaves upon division by $a^n$ . Assume there exists a positive integer $N$ such that $\displaystyle r_n < \frac{2^n}{n}$ for all integers $n\geq N$ . Prove that $a$ divides $b$ .
(Pouria Mahmoudkhan Shirazi, Iran)

Assume that $b$ is not multiple of $a.$ Hence, $\displaystyle \frac{b}{a}=\frac{p}{q}$ where $(p,q)=1$ and $q>1$ . In this case we’ll prove something stronger. Namely, it’s even not possible that $r_n<\varepsilon_n a^n$ , where $\displaystyle \lim_{n\to \infty}\varepsilon_n =0$ , that is, it’s not possible that $r_n=o(a^n)$ .

Assume on the contrary it holds. Thus,

$\displaystyle b^n=ka^n+\varepsilon_n a^n.$

Multiplying both sides by $b$ it yields

$\displaystyle b^{n+1}=k\frac{b}{a}a^{n+1}+\varepsilon_n \frac{b}{a}a^{n+1}.$

It means that

$\displaystyle \varepsilon_{n+1}=\left\{k\frac{p}{q}+\varepsilon_n \frac{p}{q} \right\}$

where $\{\cdot\}$ denotes the fractional part. Now, for sufficiently large $n$ we have $\displaystyle \varepsilon_n \frac{p}{q}<\frac{1}{q},$ since $\displaystyle \varepsilon_n\to 0$ . Note that $\displaystyle k\frac{p}{q}$ is either integer or its distance to the nearest integer is at least $1/q.$ It gives us $\displaystyle \varepsilon_{n+1}>\varepsilon_n.$ This leads us to contradiction if we take a special $\displaystyle \varepsilon_n$ such that $\displaystyle \varepsilon_i<\varepsilon_n, \forall i>n.$ It is possible since $\varepsilon_n\to 0.$ $\square$

This problem is similar to Izho 2021, problem 1 – see [3] – the idea is the same. In fact, we proved that for given positive integers $b>a$ and $b$ is not multiple of $a,$ we can find infinitely many $n$ such that the residue that $b^n$ leaves upon division by $a^n$ is greater than $Ca^n$ for some constant $C$ that depends only on $a$ and $b.$

References.
[1] RMM 2024, p.2 – AoPS thread.
[2] RMM 2024, p.4 – AoPS thread.
[3] IZhO 2021, p.1 – AoPS thread.

Almost All Binary Polynomials are Square Free. RMM 2024, Problem 6.

Here we consider problem 6 of the recent Romanian Master of Mathematics competition – a very difficult problem. Nobody solved it during the tournament. Let me point out a very similar problem – RMM Shortlist 2020, A1 – see [3], proposed by the same author. I think it’s of similar difficulty. In my opinion both are not suitable for a high school Olympiad level, although I like them because it’s real math. Maybe they fit for Miklos Schweitzer competition, but on the other hand both problems are known results – the current one by Filaseta and Konyagin – see [2] – so the papers can easily be found by searching the web.

Problem (RMM 2024, problem 6). A polynomial $P$ with integer coefficients is square-free if it is not expressible in the form $P = Q^2R$ , where $Q$ and $R$ are polynomials with integer coefficients and $Q$ is not constant. For a positive integer $n$ , let $P_n$ be the set of polynomials of the form

$\displaystyle 1 + a_1x + a_2x^2 + \cdots + a_nx^n\text{ with } a_1,a_2,\ldots, a_n \in \{0,1\}.$

Prove that there exists an integer $N$ such that for all integers $n \geq N$ , more than $99\%$ of the polynomials in $P_n$ are square-free.
(Navid Safaei, Iran)

The proof is based on the ideas I saw in [4] and consists of 3 main statements. The proof of the last one is a version of a problem we did in a blogpost here – see [1].

It boils down to prove that if we take a random polynomial in $P_n,$ the probability that it is not square-free tends to $0$ as $n\to \infty.$ Hereafter, we refer to polynomials in $P_n$ that are not square-free as bad polynomials, and to the square-free ones as good. So, in other words, if we take a random polynomial in $P_n,$ the probability that it is bad tends to $0$ as $n\to \infty.$ Here are the milestones of our plan.

Claim 1. We’ll show that if we fix a natural number $d,$ the probability of taking a bad polynomial $P$ in $P_n$ with $P=Q^2R$ and $\deg(Q)\ge d$ can be made as small as we want if $d$ is large enough.
Claim 2. We prove that there are finitely many $Q$ with integer coefficients and $\deg(Q)<d$ for which there exists $n$ and $P\in P_n$ such that $Q\mid P.$
Claim 3. We prove that for each fixed polynomial with integer coefficients $Q,$ the probability of taking a polynomial $P\in P_n$ so that $Q\mid P$ tends to $0$ as $n\to \infty.$

Suppose that we already have the above three claims proven. The second claim ensures that there are only finitely many integer polynomials $Q_1,Q_2,\dots,Q_m$ with degrees less than $d$ that can divide a binary polynomial $P$ .
For any fixed $n$ we take a random polynomial $P\in P_n$ and let us introduce the following events. Hereafter, $Q$ denotes a polynomial with integer coefficients.

$\displaystyle E_1:= (P \text{ is bad and there exists }Q, \deg(Q)\ge d, \text{ such that }Q^2\mid P)$

$\displaystyle E_2:= (P \text{ is bad and if } Q^2\mid P \text{ then }\deg(Q)< d)$

$\displaystyle E_2':=(\text{there exists } i\,,\,1\le i\le m \text{ such that }Q_i\text{ divides } P)$

$\displaystyle E_2'(i):= (Q_i\text{ divides } P)$

Apparently,

$\displaystyle E_2\subset E_2'\subset \bigcup_{i=1}^m E_2'(i)$

which implies

$\displaystyle \mathbb{P}(E_2)\le \sum_{i=1}^m \mathbb{P}(E_2'(i)).$

Fix some $\varepsilon>0.$ The first claim shows that we can choose sufficiently large $d$ such that for any $n\ge d$ we have $\mathbb{P}(E_1)<\varepsilon.$ According to the third claim, we can choose $N_i$ such that for $n\ge N_i$ we have $\mathbb{P}(E_2'(i))<\varepsilon/m.$ Therefore, for $n>\max\{d,N_i: 1\le d\le m\}$ we have

$\displaystyle \mathbb{P}(P\text{ is bad })\le \mathbb{P}(E_1)+ \sum_{i=1}^m \mathbb{P}(E_2'(i))\le 2\varepsilon.$

This means that the probability of taking a bad polynomial can be made as small as we want by choosing a sufficiently large $n.$ It remains to prove the three statements.

Proof of Claim 1. Dealing with large squares dividing binary polynomials.

Let $d$ be a natural number. Hereafter, $Q$ and $R$ denote polynomial with integer coefficients and $P$ is a binary polynomial of degree $n.$ Suppose $P=Q^2R$ where $\deg(Q)=s\ge d.$ We reduce the polynomials $P,Q,R$ modulo 2, i.e. we substitute each coefficient with its residue modulo 2, thus obtaining new polynomials $P,\overline{Q}, \overline{R}$ ( $P$ remains the same). Clearly

$\displaystyle P=\left(\overline{Q}\right)^2\overline{R}\qquad(1).$

We can assume that $Q$ is a monic polynomial, hence $\deg\left(\overline{Q}\right)=\deg(Q)=s.$ Clearly, $\deg(\overline{R})=n-2s.$ Since $\overline{Q}$ has $s+1$ binary coefficients and $\overline{R}$ has $n-2s+1$ ones, all possible options for them are $2^{s+1}\cdot 2^{n-2s+1}=2^{n-2s+2}.$ Thus, the number of polynomials $P$ that satisfies $(1)$ is at most $2^{n-2s+2}.$ Therefore,

$\displaystyle \mathbb{P}(P=Q^2R, \deg{Q}=s)\le \frac{2^{n-2s+2}}{2^n}=4\cdot 2^{-s} .$

This yields,

$\displaystyle \mathbb{P}(E_1)\le 4\sum_{s\ge d}2^{-s}=\frac{1}{2^{d-3}}.$

which proves Claim 1.

Proof of Claim 2. Only finitely many “small” polynomials can divide a binary polynomial.

Let $P$ be a binary polynomial of degree $n.$ First to see that all roots of $P$ lie in the disk $\{z\in\mathbb{C} : |z|<2\}.$ Assume on the contrary $P(z)=0$ and $|z|\ge 2.$ Then

$\displaystyle |z|^n=|a_nz^n|=\left|\sum_{i=0}^{n-1}a_iz^i \right|\le \sum_{i=0}^{n-1}|a_iz^i|$

$\displaystyle \le \sum_{i=0}^{n-1}|z|^i=\frac{|z|^n-1}{|z|-1}<|z|^n,$

contradiction. Suppose now $Q\mid P\,,\, \deg(Q)=s\le d$ and the senior coefficient of $Q$ is $1.$ Let $z_1,z_2,\dots,z_s$ are the roots of $Q$ . The magnitude of all of them is less than $2.$ Using the Vieta formulas, we see that the coefficients of $Q$ are less than some expression that depends only on $d.$ Since these coefficients are integers, the options for $Q$ are finitely many, they are bounded by some constant that depends only on $d,$ but not on $n.$

Proof of Claim 3. The probability that a binary polynomial is a multiple of a fixed polynomial is small.

Let $Q$ be a fixed polynomial of integer coefficients and suppose $Q\mid P, P\in P_n.$ Let $\xi$ be a root of $Q.$ It follows $P(\xi)=0.$ Note that $\xi\neq 0,$ that’s why $a_0=1$ in the definition of $P_n.$ Take the set $S={xi^i: i=1,2,\dots,n}$ . Let us first consider the case when $|S|=n$ , i.e. $\xi$ is not a root of unity. The equality

$\displaystyle -1=\sum_{i=1}^{n} a_i\xi^i, a_i\in\{0,1\}$

just means that the sum of elements of some subset of $S$ is $-1$

Lemma 1. Let $S$ be a set of $n$ distinct complex numbers and $r\in\mathbb{C}.$ The probability that the sum of the elements of a random subset of $S$ is $r$ is less than $\displaystyle \frac{2}{n+1}$ .

Proof. I considered and proved this claim in a blog post, see [1]. Call a subset of $S$ bad if the sum of its elements is $r.$ As usual, a subset of $S$ can be represented as a binary vector $\{0,1\}^n$ each bit indicates if an element is in the set or not. The idea is simple. For any binary vector $b$ that corresponds to a bad subset we consider the unit sphere (by Hamming distance) centered at $b$ , that is, the set of all binary vectors that differ from $b$ at exactly one bit. Their number is $n.$ Non of them is a bad binary vector. That is, each bad binary vector is surrounded by $n$ good ones. A bit care is needed to ensure that the unit spheres corresponding to distinct bad vectors do not intersect – see in [1]. So, the estimate follows. $\square$

Claim 3 follows from Lemma 1 if $|S|=n.$ It remains to consider the case when $S$ is a multiset. Note that $0\notin S$ since $\xi\neq 0.$ Let $k$ be he the smallest number with $\xi^k=1$ . We have a multiset $S$ with $k$ groups, each one consists of (almost) $n/k$ equal values. If $k$ is large (e.g. $k>\sqrt{n}$ ), we can do the same trick as in Lemma 1 (flipping the bit of the first element of each group – we can number them) and obtain that the probability of taking a bad binary vector is less than $\displaystyle \frac{2}{k+1}\le \frac{2}{\sqrt n}$ .

In case $k$ is small ( $k<\sqrt n$ ), we take the group $G$ with the largest number of elements, say $m, m\ge n/k$ . Take a bad binary vector $b$ and let the number of chosen elements that are in $G$ is $s$ . Since all the elements in $G$ are the same (they have the same value), every binary vector with the same bits as $b$ outside $G$ , and such that the number of 1’s bits corresponding to the elements of $G$ is different from $s$ is not bad. So, the portion of the bad vectors for any fixed binary values corresponding to elements outside $G$ is at most

$\displaystyle \frac{\binom{m}{s}}{2^{m}} \le \frac{C}{\sqrt m}$ .

where $C$ is a constant. Therefore, the probability of taking a bad binary vector is less than $\displaystyle \frac{C}{\sqrt m}\le \frac{C}{\sqrt[4]{n}}$

This means that for a fixed polynomial $Q$ , the probability of randomly taken $P\in P_n$ is multiple of $Q$ is $O(n^{-1/4}),$ so it tends to zero as $n\to\infty.$

Comment

This solution has several crucial moments. The most difficult part (in my opinion) is to see that the probability of a binary polynomial $P$ be multiple of $Q^2$ where $Q$ is an integer polynomial of some large degree, is small (it’s $o(1)$ ). It involves a reduction modulo $2$ . The second part is to see that there are only finitely many polynomials with small degrees that can divide some binary polynomial $P.$ To see this we bound their coefficients. This is not hard to see, but it’s meaningful only if you got the first idea. In the third place comes the idea that for any fixed $Q$ , the portion of the binary polynomials multiple of $Q$ tends to $0$ as $n\to \infty$ . I would say that it’s doable in real time, but only if you get to that point.

References.
[1] Hamming distance in Olympiad problems. Part 2.
[2] Squarefree values of polynomials all of whose coefficients are 0 and 1, M. Filaseta, S. Konyagin, Acta Arith., 74(3): 191-205, 1996
[3] A polynomial with coefficients +/-1 very likely to be irreducible. RMM 2020 Shortlist.
[4] AoPS thread on this problem

A Special Discrete Harmonic Function. Part 2.

This is a continuation of the previous post – see [1]. I’ll show a more elegant way that will allow us to find all solutions to the functional equation we considered, but it requires a tool called the Krein – Milman theorem. The outline of this post is to first recall the problem, then Krein – Milman theorem and the intuitive motivation behind it. We will finally apply it.

Problem (China MO). Let $\displaystyle f:\mathbb{Z}_{\ge 0}\times \mathbb{Z}_{\ge 0}\to \mathbb{R}_{\ge 0}$ be a function satisfying

$\displaystyle f(x,y)=f(x+1,y)+f(x,y+1)\,;\, f(0,0)=1$

Prove that

$\displaystyle \big(f(x,0)\big)^2\le f(2x,0), \forall x\in\mathbb{Z}{\ge 0}.$

In the previous post – see [1] – we proved it using finite differences and making some estimates.

Krein – Milman Theorem.

Let $K$ be a convex set inside some real vector space $X$ . We say $x_0\in K$ is an extreme point (also called a corner point) of $K$ if it does not lie in the interior of any line segment between two points of $K$ . In figure 1 below, we have a convex quadrilateral $K=ABCD$ whose extreme points are the vertices $A,B,C,D$ (in red). All the other points of $K$ are not extreme points, because we can construct a segment lying in $K$ that contains in its interior any other point of $K$ except the red corners.

Roughly speaking, Krein-Milman theorem says that any convex set $K$ is the convex hull of its extreme points. Here is the precise statement.

Krein-Milman Theorem. Let $X$ be a locally convex topological vector space and $K\subset X$ is a compact convex set. Then $K$ is the closed convex hull of its extreme points.

So, the theorem is applicable when $X$ is some abstract space, say a space of certain functions. This theorem is intuitively “obvious” when $X$ is the two or three-dimensional Euclidean space (see figure 1). In this case the claim was proved by Minkowski (1911). It was then extended to the $n$ -dimensional space. When dealing with final dimensional vector spaces we do not need the word “closed “(convex hull) so then $K$ is simply the convex hull of its extreme points. In the general case, proved by Mark Krein and David Milman in 1940, it’s essential to take the closure of the convex hull. There are counterexamples showing a compact convex set such that the convex hull of its extreme points is not closed. We proceed with a proof of the original problem as an application of the Krein-Milman theorem.

A Solution.

Let us calibrate the function $f$ by setting $g(x,y):=2^{x+y}f(x,y)$ so that the new function satisfies

$\displaystyle g(x,y)=\frac{g(x+1,y)+g(x,y+1)}{2}, \forall x,y\in\mathbb{Z}_{\ge 0}$

$\displaystyle g(x,y)\ge 0, \forall x,y\in\mathbb{Z}_{\ge 0}\text{ and } g(0,0)=1 \qquad(1).$

Denote by $Y$ the vector space of all real valued functions on the lattice $\displaystyle \mathbb{Z}_{\ge 0}\times \mathbb{Z}_{\ge 0}.$ Note that by $(1)$ it follows $0\le g(0,1)\le 2$ and $0\le g(1,0)\le 2$ and by induction we get

$0\le g(x,y)\le 2^{x+y}\qquad (2).$

Let us denote by $X$ the subspace of all functions in $Y$ that satisfies $(1).$ Thus, $(2)$ holds for each fixed lattice point $(x,y)$ and any $g\in X.$ Also, it easily follows that $X$ is closed with respect to the Tychonoff’s (product) topology on $X.$ Hence, $X$ is a compact subset of $Y.$ Let us determine the extreme points of $X.$ Asume that $g_0\in X$ is such point. Denote $a_1:=g_0(1,0), a_2:=g_0(0,1).$ Suppose for example $a_1=0.$ In this case it straightforward follows $g_0(x,y)=0, \forall x\ge 1$ and $g_0(0,y)=2^y, y=1,2,\dots.$ Assuming $a_2=0$ implies $g_0(x,y)=0, \forall y\ge 1$ and $g_0(x,0)=2^x, x=1,2,\dots.$ It can be checked that these two functions are indeed extreme points of $X.$ Suppose now $a_1,a_2>0$ and consider the functions

$\displaystyle g_1(x,y):=\frac{1}{a_1}\cdot g_0(x+1,y)\,;\, g_2(x,y):=\frac{1}{a_2}\cdot g_0(x,y+1)\qquad(3).$

It is a routine calculation to check that $g_1, g_2$ satisfy $(1),$ thus $g_1,g_2\in X.$ Observe that $g_0(0,0)=(a_1+a_2)/2,$ so $a_1+a_2=2.$ Further,

$\displaystyle \frac{a_1}{2}g_1(x,y)+\frac{a_2}{2}g_2(x,y)=\frac{g_0(x+1,y)+g_0(x,y+1)}{2}=g_0(x,y)$

which means

$\displaystyle g_0=\frac{a_1}{2}g_1+\frac{a_2}{2}g_2.$

But $\frac{a_1}{2}+\frac{a_2}{2}=1,$ so $g_0$ lies on the segment $[g_1,g_2].$ Therefore $g_0$ is an extreme point of $X$ only if $g_1\equiv g_2\equiv g_0.$ Assuming so, $(3)$ easily yields

$\displaystyle g_0(x,y)=a_1^x a_2^y.$

Thus, if $g_0(x,y)$ is an extreme point of $X,$ it must satisfy the above equality for some $a_1,a_2\ge 0$ with $a_1+a_2=2.$ Let us denote by $X_0\subset X$ the set of these functions. They are indeed extreme points, but we don’t need to prove it for our purpose. What we need is that

$\displaystyle X=\overline{\mathrm{Conv}(X_0)}.$

Now, back to the original question. Proving $\displaystyle \big(f(x,0)\big)^2\le f(2x,0), \forall x\in\mathbb{Z}_{\ge 0}$ is equivalent to proving

$\displaystyle \big(g(x,0)\big)^2\le g(2x,0), \forall x\in\mathbb{Z}_{\ge 0}.$

It is enough to check it only for convex combinations of elements in $X_0.$ Let $g_i\in X_0, i=1,2,\dots k$ and $g_i(x,y)=a_i^x b_i^y$ where $a_i,b_i\ge 0, a_i+b_i=2.$ We just need to check

$\displaystyle \left(\sum_{i=1}^k \lambda_ia_i^x\right)^2\le \sum_{i=1}^k \lambda_ia_i^{2x}$

for any $\lambda_i\ge 0, \lambda_1+\lambda_2+\dots \lambda_k=1.$ This immediately follows from Cauchy-Schwartz inequality applied to $A_i:=\sqrt{\lambda_i}, B_i:=\sqrt{\lambda_i}\cdot a_i^x, i=1,2,\dots,k.$

References.
[1] A special discrete harmonic function.
[2] Kind of Harmonic function. USA TST, 2018. Part I.
[3] Kind of Harmonic function. USA TST, 2018. Part II.
[4] Krein – Milman theorem (Wikipedia page)

A Special Discrete Harmonic Function.

A year or two ago I saw an interesting problem. The main point was to prove an estimate for a function that has a kind of mean value property – it’s defined on the 2-dimensional lattice grid and its value at each lattice point equals the average of its values on some neighboring knots. It had no solution, just a vague hint. I think it’s still unsolved in AoPS forum, but unfortunately, I lost the link and I lack patience to search that site. It was given at some Chinese Olympiad or some selection test, not sure. It is a tough problem, although the statement is just one short sentence, and it seems very easy at first glance. I discussed it with the Bulgarian team on the last year’s IMO camp, one can download the entire lecture from [1].
There are two reasons why I decided to make a separate post. This is an excellent exercise on finite differences and some analytical technique. Also, no need to type it, I had already written it. But the main reason that I came back to this thing was my intention to give a lecture to my students about the applications of the Krein – Milman theorem in Olympiad Math. I recalled this problem and thought it would be great if it could be done using Krein – Milman. As it turns out, it’s possible and it will be our next blog post. Let me show you the hard way first. Here is the statement.

Problem (China MO). Let $\displaystyle f:\mathbb{Z}_{\ge 0}\times \mathbb{Z}_{\ge 0}\to \mathbb{R}_{\ge 0}$ be a function satisfying

$\displaystyle f(x,y)=f(x+1,y)+f(x,y+1)\,;\, f(0,0)=1$

Prove that

$\displaystyle \big(f(x,0)\big)^2\le f(2x,0), \forall x\in\mathbb{Z}{\ge 0}.$

Clearly $0\le f(x,y)\le 1, \forall x,y\in \mathbb{Z}_{\ge 0}.$ Let us fix a positive integer $n.$ Applying $n$ times the given recursive formula, starting from $atex f(0,0)$ we get

$\displaystyle 1=f(0,0)=\sum_{i=0}^n \binom{n}{i}f(n-i,i).\qquad(1)$

Let us denote

$\displaystyle \Delta^i f(x,y) := \sum_{j=0}^i (-1)^{n-j} \binom{i}{j}f(x+j,y).$

This is exactly $i$ -th finite difference with step $1$ along the $x$ axes, taken at the point $(x,y).$ We have

$\displaystyle f(n-i,i)=f(n-i,i-1)-f(n-i+1,i-1)$

$\displaystyle =\big(f(n-i,i-2)-f(n-i+1,i-2)\big)- \big(f(n-i+1,i-2)-f(n-i+2,i-2) \big)$

$\displaystyle =f(n-i,i-2)-2f(n-i+1,i-2)+f(n-i+2,i-2)$

$\displaystyle =\Delta^2 f(n-i,i-2).$

Proceeding in the same way, it can be obtaned by induction that

$\displaystyle f(n-i,i)=(-1)^i\Delta^i f(n-i,0).\qquad (2).$

Pluging it into $(1)$ yields

$\displaystyle f(0,0)=\sum_{i=0}^n \binom{n}{i} (-1)^{n-i}\Delta^{n-i} f(i,0).\qquad(3)$

In the same way we get

$\displaystyle f(k,0)= \sum_{i=k}^n \binom{n-k}{i-k} (-1)^{n-i}\Delta^{n-i}f(i,0)$

$\displaystyle =\sum_{i=k}^n \frac{i(i-1)\cdots (i-k+1)}{n(n-1)\cdots (n-k+1)} \binom{n}{i}(-1)^{n-i}\Delta^{n-i}f(i,0).$

Clearly

$\displaystyle \left(\frac{i-k+1}{n-k+1}\right)^k \le \frac{i(i-1)\cdots (i-k+1)}{n(n-1)\cdots (n-k+1)} \le \left(\frac{i}{n} \right)^k. \qquad(4)$

Let us denote

$\displaystyle g(k,n):= \sum_{i=k}^n \left(\frac{i}{n} \right)^k\binom{n}{i}(-1)^{n-i} \Delta^{n-i}f(i,0).$

Having in mind $(4)$ it follows

$\displaystyle |f(k,0)-g(k,n)|\le \sum_{i=k}^n \left|\left(\frac{i}{n}\right)^k -\left(\frac{i-k+1}{n-k+1}\right)^k\right|\binom{n}{i}(-1)^{n-i}\Delta^{n-i}f(i,0)$

We used $(-1)^{n-i}\Delta^{n-i}f(i,0)\ge 0,$ which folows from $(2)$ . Therefore,

$\displaystyle |f(k,0)-g(k,n)|\le \max_{i,k\le i\le n}\left|\left(\frac{i}{n}\right)^k -\left(\frac{i-k+1}{n-k+1}\right)^k\right|\cdot \sum_{i=k}^n \binom{n}{i}(-1)^{n-i}\Delta^{n-i}f(i,0)$

Observe that due to $(3),$ the sum in the right hand side of the above inequality is $1$ . This gives

$\displaystyle |f(k,0)-g(k,n)| \le \max_{i,k\le i\le n}\left|\left(\frac{i}{n}\right)^k -\left(\frac{i-k+1}{n-k+1}\right)^k\right|.$

Note that

$\displaystyle \lim_{n\to\infty} \,\max_{i,k\le i\le n}\left|\left(\frac{i}{n}\right)^k -\left(\frac{i-k+1}{n-k+1}\right)^k\right|=0.$

Thus,

$\displaystyle f(k,0)=\lim_{n\to\infty} \sum_{i=k}^n \left(\frac{i}{n} \right)^k \binom{n}{i} (-1)^{n-i}\Delta^{n-i}f(i,0)$

$\displaystyle = \lim_{n\to\infty} \sum_{i=0}^n \left(\frac{i}{n} \right)^k \binom{n}{i} (-1)^{n-i}\Delta^{n-i}f(i,0) \qquad(5).$

Denote

$\displaystyle A_i:=\binom{n}{i}(-1)^{n-i}\Delta^{n-i}(i,0).$

Using the Cauchy-Schwartz inequality, $(3)$ and $(5)$ , we obtain

$\displaystyle f(k,0)^2 = \lim_{n\to\infty} \left( \sum_{i=0}^n \left(\frac{i}{n}\right)^k A_i^{1/2} A_i^{1/2}\right)^2$

$\displaystyle \le \lim_{n\to\infty} \sum_{i=0}^n \left(\frac{i}{n}\right)^{2k}\binom{n}{i}(-1)^{n-i}\Delta^{n-i}f(i,0)\cdot \lim_{n\to\infty}\sum_{i=0}^n \binom{n}{i}(-1)^{n-i}\Delta^{n-i}(i,0).$

$\displaystyle = f(2k,0) f(0,0)=f(2k,0)$

Finally, we get $\displaystyle f(k,0)^2\le f(2k,0).$

References.
[1] Finite differences, etc. – IMO 2023 Bulgarian training camp.
[2] Kind of Harmonic function. USA TST, 2018. Part I.
[3] Kind of Harmonic function. USA TST, 2018. Part II.

A Family of Subsets. Combinatorial Nullstellensatz, Part 3.

I didn’t expect that Combinatorial Nullstellensatz theorem could be applied to many Math Olympiad problems. In two recent post we discussed some of its applications – see [1], [2]. Yesterday I saw (see [3] ) a solution to a nice problem that used this method. It was given at the Kürschák Math competition, 2019. Here is the statement

Problem (Kürschák MO, 2019, p2). Find all families $\mathcal{F}$ of subsets of $[n],$ such that for any nonempty subset $X\subseteq [n]$ , exactly half of the elements $A\in \mathcal{F}$ satisfy that $|A\cap X|$ is even.

I give here two solutions to this problem, which I borrowed from [3]. The first one uses double counting, the second is based on Nullstellensatz.

1-st solution.

As expected, the only possible families are the trivial ones, the empty family and the family of all subsets of $[n].$ The idea is to balance the number of even and odd values of $|A\cap X|$ for all possible pairs $A\in \mathcal F, X\subset [n].$ It’s useful to introduce a notation that indicates whether $|A\cap X|$ is even or not ( $P$ stands for “parity”)

$P(A\cap X):= \begin{cases} 1 &\text{ if } |A\cap X| \text{ is even}\\ -1 &\text{ otherwise}\end{cases}$

We assume that $|\emptyset| =0,$ thus $P(\emptyset)=1.$ Consider now the following sum

$\displaystyle S:= \sum_{A\in \mathcal{F}\,,\, X\subset [n]}\, P(A\cap X)$

Let’s calculate $S$ in two ways – first fixing $A$ and summing over all $X \subset [n]$ , and then fixing $X$ and summing over all $A\in\mathcal{F}.$ Note that if $A\neq \emptyset$ then

$\displaystyle \sum_{X\subset [n]} P(A\cap X)= 0$

since there are equal number of subsets of $A$ with even resp. odd elements. In case $A=\emptyset$ this sum is equal to $2^{n}.$

Suppose now, $\mathcal{F}$ is not empty. Calculating $S$ in the following way

$\displaystyle S= \sum_{A\in \mathcal{F}} \sum_{X\subset [n]} P(A\cap X).$

it follows that $S=0$ in case $\emptyset \notin \mathcal{F}$ and $S=2^n$ otherwise.

Now we calculate $S$ in the following way

$\displaystyle S= \sum_{X\subset [n]}\sum_{A\in \mathcal{F}} P(A\cap X).$

If $X\neq \emptyset,$ the internal sum equals $0$ because of the given condition. In case $X$ is empty, the internal sum is equal to $|\mathcal{F}|.$ Hence, $S=|\mathcal{F}|.$ Since $\mathcal F$ is not empty, we get $|\mathcal{F}|=2^n,$ thus $\mathcal F$ consists of all subsets of $[n].$ Therefore there are only two possibilities for $\mathcal F$ – either it consists of all subsets of $[n]$ or it is empty.

2-nd solution

The idea is similar to the above, but we use the Combinatorial Nullstellensatz theorem to make the conclusion. Let us interpret a set $X\subset [n]$ as a binary vector $(x_1,x_2,\dots,x_n)$ such that $x_i=1$ if $i\in X$ and $x_i=0$ otherwise. Suppose that $\mathcal F$ is non-empty. Note that for any non empty $A\in \mathcal F$ and a binary vector $x=(x_1,x_2,\dots,x_n)$ that represents a subset $X\subset [n],$ the following expression

$\displaystyle \prod_{i\in A}(1-2x_i)$

is equal to $1$ if $|A\cap X|$ is even and $-1$ otherwise. Let us consider the polynomial

$\displaystyle g(x_1,x_2,\dots,x_n):= \sum_{A\in \mathcal F} \prod_{i\in A}(1-2x_i)\qquad (1).$

Due to the given condition, $g(x)=0$ for every binary vector $x=(x_1,x_2,\dots,x_n)$ except $x=(0,0,\dots,0).$ For this value we have

$\displaystyle g(0,0,\dots,0)=|\mathcal F|.$

Now, we take the polynomial

$\displaystyle f(x_1,\dots,x_n):= |\mathcal F|\prod_{i=1}^n(1-x_i)-g(x_1,\dots,x_n) \qquad (2).$

Observe that $f(x)$ is zero for every binary vector $x.$ Assume first that $[n]\notin \mathcal F.$ Then the monomial $x_1\cdot x_2\cdots x_n$ is present only in the first product in the right hand side of $(2)$ and its coefficient is $(-1)^n|\mathcal F|,$ i.e. it’s non-zero. By Combinatorial Nullstellensatz, there exists a binary vector $x,$ such that $f(x)\neq 0,$ conradiction.
Assume now, $[n]\in\mathcal F.$ Then the coefficient in front of $x_1\cdot x_2\cdots x_n$ in $g$ is $(-2)^n.$ So, the coefficient of this monomial in $f$ is equal to $(-1)^n |\mathcal F|-(-1)^n2^n.$ If this value is not zero, we get the same contradiction. Therefore $|\mathcal F|=2^n$ and $\mathcal F$ consists of all subsets of $[n].$

References.
[1] Combinatorial Nullstellensatz, Part 1
[2] Combinatorial Nullstellensatz, Part 2.
[3] AoPS thread on this problem. (posts #2 and #10)

The unexpected equilateral triangle

The problem we are about to comment on was published 15 years ago in Crux Mathematicorum magazine and not long after appeared as Problem 2 in Romania TST 3, 2009. Equilateral triangles have the property of appearing where we least expect them … remember Morley’s trisector theorem. We will deal with exactly this situation. A significant problem, and it’s useful and pleasant to revisit it.

Problem. Prove that the circumcircle of a triangle contains exactly 3 points whose Simson lines are tangent to the triangle’s Euler circle and these points are the vertices of an equilateral triangle.

Let $ABC$ be a triangle with circumcircle $k(O)$ and $P\in \widehat{AB}$ be a point such that its Simson line $s_P$ touches the Euler circle $k_9(O_9)$ . Note that the center $O_9$ of the Euler circle of $ABC$ is the midpoint of the segment $OH$ ( $H$ is the orthocenter of $ABC$ ). On the other hand, it is well known that the intersection point $M=k_9\cap s_P$ is the midpoint of $PH$ .

Thus $O_9M$ is a midsegment in $OPH$ . Tre radius $O_9M$ is perpendicular t0 the tangent line $s_P$ and it follows that $OP$ is perpendicular t0 $s_P$ . So we get that the point $P$ bisects the arc $\widehat{XY}$ that the line $s_P$ cuts from the circle $k$ .

In fact, the equality $\widehat{XP}= \widehat{PY}$ easily follows from the homothety $h(H,2):k_9\to k$ .

It remains to do some angle chasing in the case $\alpha\geqq \beta\geqq \gamma.$

An useful fact about Simson line is that $\varphi=\angle(AB,s_P)=\angle PCO$ (notice that $\angle XDP=90^\circ-\varphi=\angle CPB$ and $\angle COP=2\angle CBP=180^\circ-2\varphi$ ).

Using this fact we get

$\widehat{AP}=\widehat{PC}-\widehat{AC}=180^\circ-2\varphi-2\beta$ and $\widehat{PB}=180^\circ+2\varphi-2\alpha$ .

Since $\widehat{XP}=\widehat{YP}$ it follows that

$0=\widehat{XP}-\widehat{YP}=\widehat{AP}-\widehat{PB}-(\widehat{AX}+\widehat{BY})=2\alpha-2\beta-4\varphi-2\varphi$ ,

which means that $\displaystyle \varphi=\frac{\alpha-\beta}3$ .

This result shows that on each of the arcs on which the vertices of the triangle divide the circumscribed circle, there is a point whose Simson line touches the Euler circle. Let $P_1,P_2,P_3$ be these points and $s_1,s_2,s_3$ be their Simson lines.

Since $\displaystyle\angle (AB, s_1)=\frac{\alpha-\beta}3$ and $\displaystyle\angle(BC,s_2)=\frac{\beta-\gamma}3$ , we get

$\displaystyle\angle (s_1,s_2)=\beta +\frac{\alpha-\beta}3-\frac{\beta-\gamma}3=60^\circ$

This means that the triangle formed by the intersection of the Simson lines $s_1,s_2,s_3$ is equilateral. But triangle formed by the intersection of the Simson lines of any three points is similar to the triangle with vertices at these points. This completes the proof.