MathDB
Research flavoured combi

Source: IMC 2022 Day 1 Problem 4

August 5, 2022
logarithmscombinatoricsSetsgraph colouringcollege contestsIMC 2022

Problem Statement

Let n>3n > 3 be an integer. Let Ω\Omega be the set of all triples of distinct elements of {1,2,…,n}\{1, 2, \ldots , n\}. Let mm denote the minimal number of colours which suffice to colour Ω\Omega so that whenever 1≤a<b<c<d≤n1\leq a<b<c<d \leq n, the triples {a,b,c}\{a,b,c\} and {b,c,d}\{b,c,d\} have different colours. Prove that 1100log⁡log⁡n≤m≤100log⁡log⁡n\frac{1}{100}\log\log n \leq m \leq100\log \log n.
Back to ProblemsView on AoPS