Competition problem — Combinatorics

Library / /447 of 520

Combinatorics Difficulty 5.8 AIME, harder Prove it

3. Given $n+1$ points $X_{0}, X_{1}, \cdots, X_{n}$ $(n \geqslant 2)$ in the plane. Prove: In $\triangle X_{0} X_{i} X_{j}(1 \leqslant i<j \leqslant n)$ , the number of triangles with area 1 is less than or equal to $\frac{9}{8} n \sqrt{n}$ .

Solution

Construct a graph $G$ with vertices $X_{1}, X_{2}, \cdots, X_{n}$ , where $X_{i} X_{j}$ is an edge of $G$ if and only if the area of $\triangle X_{0} X_{i} X_{j}$ is 1. It is easy to verify that graph $G$ does not contain $K_{2,5}$ .
Therefore, using Theorem 2, the number of edges in graph $G$ does not exceed
$\frac{n}{4}(1+\sqrt{16 n-15}) \leqslant \frac{9}{8} n \sqrt{n} .$

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.