A problem given at a 2022 Bulgarian tournament will be commented on. As I learnt, it was given also in a similar Russian tournament. The idea used is instructive and we finish the arguments using the probabilistic method.

Problem. A graph with vertices is given, and of its edges are colored red so that each triangle has at most one red edge. The maximum number of vertices in that induce a bipartite graph equals Prove that

Solution. Let be the vertices of and be the number of red edges incident with the vertex Denote by the set of vertices connected to through red edges. Apparently

The main observation. Any two vertices in are not connected, that is, each is an independent set. Indeed, if some two vertices in are connected we obtain a triangle with two red edges, which is ruled out.

The fancy statement about the maximum induced bipartite graph is just equivalent to show that there exist two independent vertex sets with

Plausible candidates of these independent sets are Thus, it’s enough to prove that there exist with

It’s quite intuitive. Indeed, since we have

So, if there exists one independent set with half of the required elements, there will most likely be two of them with twice the number of elements!? At this point it’s tempting to forget about the fact that these sets are related to the structure of the graph and prove it for any sets. Unfortunately, it’s not true for arbitrary sets. But fortunately, some of the sets do not intersect with each other.

The second observation. If and are connected then Indeed, if there exists we would get a triangle with two red edges, and

We prove even something stronger. The condition holds for some vertices connected with a red edge. Take randomly a red edge and number its two ends randomly as 1st and 2nd. Let be a random variable that equals the number of red edges incident with the 1st end and – a random variable equal to the number of red edges incident with the 2nd end. Since the number of all red edges is and there are two possibilities to enumerate the ends of each one, we obtain.

The same holds for the expectation of hence by linearity of expectation,

By AM-QM inequality and we get

This means that there exists a red edge connecting vertices and for which holds.

Connected graphs, cut-vertices, -connected graphs, … these notions are part of the variety of problems given at Math Olympiads. I plan to shed some light on these topics – definitions and core theory needed. A problem given at the 2022 Korea winter program practice test will be solved as an application of the theory.

Definitions and useful facts.

Definition. A graph is connected (or 1-connected) if for any two of its vertices there is a path that connects them. Any graph can be split into connected subgraphs (components) , such that there is no edge between and A graph is –connected () if removing any of its vertices leaves graphs still connected. Here we consider only 2-connected graphs, i.e. removing any vertes of the graph leaves it still connected.

Some useful facts. Assume a graph is 2-connected. Then for any two of its vertices, there is a cycle that passes through them. And vise versa, if a graph has that property it is 2-connected. On this base, there is a simple construction that enables us to obtain any 2-connected graph. Start from a cycle and at every step add to the already constructed graph a path where and are different vertices in and are new vertices (the set of which may be empty – in this case we add just an edge that connects two existing vertices of ). Proofs of those facts can be seen in [1] (chapter 3.1). The handout in [2] contains some applications on this topic (and many others). The last claim is useful when we have to prove something about a 2-connected graph and want to induct on the number of edges. As said, any graphs is a union of its connected components. As a parallel, any connected graph is a structure that includes (in a sense) its 2-connected components.

Definition. A vertex of a connected graph is called a cut-vertex (or articulation point) if deleteing makes the graph disconnected. Two examples on the picture below – the red vertices are cut-vertices. The red edge on the second graph is called a bridge – upon removal of an edge like that the graph becomes disconnected.

Definition. A maximal 2-connected subgraph of a connected graph is called a block.

Look again on fig.1. The first graph has two blocks that are connected via the red cut-vertex. The second graph has three blocks – the bridge with its two ends is also a block. Intuitively, any connected graph can be viewed as its blocks that overlap at its cut-vertices. Moreover, this structure resembles a tree, as we will see. The next figure (fig.2) shows a graph, its blocks and its cut-vertices – the red dots.

Let us replace each block with a large white dot, and connect each cut-vertex (red points) to every block it belongs to. The result is illustrated on fig.3.

Claim. The resulting graph is a tree. It’s called the block tree of the initial graph. The proof is short, and also can be found in [1]. Keep in mind that each cut-vertex is part of the blocks it’s adjacent to in the block tree (red points on fig. 3). I think the mentioned theory is enough to proceed to the next section.

2022 Korea winter test problem.

Problem (2022 Korea winter test). Let be a positive integer and be a set of airports. For two arbitrary airports , if there is an airway from to , then there is an airway from to . Suppose that has only one independent set of airports. Prove that there exists an airport which satisfies following condition. Condition : For each two distinct airports , if there exists a path connecting and , then there exists a path connecting and which does not pass through .

So, in another words, we have a simple graph and is the only independent set with vertices. We have to prove there exists which is not a cut-vertex. Let be all connected components of . There is at least one with . We denote and be the graph induced by . Then is the only independent set with vertices in . Further we work only with . The plan is to prove via induction on the number of blocks of the following claim. It involves a certain amount of casework, but it unfolds naturally.

Claim. Let be a connected graph with an unique independent set of vertices, and . Then there exists a vertex which is not a cut-vertex.

Proof. Note first that if is an unique independent set with some number of elements, it must be the maximum independent set. Induction on the number of blocks of . In case contains only one block, that is, is 2-connected, then all of its vertices are not cut-vertices. Suppose now, has multiple blocks. Let be a block that is a leaf of the block tree – see figure 3. If consists of at least 3 vertices, then there are two of them that are not cut-vertices and are connected, see fig.4.

They cannot be both in , and we are done. Let now consists of less than 3 vertices. This means is a bridge – on figure 5.

In case we are done, so assume Then Further, suppose is also connected to the blocks in the blocks tree. We remove the vertices and and get a graph which consists of connected components , each one contains respectively the blocks . Each of the graphs has unique maximum independent set, denote it by and . There are two possible cases. Either there exists a graph satisfying or Further we consider each of these cases.

1-st case. There is a graph, say that satisfies

If is connected to at least two of the other vertices of the block we apply the induction hypothesis to and are done, since removing a vertex from that does not break will also not break Assume, is connected to only one vertex, say in – fig.6

This means is a bridge consisting of . If we are done again, applying the induction hypothesis to . Assume If is connected to more than one block in we can apply again the induction with respect to and get a point taht can be removed leaving still connected. That point cannot be , because it would disconnect So, in this case we are done again. Suppose, finally is connected to only one block, say (apart from ). Note that upon removing from the resulting graph again satisfies the hypothesis of the claim. In case is connected to more than one vertex in we are done again, for the same reasons. This means should be again a bridge, that is, is connected to only one vertex but this time must be in , because otherwise we can increase the maximu independent set in by adding to (). Therefore, by applying the induction to we get the needed vertex.

2-nd case. All the graphs satisfy the conditions of our claim. In this case, the picture is something like on figure 7.

As explained above (fig. 6), if one of vertices belongs to we are done. Assume all these vertices are not in . But, in this case we can remove from and put in its place the vertex thus getting another independent set with the same number of elements. It means this case is impossible.

To recap. In any possible case we either used the induction hypothesis or found the needed vertex explicitly.

I was delighted to be invited to give a lecture at our National team camp for the 2022 International Math Olympiad. I was told it had to be on Graph Theory and I was absolutely free to include whatever I wanted. That’s how the paper linked below came about – I wanted to give the students something written besides the lecture and exercises that I did. I checked a lot of problems from IMO’s, Shortlists, NMO’s, etc., most of which I have solved on the AoPS forum or commented on on this blog over a period of time. The needed theory was also included. I spent time on wording and style, but not much. Thus, some of it might be raw, so please, inform me if there are some typos or issues. The handout is intended for students who already have basic knowledge on Graph Theory. Most of the examples included are from prestigious math competitions or their shortlist.

In some recent posts we commented on two problems of this year’s International Math Olympiad (see [1] and [2]). Both are excellent, with fresh ideas. I like the trend of the problems chosen in recent IMOs – they are not pure combinatorics or number theory, algebra, etc., they have elements from different subjects. It favors creative thinking, instead of applying well known techniques. The problem, I am going to present, is a wonderful example illustrating this fact. The statement is about a certain graph constructed on the primes as its vertices. It has two parts, the number theory part helps to establish two important properties of the graph. The rest is pure combinatorics.

Problem (IMO 2022, problem 3). Let be a positive integer and let be a finite set of odd prime numbers. Prove that there is at most one way (up to rotation and reflection) to place the elements of around the circle such that the product of any two neighbors is of the form for some positive integer .

A quick comment first. The claim is also true if the condition the primes being odd is omitted. It’s given just for convenience. In fact, we will not use this hypothesis, at least not explicitly. Indeed, is even, so if is odd and then must be odd. If is even than is even which means one of them is and in this case the elements of cannot be disposed around a circle in the desired way.

So, translated into graph theory language it looks like: We have an (infinite) graph with vertices all odd prime numbers. Two vertices and are connected if and only if there exists a positive integer such that We want to prove that any finite subgraph of contains at most one Hamiltonian cycle.

This is a very strong claim for a graph, its structure should not be so complicated. For instance, it holds if every vertex of has a degree at most . We can try it as a first idea, though unfortunately this is not true. Trying to prove the degrees are 2 or less, we, of course, are doomed, but we could establish that it’s “almost” true. Each vertex is connected with at most two other vertices less than . Here, by “less” we mean the natural order of the primes. This is the easier part – there are only two properties of we need, this is the first one.

Lemma 1. Each vertex (prime number) is connected with at most two primes less than .

Proof. Suppose, a prime is connected to two primes with . Then there exist two positive integers such that

Subtracting the two equalities, we get

Since is the biggest one among by we obtain thus cannot divide , hence it divides but therefore I think, almost every contestant has discovered this fact. One step further lies the observation that cannot be connected to another prime (apart from ) that is less than . Indeed, if is a prime and the same argument yields therefore and

What we have established till now is that is (so called) two-degenerate graph. A graph is two-degenerate if its vertices can be enumerated as such that is connected to at most two vertices among . Unfortunately, this property is not enough to prove the uniqueness of Hamiltonian cycles. Bellow is a picture that presents a two degenerate graph with two Hamiltonian cycles.

Indeed, the vertices can be ordered like it’s shown: 1,2,3,4,5, and every next vertex is connected with at most two of the previous ones. However, there are two Hamiltonian cycles: 1,2,3,5,4,1 and 1,3,5,4,2,1.

The second property of is harder to establish though there are some hints. (I didn’t go further then the two-degenerate property). Look at the fig.1 again. The moment breaches the uniqueness-of-Hamiltonian-cycle property is the moment we add the vertex . Assume, instead of connecting to and , we connect it to and

This graph still has a unique Hamiltonian cycle. Indeed, the vertex 5, as the last one, has degree , so if there are two Hamiltonian cycles, both of them pass through like and since and are connected, there are also two Hamiltonian cycles in the induced subgraph on . Which is false. The same argument can be used (as shown later) to establish Hamiltonian uniqueness in case every time we add a vertex and it’s connected to two of the previous ones, these two vertices are also connected. At this moment one may say – wait, what if we connect the vertices 3 and 4 on fig. 1? We still get two Hamiltonian cycles!? The point is, if we do so, the graph would not be two-degenerate any more.

The graph induced on 1,2,3,4 is not two-degenerate graph. It can’t be, since all its vertices have degree 3 and the last one added will be connected to three of the previous vertices. The next claim is the toughest NT part of this problem and is the key property satisfies. I have read in some forums that the problem was not difficult, etc. Had the next sentence was given as a hint it would have been easy indeed. Because, if you know what to prove, it’s straightforward at that level. The point is that it’s not that intuitive.

Lemma 2. Let be a prime number, connected to and Then and are also connected.

Proof. Let . As we showed and

It implies . Let us set where Further,

Hence, and let Multiplying the equalities in we get

Putting back in we obtain

Thus, we showed where . Here, we have a “small” issue since it may happen . If one trace back what and were, one can it’s mostly the case. Fortunately, if we can represent as where we can represent it also as .

But, we have still an issue! What if or . That is, what we proved is that is representable as where . It’s slightly annoying since and are connected if and only if is representable as and We cannot do anything, but to change the statement of the problem. Allow the vertices be connected even if It cannot change anything, since if we prove the claim for a graph obtained by adding a few more edges, it will be also true for the original graph. That said, let’s recap. We proved the graph has the following two properties.

(i) The vertices of can be ordered such that is connected with at most two among the vertices and

(ii) If is connected to and then and are also connected.

This is enough to prove that there does not exist a subgraph of with two distinct Hamiltonian cycles. The argument is simple. Suppose there is a subgraph like that and let the vertex be the first one so that appears after adding it. That is, there is no subgraph like that in the graph induced by but there is one, say , in the graph induced by Apparently, since it’s the first time appears. It also means is connected to exactly two vertices and . So, we have at least two Hamiltonian cycles in and both pass trough like . Since and are connected, by (ii) it yields there are also two Hamiltonian cycles in contradiction.

The problem I am going to present was on the IMO 2021 shortlist, but it was not chosen as IMO problem, which is sad. This is a briliant problem, because it seams so easy, so easy, untill a moment later you realize it’s not! I intend to present a solution to a slightly easier version of this problem and then reduce the original one to it.

Problem 1 (C5, IMO 2021 SL). Let and be two integers with . There are students standing in a circle. Each student has neighbors – namely, the students closest to on the left, and the students closest to on the right. Suppose that of the students are girls, and the other are boys. Prove that there is a girl with at least girls among her neighbors.

So, let’s put on each girl’s position and on the boys’ positions. Thus, we have and ‘s placed on the circle with a positive sum, and want to locate a number equal to $+1$ such that the sum of all its neighbors up to the -th position to the left and right and the number itself is positive. One may think: what if we take only the neighbors on the left (or right). Let’s discuss this problem first.

Problem 2. We have numbers or written on a circle with positive total sum. Prove that there exists a number equal to such that the sum of all its neighbors on the left and the number itself is positive.

Proof. Enumerate the numbers anti-clockwise as Consider the sequence of their partial sums

where we assume Suppose, seeking contradiction, that the claim is not true. It means that for any we have , that is, Let’s focus on the behavier of the sequence . At each next step, this sequence may jump one unit up, stay the same or decrease one unit. It converges to since We also know that the following property holds

(i) For any whenever jumps up one unit (that’s, when ) we have

The point is that (i) rules out the possibility Indeed, if this were the case, then for any positive integer larger than there is a moment such that for the first time. But the property (i) prevents this to happen. This leads to contradiction, hence we established the claim of Problem 2.

Let’s now go back to the original Problem 1. As done above, place and instead of boy respectively girl. Denote the given numbers as and let where means . Note that can take values and . By Problem 2 there exists such that is positive. This means two things. First, must be which means . Second, is at least and then . We are done.

Do you remember problem 3 of IMO 2017? A wonderful problem! I glanced again on the results of that year and still cannot understand why they were so disastrous! The knowledge needed to solve it is just the Pythagoras theorem or an entry level of trigonometry. So, it was not about technique. Absolutely everyone at that level can make those calculations, and still only 1 student had something like 5 points. I am notified every time a guy posts a solution on AoPS thread, and sometimes I take a glance. Most of them are like: “â€¦the best strategy of the hunter is bla-bla, so he cannot discern whether the rabbit is here or thereâ€¦” and then a bunch of calculations follows that shows something could increase. The emphasize is always on the calculations! I dare say had the same problem was formulated in another way it could have been completely solved by at least 75% of the contestants. Just changing the wording could make the difference! But, this is a story for another post (maybe the next one). Oh, that problem was a gem!

There is another problem on 2021 IMO’s shortlist worded for a hunter and a rabbit. It was listed as C6 but I think, it would have been solved by many students if it had been chosen as IMO 2021 problem. This problem is more of a technique than any out-of-the-box idea. Let us recall the statement.

Problem (IMO 2022 SL,C6). A hunter and an invisible rabbit play a game on an infinite square grid. First, the hunter fixes coloring of the cells with finitely many colors. The rabbit then secretly chooses a cell to start in. Every minute, the rabbit reports the color of its current cell, and then secretly moves to an adjacent cell that is not visited before (two cells are adjacent if they share a side). The hunter wins after some finite time either

the rabbit cannot move; or

the hunter can determine the cell in which the rabbit started.

Decide whether there exists a winning strategy for the hunter.

Solution.

The hunter can color the cells in a way that enables him to guess the starting point of the rabbit, providing the rabbit does not end up in a dead end. We consider the colors as consisting of some layers, i.e. any color will be viewed as a tuple where each variable (layer) can take a finite number of colors. Each layer has a purpose. The first one is for orientation – to know the directions of each move the rabbit makes (up,down,right, left). The second layer will ensure there are no two paths with identical sequence of colors that start from different cells within a fixed frame around the origin. The third layer is to give us the information about the region (frame) within which the rabbit starts. This structure of colors is only for convenience, clearly this configuration can be encoded with one dimensional colors. The first layer takes values and its purpose is to control the direction of the rabbit. We put these values on each row starting as and on the next row starting from , on the next one – from , then from and so on. This coloring allows us to translate the sequence of colors into directions, say, up, left, down, down, right, etc. So, if we know the starting cell, this layer helps us to recover rabbit’s trajectory. It also means that two equal sequences of the first layer color correspond to trajectories such that one of them can be obtained by translating the other with the vector determined by their starting points. The second layer of colors will allow the hunter to locate the starting position of the rabbit, providing he knows the rabbit started in a fixed frame. The second layer will consist of only two colors. Suppose the hunter knows the approximate location the rabbits started from, i.e. he knows that the rabbit started in a cell inside some (big) square (frame), say centered at the origin. Suppose all the cells inside a bigger square (also centered at the origin) have their second layer already colored. We claim that the hunter can consecutively color the second layer of each cell in a bigger square in a way that there are not two paths starting from different cells in and leaving that have the same sequence of colors. Let us fix two cells and be the vector . For any cell outside , but having a common side with we consider the cells . They cannot be both in (then q’ would have been inside since is convex). So, in case one of them is outside , say , and is inside this square, we set the second layer of to differ the second layer of , and the second layer of be thae same as that of that is, we color them alternatively. If both are outside we also color the second layers of alternatively. We do this procedure for all outside but with a common side with . Suppose now, there exists two paths, say, that start from and respectively, and with the same sequences of colors. Suppose, is the first cell that one of them hits outside the frame . At this moment the other path hits one of the cells . But, we took care and have different second layer color. Thus, there are no paths starting from and respectively, that leave and have the same sequence of colors. Further, we color somehow the second layer of those cells that have a common side with and are still uncolored, and proceed with some other pair of cells and with one unit bigger than frame which we again denote as In the end, we expand the coloring to a frame and are sure that there are no two paths that start inside leave and have the same sequence of colors.

It remains to invent some sign that would show us the approximate location the rabbit started from. That’s the third layer that comes to help. This layer consists of three colors, say, white, black and neutral. Place a strip, two cells wide, symmetrical to the origin, and color the third layer of its inner cells white and its outer cells black. Thus, we will know if the rabbit starts within this strip – it will cross the border as white, black pattern. Now, we set infinitely many concentric strips like that of rapidly increasing sizes. It’s enough to ensure that the shortest path between two consecutive strips is longer than the longest path between the previous strips. We color the third layer of all other cells neutrally. In this way, examining the sequence ot the third layer’s color, we can determine the frame from which the rabbit started.

So, the number of needed colors is . But looking closely to the third layer one may see that in order to determine the frame the rabbit starts in, we actually only need strips one cell wide, colored, say, white, and all the other cells colored neutrally. Hence we can decrease the number of total colors to .

The previous post, commented on problem 2 of IMO 2022 – a non standard nice functional equation. A graph theory approach was used although it served only for a visualization and convenience. Here, we will comment on Problem 6, which is clearly a graph theory problem. Thanks to Aleksandar Ivanov, some ideas came up in the discussion we had. We will see that all simple graphs that allow a minimum number of up-paths, are exactly the graphs whose vertices can be partitioned into two parts and such that is an independent set and the graph induced by is a tree. Let us first recall the problem.

Problem (IMO 2022, problem 6). Let be a positive integer. A Nordic square is an board containing all the integers from to so that each cell contains exactly one number. Two different cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a valley. An uphill path is a sequence of one or more cells such that:

(i) the first cell in the sequence is a valley,

(ii) each subsequent cell in the sequence is adjacent to the previous cell, and

(iii) the numbers written in the cells in the sequence are in increasing order.

Find, as a function of , the smallest possible total number of uphill paths in a Nordic square. (Nikola PetroviÄ‡)

Consider the graph whose vertex set consists of all the cell of the board. Any two of them are connected only if they have a common side. We are allowed to choose the direction on each edge in in such a way that becomes an acyclic directed graph. We call a vertex a root (a valley) if there are only out-edges incident with . We call a directed path that starts from a root, a up-path. The question asks for the minimum number of distinct up-paths.

Lower bound. Fix a directed edge and start walking downward until reach a root. It is not possible to fall into a cycle because the graph is acyclic. Thus, we found a up-path which last edge is . Hence, the number of up-paths that consist of at least an edge is at least the number of edges . Further, there is at least one root, and so, an up-path that consists of only a vertex. Therefore the number of up-paths are at least . This is true for any simple graph.

An example and attempt to generalize it.

It is the harder part of the job. Let’s first analyze what directions we have to introduce, so that the number of up-paths equals to the minimum possible, i.e. . Suppose we can make a configuration like that. There must be only one root, otherwise the up-paths would be more than needed. Further, starting from that root and following the directions, there do not exist two paths from the root to the same vertex, unless this vertex has only in-bounded edges. Let be the set of all those vertices with only in-bounded edges. If we remove , (and the incident edges) the remaining graph is a directed tree. Moreover, must be independent set of vertices, because it’s impossible an edge between two vertices of to exists. The conclusion is: The graph (the undirected one) admits a decomposition into a tree and a set of independent vertices. On the other hand, if we can do this, we can direct edges as needed. Indeed, take a root of and direct its edges from this root to the leaves. Next, direct the edges, that connect and , from to .

That’s, we can characterize all simple graphs that allow example of exactly up-paths. They are exactly those graphs whose vertices can be partitioned into two parts and such that is an independent set and the graph induced by is a tree.

So, the question is: can we characterize graphs like that in a simpler way. For example, not all simple graphs can be partitioned into a tree and independent set. Note that the original graph is bipartite. I am convinced that there are bipartite graphs that cannot be decomposed like that. So, apparently, we cannot generalize the problem for, say, all graphs, or bipartite graphs. If one tries to find a greedy algorithm that consecutively puts vertices into or one can notice that there is a big chance -degenerate graphs to allow partitioning like that.

Definition. We call a simple graph –degenerate if its vertices can be ordered such that every vertex has at most two neighbors among

Still, I have obstacles to prove any 2-degenerate graph has the needed partition. Most probably, this is not true. But, if we impose a further restrictions, it will be true. Consider a graph whose vertices can be ordered as with the following properties.

For each the vertex has only one neighbour among the previous ones

For each all neighbours of among the previous vertices are either all among or they are at most two, and one of them is among

If a simple graph satisfies and then a greedy algorithm can partitioned it into a tree and an independent vertex-set. We put the first vertices into the set . It is indeed a tree so far. For any next vertex , if it is connected (up to this moment) to only vertices among we put into . Otherwise, is connected to at most two previous vertices and one of them is in . If the other one (if any) is also in we put in . If the other one is in or does not exist, we put into . Clearly, is still a tree and – still independent set.

This year’s International Mathematical Olympiad has ended. The results are known, and I am happy that the Bulgarian team was 16th and won 5 medals and a honorable mention – 1 gold, 3 silver and a bronze. Congratulations to the entire team and their leaders. Let me first comment on a nice functional equation from this Olympiad, it was problem 2. It’s not like the routine ones – like, you have a function that satisfies an equality on a certain domain. Here, you have a function that satisfies a certain constraint, and that constraint is more interesting than an equality. Therefore, it needs a fresh ideas, not just putting values back and forth, hoping to find some values and unravel the case. Of course, there is no need to involve any graph theory in this problem, but it helped me visualize the situation more clearly, so I decided to keep the graph theory language in the explanation that follows.

Problem (IMO 2022, Problem 2). Let denote the set of positive real numbers. Find all functions such that for each , there is exactly one satisfying

Before presenting a solution, let me remark that the requirements of the statement can be weakened keeping the same result. It’s enough to impose that for each , there is at least one, but at most countably many satisfying the inequality. The result will be the same – see at the end of the post.

Solution. Let us denote . Consider a graph with vertices and edges defined as iff . It may happen be connected to , so the graph may contain loops. The imposed requirements imply , that is, we have a perfect matching (with the convention that a matching to is allowed). For convenience, for any edge we write .

Claim. Let be the subset of edges defined as

Then is at most countable.

Proof. In order to prove the claim it is enough to prove that the set

is at most countable for any . Assume on the contrary is uncountable. Consider a subset of defined as

.

This is an uncountable subset of , hence there is a point such that in each neighborhood of there are infinitely many points of . Note that For each of these points either or , so without lost of generality we can assume each neighborhood of contains infinitely many points of with For any we have

Since is a continuous function on the variables there exists a neighbourhood of such that

It means that taking any and we get

Thus, and which means both and are edges in which is contradiction, since we can take .

So, we have proven there are at most countably many with . It means on a set that contains all but countably many positive reals. Further,

yields Therefore, for all but countably many edges we have

where we used AM-GM inequality. Taking into account , there must be equality everywhere in the chain of , hence for all but countably many . Thus,

where is at most countable. Since is everywhere dense in it easily follows holds for all

Remarks

As said, we can weaken the requirement and ask for each to exist at most countably many that satisfy the inequality. The only function that complies with this condition will be still In this case, the edges incident with any vertex of the graph we constructed, are countably many. claim we proved. The claim, we proved still holds, but its proof needs to be changed a bit. Namely, there exists such that in each neighborhood of there are uncountable many points of . The rest is the same.

In the previous blog post, we considered a general idea that is applicable in combinatorics. In particular, a hard problem from 2007 Bulgarian Olympiad was solved. Here, the same method will be applied to a problem from IMO 2021 shortlist. Consider permutations of . One can think of them as functions and define a distance between two permutations as the maximum pointwise distance between their values. The question is: How many permutation we can choose, such that the distance between any two of them is at least ?

Problem (SL 2021, C8). Determine the largest for which exists a table of integers of rows and columns that has the following property:

(i) Every row contains the numbers in some order.

(ii) For any two distinct rows and there is a column such that (here means the number at the intersection of the row and the column )

Solution.

Look on each row as a function which has an additional property of being a permutation. Let be the family of all possible functions (permutations) like that. For any two we can define a non negative number , call it the distance between them as

This distance satisfies all the properties of being a “distance” as for instance the triangle inequality, etc. Denote by the unit ball centered at , i.e.

Upper bound. Let be a collection of the given functions that satisfies (ii). It means that So, the unit ball centered at any does not contain any other point (function) in . Let’s now fix and see what kind of functions consists of. Take into account that consists of only permutations. We are interested of the values of , see the picture.

Any can be obtained from applying a composition with which is a permutation and satisfies.

That is,

It’s easy to see that all permutations like that can be obtained by choosing some consecutive disjoint pairs and “swap” their values () and keeping fixed the non paired numbers.

Knowing what the structure of is, back to the main point. A greedy algorithm of obtaining is to start with a function , and at -th step to take that is outside . The main difficulty in this approach is that two balls can have common points and it’s difficult to put some bounds on the maximum number of functions we can construct with this procedure. Fortunately, each ball contains a subset, call it a “kernel”, and all those kernels are disjoint! Let’s partition the numbers from 1 to 100 into 50 pairs and be the subset of those permutations which act on each pair either as swapping or leaving it intact. Thus,

is a subset of and the following claim holds

Claim. For any we have .

Proof. suppose . Then which yields

and since it follows , contradiction.

Now, suppose are functions/permutations with . It means are disjoint and since each of them consists of elements we get

hence

A construction. It remains to show we construct a set of permutations like that. First, we consider the family of all partitions of the numbers into 50 sets of two elements. The number of these partitions is Indeed, the number can be paired with 99 other numbers, then the least number among the remaining ones can be paired with of the others, and so on. Further, we want to take into account the order of those 50 pairs by permuting them, that is, we want to put these two element sets in a row. In this way, we obtain of those objects. It remains to order each set like or and each object will become a permutation The ordering of the pairs will be constructed inductively on the size of the permutations. In our case . For it can be made straightforward and checked that the distance between any two of the obtained permutations is at least . Suppose now for some we can order the pairs in any partition of into sets of two elements, so that the distance between any two of the obtained permutations, obtained by permuting those pairings, is at least . Moreover, we assume all the two element sets are ordered as . Further, suppose the set is paired somehow and is paired with . We order as , then map the remaining numbers to conserving the order. At this point, we order the the remaining pairs the way it can be done for a pairing of . Finally, we reverse their order. Let’s see that for any two of the permutations, we just constructed, it holds . Assume and are pairs in and respectively. We first consider the case these two pairs are not at the same positions in and respectively. In this case should be at the same position in as the pair in , otherwise and we are done. But the pair in is ordered as (we reversed the order in our inductive construction). Thus, in this case we certainly have . So, assume in is at the same position as in . If we are done, and in case the inductive hypothesis yields again . Let now . We remove the two pairs and from and respectively, thus obtaining new functions – that map to some values. The values of are and those of are Let and be the corresponding to functions which values are so that is obtained from by lifting the values one unit up and is obtained from by lifting the values by one unit up. We know, by the induction hypothesis, that and let be the position where . Since and are consecutive integers, either both values will be raised one unit up, or the greater value among will be raised up. In both cases , which means . This completes the induction step.