Maths Olympiad Prep

Library / /43 of 106

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. Spacing and $ signs are ignored.

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 and solution reproduced as published; topic and difficulty added by this site.