М416. О максимальном количестве ребер в таком графе, что никакие три ребра не создают треугольник

Задача из журнала «Квант»(1977 №8)

Условие

На плоскости даны $n$ точек $A_{1},\ldots,A_{n}$, никакие три из которых не лежат на одной прямой. Какое наибольшее число отрезков с концами в этих точках можно провести так, чтобы не получилось ни одного треугольника с вершинами в этих точках?

Решение

Проведем максимальное число отрезков с концами в точках $A_{1},\ldots,A_{n}$. Получим некоторый граф с вершинами в этих точках. Отрезки с концами в вершинах графа будем называть ребрами графа. Оценим число ребер в нашем графе.

Назовем степенью вершины в графе число выходящих из неё ребер. Пусть $k$ — максимальная степень вершины в графе, и пусть некоторая вершина $A_{i}$ соединена с $k$ вершинами $A_{j_{1}},\ldots,A_{j_{k}}$ графа (рисунок 1).

kvant1

Тогда степень любой вершины из множества $\left \{ A_{j_{1}},\ldots,A_{j_{k}} \right \}$ не превосходит $n-k$ ($n$ — число вершин графа), поскольку любые вершины из этого множества уже не могут быть соединены ребром (в нашем графе никакие три ребра не образуют треугольника — с вершинами в вершинах графа). Так как $k$ — максимальная степень вершины в графе, степень каждой из оставшихся $n-k$ вершин не превосходит $k$. Поэтому сумма степеней всех вершин графа не превосходит $$k \left(n-k \right )+ \left (n-k \right) k=2k \left (n-k\right).$$ Но легко видеть, что сумма степеней всех вершин графа равна удвоенному количеству его ребер. Следовательно, количеств ребер графа не больше $$k\left(n-k\right)\leqslant\left(\frac{k+(n-k)}{2}\right)^{2}=\frac{n^{2}}{4}.$$ Чтобы получить данное соотношение, мы воспользовались теоремами о среднем арифметическом и среднем геометрическом. Учитывая, что количество ребер графа — число целое, мы получаем, что ребер в нашем графе не больше чем $\left [ \frac{n^{2}}{4}\right]$ (здесь $\left [ x \right]$ означает целую часть числа $x$ — наибольшее целое число, не превосходящее $x$).

Укажем теперь способ построения графа без треугольников с $n$ вершинами, число ребер которого в точности равно $\left [ \frac{n^{2}}{4}\right]$.

Разобьем множество точек $A_{1},\ldots,A_{n}$ на два: $\left [ \frac{n}{2} \right ]$ точек в одном множестве и $n — \left [ \frac{n}{2} \right ]$ — в другом. Соединив все точки точки первого множества с точками второго (как на рисунке 2, где $n=5$), мы получим граф, у которого не будет ни одного треугольника с вершинами в точках $A_{1},\ldots,A_{n}$.

kvant2

Число ребер в этом графе, очевидно, равно $\left [ \frac{n}{2} \right ]\left(n-\left [ \frac{n}{2} \right ]\right)$. Если $n$ — четное, то $$\left [ \frac{n}{2} \right ]\left (n-\left [ \frac{n}{2} \right ]\right)=\frac{n^{2}}{4}=\left [ \frac{n^{2}}{4} \right ].$$Если $n$ — нечетное, то $\left [ \frac{n}{2} \right ]\left(n-\left [ \frac{n}{2} \right ]\right)=$ $\frac{n-1}{2}\left(n-\frac{n-1}{2}\right)=$ $\frac{n^{2}-1}{4}=$ $\left [ \frac{n^{2}}{4}\right].$ Что и требовалось доказать.

Итак, ответ в задаче: максимальное число отрезков равно $\left [ \frac{n^{2}}{4}\right]$(этот результат в теории графов называют теоремой Турана).

M1635. О разбиении сторон правильного треугольника на $n$ равных отрезков.

Задача из журнала «Квант» (выпуск №2, 1998).

Условие

    Каждая сторона правильного треугольника разбита на $n$ равных отрезков, и через все точки деления проведены прямые, параллельные сторонам. Данный треугольник разбился на $n^{2}$ маленьких треугольников-клеток. Треугольники, расположенные между двумя соседними параллельными, образуют полоску.

  1. Какое наибольшее число клеток можно отметить, чтобы никакие две отмеченные клетки не принадлежали одной полоске ни по одному из трёх направлений, если $n=10$?
  2. Тот же вопрос для $n=9$.

Решение

  1. На рисунке 1 показан способ отметить 7 треугольников. Чтобы доказать, что при $n=10$ нельзя отметить 8 треугольников, разрежем исходный треугольник средними линиями на четыре треугольника. Каждый из них состоит из 25 треугольничков. Обозначим количества отмеченных треугольничков в угловых треугольниках буквами $k,l,m$, а в центральном — $n$. Тогда $k+l+n \leq 5$, поскольку два угловых треугольника вместе с центральным состоят из 5 полос. Аналогично,$l+m+n \leq 5$ и $m+k+n \leq 5$.
    Сложим эти три неравенства: $2k+2l+2m+3n \leq 15$. Следовательно, $ k+l+m+n \leq \frac{1}{2} \cdot (2\cdot k+2\cdot l+2\cdot m+3\cdot n)\leq \frac{15}{2} < 8 $.
  2. Решим задачу для произвольного $n$. Рассмотрим одну из сторон исходного треугольника и пронумеруем полоски соответствующего направления следующим образом: полоска, прилегающая к стороне, пусть будет иметь номер 1; следующая за ней — номер 2;…; полоска, состоящая из одного треугольника, примыкающего к вершине исходного большого треугольника, получит номер $n$.
    Теперь положение любого из $n^{2}$ треугольничков можно задать тройкой чисел — номеров полосок, в которых он лежит.
    Уточнение о номерах полосок показать

    Введённые нами тройки номеров = «координаты» треугольничков — не могут принимать произвольные значения. Их сумма равна $n+2$, если треугольничек расположен «остриём вверх» (т.е. ориентирован так же, как исходный большой треугольник), и равна $n+1$, если «остриём вниз».
    Предположим, отмечены $k$ треугольников, никакие два из которых не попали в одну полоску. Оценим сумму $S$ всех их координат двумя способами. С одной стороны, сумма координат любого треугольника не превышает $n+2$, поэтому $ S\leq k\cdot (n+2) $. С другой стороны, сумма значений одной из координат по всем отмеченным треугольникам не меньше чем $1+2+3+\cdots +k=\frac{k\cdot (k+1)}{2}$. Значит, $3\cdot \frac{k\cdot (k+1)}{2}\leq S\leq k\cdot (n+2)$, откуда $3\cdot \frac{k+1}{2}\leq n+2$, т.е. $k+1\leq \frac{2\cdot n+4}{3}$. Итак, $k\leq \frac{2\cdot n+1}{3}\cdots$.
    Отметить $[\frac{2\cdot n+1}{3}]$ треугольничков можно следующим образом. Рассмотрим число $m=[\frac{n+1}{3}]$. На основании исходного треугольника отметим $(m+1)-й$ слева треугольничек, расположенный остриём вверх. В этой же вертикали отметим и все остальные треугольнички, ориентированные остриём вверх (рис.2).

    Всего в этой вертикали отмечено $(m+1)$ треугольничков. На второй горизонтальной полосе большого треугольника отметим $(2\cdot m+1)-й$ (считая слева) треугольничек, расположенный остриём вверх. Отметим и все остальные треугольнички этой вертикали, ориентированные остриём вверх. Всего в этой вертикали будет отмечено $n-1-2\cdot m$ треугольничков.
    Общее количество отмеченных треугольничков есть $m+1+n-1-2\cdot m=n-m=n-[\frac{n+1}{3}]=[\frac{2\cdot n+1}{3}]$.
    Чтобы проверить последнее равенство, достаточно разобрать три случая: $n$ равно $3\cdot a, 3\cdot a+1$ и $3\cdot a+2$.