Maths Olympiad Prep

Library / /44 of 116

Combinatorics Difficulty 8.3 Shortlist Find the answer

Consider 99 points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of  n \,n\, such that whenever exactly  n \,n\, edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Consider a configuration where you have 9 points in space, with each pair of points joined by an edge, for a total of (92)=36\binom{9}{2} = 36 edges. We want to find the smallest n n such that if exactly n n edges are colored (either blue or red), there must exist a monochromatic triangle (a triangle with all edges of the same color).

The problem is equivalent to finding the smallest number n n such that every coloring of n n edges, using two colors, necessarily forms a monochromatic triangle. This is a classic application of Ramsey Theory, specifically the problem of finding R(3,3) R(3,3) for two colors, which states the minimum number of edges needed to ensure a monochromatic triangle in a complete graph.

From Ramsey Theory, we know:
R(3,3)=6, R(3,3) = 6,
meaning that in any two-coloring of a complete graph on 6 vertices, there exists a monochromatic triangle.

Therefore, if we have a complete graph K9 K_9 , and we color n n edges without getting a monochromatic triangle, then n n must be greater than the maximum number of edges we can color without creating such a triangle.

A K5 K_5 (complete graph on 5 vertices) does not necessarily have a monochromatic triangle if less than 10 edges are colored. Thus, we need to consider larger configurations. For K9 K_9 , which has (92)=36\binom{9}{2} = 36 edges:

If we leave 3 edges uncolored, we are left with 33 colored edges. This will ensure that in K9 K_9 (when 33 edges are colored), there must necessarily exist a monochromatic triangle.

Thus, the smallest number n n such that any coloring of n n edges guarantees a monochromatic triangle is:
33 \boxed{33}

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 reproduced verbatim; metadata (topic, difficulty) added by this project.