IMC 2022, Day 1, Problem 4
Let be an integer. Let be the set of all triples of distinct elements of . Let denote the minimal number of colours which suffice to colour so that whenever , the triples and have different colours. Prove that
Original from the official PDF

This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
(proposed by Danila Cherkashin, St. Petersburg)
Hint: Define two graphs, one on and another graph on pairs (2-element sets).
Solution. For denote by the set of all -subsets of . For each define a directed graph whose vertices are elements of , and edges correspond to elements of as follows: if , then the edge of corresponding to goes from to .
For a directed graph we call a subset admissible, if does not contain a directed path of length 2. Define b-index of the as the minimal number of admissible sets which cover . As usual, a subset is called independent, if there are no edges with both endpoints in ; a chromatic number of is defined as the minimal number of independent sets which cover .
A straightforward but crucial observation is the following
Lemma. For all a subset is independent in if and only if it is admissible as a set of edges of .
Corollary. for all .
Now the bounds for numbers follow by induction using the following general
Lemma. For a directed graph we have
Proof. 1) Denote and prove that . For this we take a covering of by admissible subsets and define a color of a vertex as the following subset of : . Note that for any edge there exists such that which yields and , therefore . So, each color class is an independent set and we get as needed.
- Denote and prove that . Take a proper coloring (that means that for all edges ). For an integer take a binary representation , , where . Consider the following subsets of , two subsets and for each :
Each of them is admissible, and they cover , thus .
Note that , thus . Actually we have : indeed, if we define for all , then the above sets cover all edges of .
The Lemma above now yields for our number the following bounds, which are better than required:
Remark. Actually the upper bound in the Lemma may be improved to that yields .
Transcribed from the official solutions, page 4. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.