Olympiad Maths Prep

Library / /2 of 3

Combinatorics Difficulty 5.0 AIME, harder Prove it Greece

Given are 50 points in the plane, no three of them belonging to a same line. Each of these points is colored using one of four given colors. Prove that there is a color and at least 130 scalene triangles with vertices of that color.

Solution

Since 50=412+250 = 4 \cdot 12 + 2, according to the pigeonhole principle we will have at least 13 points colored in the same color. Using these 13 points we construct (133)=286\binom{13}{3} = 286 different triangles, since there are no three collinear points.

We will prove that there are at most 1213=15612 \cdot 13 = 156 isosceles triangles. In fact, there are (132)=78\binom{13}{2} = 78 different line segments. Each of them can be the basis at most two different isosceles triangles (because there are not three collinear points). Therefore there are at most (132)2=782=156\binom{13}{2} \cdot 2 = 78 \cdot 2 = 156 isosceles triangles. Thus we can construct at least 286156=130286 - 156 = 130 scalene triangles.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.