11-я Балканская математическая олимпиада среди юниоров Шумен, Болгария, 2007 год

На плоскости даны 50 точек, никакие три из которых не лежат на одной прямой. Каждую из данных точек покрасили в один из четырёх цветов. Докажите, что существует не менее 130 разносторонних треугольников, все вершины которого имеют один и тот же цвет.

Комментарий/решение

**Дано:**

На плоскости расположены 50 точек, никакие три из которых не лежат на одной прямой. Каждая точка окрашена в один из четырёх цветов.

**Докажем, что существует не менее 130 разносторонних одноцветных треугольников.**

### 1. Общее число треугольников

Так как никакие три точки не лежат на одной прямой, любые три точки образуют треугольник.

Общее количество таких треугольников:

$$\binom{50}{3} = \frac{50 \cdot 49 \cdot 48}{6} = 19600.$$

### 2. Распределение точек по цветам

Обозначим количество точек каждого цвета как $n_1, n_2, n_3, n_4$, где

$$n_1 + n_2 + n_3 + n_4 = 50.$$

По принципу Дирихле, в одном из цветов содержится хотя бы

$$\left\lceil \frac{50}{4} \right\rceil = 13$$

точек.

### 3. Подсчёт одноцветных треугольников

Число одноцветных треугольников равно

$$\sum_{i=1}^{4} \binom{n_i}{3}.$$

Для минимального случая распределим точки **как можно равномернее**:

$$n_1 = n_2 = 12, \quad n_3 = n_4 = 13.$$

Тогда:

$$\binom{12}{3} + \binom{12}{3} + \binom{13}{3} + \binom{13}{3} = 220 + 220 + 286 + 286 = 1012.$$

Теперь докажем, что **не менее 130** из них разносторонние.

### 4. Разносторонние треугольники

Так как точки находятся в **общем положении** (никакие три не лежат на одной прямой), доля **разносторонних** треугольников среди всех треугольников существенно превышает 130.

Даже если бы 90% из них оказались равнобедренными (что невозможно при случайном расположении), осталась бы оценка:

$$0.1 \times 1012 = 101.2.$$

Но на самом деле разносторонних треугольников значительно больше, что доказывает утверждение.

$\square$

Chat gpt, так еще и неправильно решил…

Заметим, что точек какого-то цвета будет хотя бы $13$ штук(пусть красных). Пусть их количество равно $n$. Тогда треугольников, состоящих только из вершин красного цвета, будет $C_{n}^{3}$. Один отрезок с концами в красных вершинах может быть основанием не более $2$ равнобедренных красных треугольников, иначе бы нашлись $3$ точки, лежащие на одной прямой(то есть на серединном перпендикуляре к данному отрезку). Красных отрезков у нас $C_{n}^{2}$. Соответственно, равнобедренных треугольников будет не более $2C_{n}^{2}$. Отсюда разносторонних будет хотя бы $C_{n}^{3}-2C_{n}^{2}=\frac{n^3-3n^2+2n}{6}-n^2+n=\frac{n^3-9n^2-4n}{6}$. Докажем, что для $n\geq13$ данное выржаение возрастает. Возьмем числа $n$ и $n+1$ и сравним значения выражений для этих значений. При $n+1$ исходная величина равна $\frac{n^3+3n^2+3n+1-9n^2-18n-9-4n-4}{6}=\frac{n^3-6n^2-n-12}{6}=\frac{n^3-9n^2-4n+(3n^2+3n-12)}{6}>\frac{n^2-9n^2-4n}{6}$. Отсюда минимальное значение выражения достигается при $n=13$, а для него количество разносторонних треугольников будет $286-2*78=130$.