F8 Комбинаторная геометрия

Почему F8 — третий метод после E14 и F1

По таблице F8 имеет 22 основные задачи и 29 задач с учётом дополнительных тегов. Он встречается в 11 годах из 16, причём часто на региональном и заключительном этапах. Это значит, что F8 — не «развлекательная геометрия», а один из главных способов отличить сильного ученика.

F8 почти всегда смешивается с идеями E14, E1, E9, E11:

• E14: найти максимум/минимум и построить пример;
• E1: перебор и прямой подсчёт;
• E9: выбрать крайний объект;
• E11: раскраски и разрезания.

Главная мысль: в F8 фигура — это не только геометрия. Это набор объектов, которые надо правильно посчитать.

Реальные ориентиры из таблицы

В базе есть такие реальные сюжеты F8:

Часть реальных условий требует рисунка или полного оригинального текста. Поэтому в курсе нужно разделять:

• чистые тренировочные задачи;
• реальные OCR-фрагменты как «ориентиры»;
• полные реальные задачи только после ручной сверки с оригинальным условием.

• Теорема Радона: любые $d+2$ точки в $\mathbb{R}^d$ можно разбить на два непересекающихся множества, выпуклые оболочки которых имеют общую точку. *Для плоскости ($d=2$$):*$ любые 4 точки можно разбить на два множества с пересекающимися выпуклыми оболочками.

• Теорема Хелли (для плоскости): если имеется конечный набор выпуклых фигур на плоскости, и каждые три из них имеют общую точку, то все фигуры имеют общую точку. Применение: доказательство существования точки покрытия.

• Теорема Эрдёша–Сегеди (о числе прямых): $n$ точек, не все коллинеарные, определяют не менее $n$ прямых (теорема Силвестра–Галлая: среди них есть прямая, содержащая ровно две точки множества).

• Принцип Дирихле (в геометрии): если $n+1$ объект размещён в $n$ областях, в какой-то области не менее двух объектов. Применение: если $5$ точек в треугольнике со стороной $1$, то найдутся две на расстоянии $\leq 1/2$ (делим треугольник на 4 маленьких).

• Число диагоналей выпуклого $n$-угольника: $\binom{n}{2} - n = \frac{n(n-3)}{2}$. Число треугольников из $n$ точек общего положения: $\binom{n}{3}$.

• Разбить область на «клетки» и применить принцип Дирихле: для задач «докажите, что найдутся две точки на расстоянии $\leq d$» — разбей область на части диаметра $\leq d$ и примени принцип.

• Подсчитать число объектов двумя способами (двойной подсчёт): для задач «сколько пересечений?», «сколько общих точек?» — считай сначала по строкам, затем по столбцам.

• Рассматривать выпуклую оболочку: найди вершины выпуклой оболочки; точки внутри имеют другие свойства, чем граничные.

• Использовать экстремальный принцип: рассмотри самую левую, самую высокую, самую удалённую точку — она часто имеет особые свойства (например, лежит на выпуклой оболочке).

• Строить граф на точках и применять теоремы теории графов: соедини точки рёбрами по условию (например, «пара точек на расстоянии $\leq 1$») и подсчитай степени, компоненты связности.

• Применять инверсию или проективные преобразования для задач с инцидентностью (точки на прямых, прямые через точки).

• Разбить $n$ точек на подмножества и применить индукцию: добавляй точки по одной и отслеживай изменение числа объектов (диагоналей, треугольников).

Поверхностные признаки (что буквально написано):
- «$n$ точек на плоскости, никакие три не коллинеарны».
- «Докажите, что можно покрыть...» или «каково минимальное число фигур, покрывающих...».
- «Среди $n$ точек найдутся $k$ точек, образующих выпуклый многоугольник».
- «Каково наибольшее/наименьшее число...».

Структурные признаки (форма выражения, объекты):
- Условие содержит счётное количество точек, прямых, многоугольников — и вопрос о числе или существовании.
- В задаче есть конечное множество объектов, и нужно что-то доказать о нём как целом (не об одном конкретном объекте).
- Задача содержит ограничение «не более $k$ точек на прямой» или «точки в общем положении».

Цель задачи (что от тебя хотят):
- Доказать, что некоторые $k$ точек образуют выпуклый $k$-угольник.
- Найти максимальное число «хороших» конфигураций.
- Покрыть фигуру минимальным числом частей или доказать, что покрытие невозможно меньшим числом.

Задача 1 (подтип: точки общего положения). Монохроматический треугольник

Условие: Каждую из $6$ точек в общем положении (никакие три не коллинеарны) окрасили в красный или синий цвет. Докажите, что среди всех $\binom{6}{3} = 20$ треугольников найдётся монохроматический (все три вершины одного цвета).

Источник: Классическая задача (теорема Рамсея $R(3,3)=6$), Турнир городов

Как думать (рассуждение ученика):
1. 6 точек, 2 цвета. Это задача на принцип Дирихле / теорему Рамсея. Метод: рассмотрю одну точку $A$. Из неё идут рёбра к остальным 5 точкам.
2. По принципу Дирихле: 5 рёбер, 2 цвета → хотя бы $\lceil 5/2 \rceil = 3$ ребра одного цвета (скажем, красного). Пусть $AB$, $AC$, $AD$ — красные.
3. Рассмотрю треугольник $BCD$. Если хотя бы одно ребро $BC$, $CD$, $BD$ — красное (скажем, $BC$) — то $ABC$ — красный треугольник. Готово!
4. Если все рёбра $BC$, $CD$, $BD$ — синие, то $BCD$ — синий треугольник. Тоже готово!
5. В обоих случаях монохроматический треугольник найден.

Решение:
Возьмём произвольную точку $A$. Из 5 рёбер $AB$, $AC$, $AD$, $AE$, $AF$ по принципу Дирихле хотя бы 3 имеют одинаковый цвет. Не умаляя общности, $AB$, $AC$, $AD$ — красные.

Рассмотрим три ребра $BC$, $CD$, $BD$:
- Если хотя бы одно, скажем $BC$, красное: $\triangle ABC$ — красный монохроматический.
- Если все $BC$, $CD$, $BD$ — синие: $\triangle BCD$ — синий монохроматический.

В обоих случаях монохроматический треугольник существует. $\square$

Ответ: Монохроматический треугольник всегда найдётся.

Что в этой задаче было главным: ключ — рассмотреть одну вершину, применить принцип Дирихле к 5 рёбрам, а затем к оставшемуся треугольнику снова применить ту же идею.

Задача 2 (подтип: выпуклые оболочки и принцип Дирихле). Точки в квадрате

Условие: В квадрате со стороной $1$ расположены $5$ точек. Докажите, что найдутся две точки на расстоянии не больше $\frac{\sqrt{2}}{2}$.

Источник: Классическая задача (ВсОШ, принцип Дирихле в геометрии)

Как думать (рассуждение ученика):
1. 5 точек в квадрате. Нужно найти две близкие точки. Это типичный принцип Дирихле: нужно разбить квадрат на 4 части, в каждой из которых диаметр $\leq \frac{\sqrt{2}}{2}$.
2. Делю квадрат на 4 маленьких квадрата со стороной $\frac{1}{2}$. Диаметр каждого = $\frac{\sqrt{2}}{2}$ (длина диагонали).
3. 5 точек в 4 клетках → по принципу Дирихле в одной клетке $\geq 2$ точки. Расстояние между любыми двумя точками в этой клетке $\leq \frac{\sqrt{2}}{2}$.

Решение:
Разобьём квадрат на $4$ маленьких квадрата со стороной $\frac{1}{2}$ (горизонтальным и вертикальным разрезом посередине). Диаметр каждого маленького квадрата (наибольшее расстояние между точками) равен длине его диагонали: $\frac{1}{2}\sqrt{2} = \frac{\sqrt{2}}{2}$.

По принципу Дирихле: 5 точек в 4 клетках $\Rightarrow$ в одной клетке не менее 2 точек. Расстояние между ними $\leq \frac{\sqrt{2}}{2}$.

Ответ: Расстояние $\leq \frac{\sqrt{2}}{2}$ (доказано).

Что в этой задаче было главным: правильный выбор разбиения (4 клетки для 5 точек, диаметр клетки = ответу) — это сердце задачи; остальное тривиально.

• Ошибка: неверно выбирать разбиение в принципе Дирихле (число клеток не на единицу меньше числа точек). → Почему неверно: нужно ровно $n$ клеток для $n+1$ точки, иначе оценка не работает. → Как избежать: всегда проверяй: «клеток = число точек минус один».

• Ошибка: при подсчёте числа объектов забывать граничные случаи (например, точки на границе клетки принадлежат двум клеткам сразу). → Почему неверно: точка на границе может быть в любой из смежных клеток; принцип Дирихле всё равно работает, но нужно аккуратно формулировать. → Как избежать: договорись, что граничные точки принадлежат конкретной клетке (например, нижней или левой).

• Ошибка: считать, что «выпуклая оболочка» — это просто контур всех точек. → Почему неверно: выпуклая оболочка — строго определённый минимальный выпуклый многоугольник; точки внутри не являются вершинами оболочки. → Как избежать: явно определяй, какие точки «на оболочке», а какие «внутри», и используй это разбиение.

• Ошибка: применять принцип Дирихле, не проверив, что диаметр клетки действительно равен нужному значению. → Почему неверно: если диаметр клетки больше искомого расстояния, оценка слабее. → Как избежать: явно вычисляй диаметр каждой клетки как максимальное расстояние между её точками.

• Ошибка: в задачах Рамсея не использовать принцип Дирихле на рёбрах, а перебирать все случаи руками. → Почему неверно: перебор занимает много времени и легко допустить ошибку. → Как избежать: стандартная техника — зафиксируй одну точку, примени Дирихле к её рёбрам, потом к оставшемуся треугольнику.