Competition problem — Combinatorics

Library / /1 of 34

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Let $n \ge 3$ be an integer and let $K_n$ be the complete graph on $n$ vertices. Each edge of $K_n$ is colored either red, green, or blue. Let $A$ denote the number of triangles in $K_n$ with all edges of the same color, and let $B$ denote the number of triangles in $K_n$ with all edges of different colors. Prove that
$B \le 2A + \frac{n(n-1)}{3}.$

Solution

* each monochromatic triangle has a charge of +6,
* each bichromatic triangle has a charge of 0, and
* each trichromatic triangle has a charge of -3.
Since each vee contributes to exactly one triangle, we obtain that the total charge is $6A - 3B$ .

$\begin{align*} & 2 \left[ \binom{a}{2} + \binom{b}{2} + \binom{c}{2} \right] - (ab + ac + bc) \\ &= (a^2 - a + b^2 - b + c^2 - c) - (ab + ac + bc) \\ &= (a^2 + b^2 + c^2 - ab - ac - bc) - (a + b + c) \\ &= (a^2 + b^2 + c^2 - ab - ac - bc) - (n - 1) \\ &\ge -(n - 1). \end{align*}$

$6A - 3B \ge -n(n-1) \iff B \le 2A + \frac{n(n-1)}{3}$

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.