Maths Olympiad Prep

Library / /10 of 13

Combinatorics Difficulty 6.5 National olympiad Find the answer

There are n>2022n > 2022 cities in the country. Some pairs of cities are connected with straight two-ways airlines. Call the set of the cities {\it unlucky}, if it is impossible to color the airlines between them in two colors without monochromatic triangle (i.e. three cities AA, BB, CC with the airlines ABAB, ACAC and BCBC of the same color).

The set containing all the cities is unlucky. Is there always an unlucky set containing exactly 2022 cities?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To address the given problem, we start by interpreting the key terms and constraints involved. The problem describes a set of cities with airlines (edges) connecting them, which can be considered as a graph where cities are vertices and airlines are edges. We need to determine whether there exists a subset of exactly 2022 cities (vertices) for which it is impossible to two-color the connecting airlines (edges) without forming a monochromatic triangle.

### Step 1: Understanding the Ramsey Number Concept

The core mathematical concept involved here is related to Ramsey theory. In Ramsey theory, the Ramsey number R(k,l) R(k, l) is defined as the minimum number of vertices n n such that any graph of n n vertices, when its edges are colored with two colors, will contain a monochromatic complete subgraph with k k vertices in one color or l l vertices in the other color.

Specifically, R(3,3) R(3, 3) is the smallest number of vertices required to ensure any two-coloring of the edges results in a monochromatic triangle. From known results:

R(3,3)=6. R(3, 3) = 6.

This implies that any set of 6 vertices in a graph will always contain a monochromatic triangle if the edges are colored with two colors.

### Step 2: Applying the Ramsey Number to the Given Problem

We are asked if there is always a subset of exactly 2022 cities such that it is impossible to color the airlines between them in two colors without a monochromatic triangle.

To investigate this, consider a subset of 5 cities. The Ramsey number tells us it is possible to color the airlines between 5 cities in two colors without forming a monochromatic triangle. Thus, for any subset of cities with fewer than 6 vertices, a two-coloring exists where no monochromatic triangles are formed.

### Conclusion

Given that R(3,3)=6 R(3, 3) = 6 , there can be a complete graph or any subset with more than 5 vertices forming an "unlucky" set due to the two-coloring condition. However, for exactly 2022 cities, it is not guaranteed they will always form an unlucky set because the presence of a monochromatic triangle is contingent upon the exact structure and coloring.

Hence, the answer to whether there is always an unlucky set containing exactly 2022 cities is:

No \boxed{\text{No}}

There might exist colorings and configurations that avoid a monochromatic triangle among exactly 2022 cities, hence not every arrangement of 2022 cities results in an unlucky set.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.