Maths Olympiad Prep

Library / /453 of 520

Combinatorics Difficulty 5.8 AIME, harder Prove it

4. Let SS be a finite set of points in the plane (the number of points is greater than or equal to 5), some of which are colored red, and the rest are colored blue. Suppose that no three or more points of the same color are collinear. Prove that there exists a triangle such that
(1) its three vertices are of the same color;
(2) this triangle has at least one edge that does not contain a point of the other color.

Solution

For any five points in SS, coloring them red or blue must result in three points of the same color (pigeonhole principle), so conclusion (1) holds. There are finitely many triangles with three vertices of the same color, and among them, there must be one with the smallest area (let it be ABC\triangle A B C). Then ABC\triangle A B C satisfies conclusion (2). If not, each side of ABC\triangle A B C would have a point of a different color, and these three different-colored points would form another triangle with three vertices of the same color, which is smaller than ABC\triangle A B C, leading to a contradiction.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.