М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]$(этот результат в теории графов называют теоремой Турана).

M447. Задача об остроугольном треугольнике

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

Условие

В остроугольном треугольнике $ABC$ отрезки $BO$ и $CO$ (где $O$ — центр описанной окружности) продолжены до пересечения в точках $D$ и $E$ со сторонами $AC$ и $BC$ треугольника. Оказалось, что $\widehat{BDE}=50^{\circ}$, а $\widehat{CED}=30^{\circ}$. Найдите величины углов треугольника $ABC$ и докажите равенства $\left | AE \right |=\left | ED \right |$, $\left | CE \right |=\left | CB \right |$, $\left | CD \right |=\left | CO \right |$.

Решение

Величина угла $A$ находится легко (см. рис. 1): поскольку $\widehat{BOC}=\widehat{EOD}=180^{\circ}-30^{\circ}-50^{\circ}=100^{\circ}$, величина вписанного угла $A=50^{\circ}$. Заметим также, что $\widehat{OBC}=\widehat{OCB}=40^{\circ}$ (поскольку $\left | BO \right |=\left | CO \right |$).

Рис. 1

Рис. 1

Найти величины других углов треугольника $ABC$ можно с помощью теоремы синусов. Положим $\widehat{EBD}=\varphi $. Тогда $\widehat{OEB}=100^{\circ}-\varphi $, $\widehat{ABC}=\varphi +40^{\circ}$, $\widehat{ACB}=90^{\circ}-\varphi $, $\widehat{OCD}=50^{\circ}-\varphi $, $\widehat{ODC}=\varphi +50^{\circ}$; таким образом, $0^{\circ}< \varphi < 50^{\circ}$. Из треугольников $ODE, OBE$ и $OCD$ находим: $$\frac{\sin 50^{\circ}}{\sin 30^{\circ}}=\frac{\left | OE \right |}{\left | OD \right |}=\frac{\left | OE \right |}{\left | OB \right |}\cdot \frac{\left | OE \right |}{\left | OD \right |}=$$ $$=\frac{\sin \widehat{OBE}}{\sin \widehat{OEB}}\cdot \frac{\sin \widehat{ODC}}{\sin \widehat{OCD}}=\frac{\sin \varphi \sin \left ( \varphi +50^{\circ} \right )}{\sin \left ( 100^{\circ} -\varphi \right )\sin \left ( 50^{\circ}-\varphi \right )} .$$ Уравнение, из которого мы должны найти $\varphi \left ( 0^{\circ} < \varphi < 50^{\circ}\right )$: $$\frac{\sin \varphi \sin \left ( \varphi +50^{\circ} \right )}{\sin \left ( 100^{\circ} -\varphi \right )\sin \left ( 50^{\circ}-\varphi \right )} = 2\sin 50^{\circ},$$ эквивалентно следующим: $$2\sin 50^{\circ}\left ( \cos 50^{\circ} -\cos \left ( 150^{\circ} -2\varphi \right ) \right ) =\cos 50^{\circ}-\cos \left ( 50^{\circ}+2\varphi \right ),$$ $$\sin 20^{\circ}-\sin\left ( 2\varphi -40^{\circ} \right )+2\sin 50^{\circ}\cos \left ( 2\varphi +30^{\circ} \right )=0,$$ $$\cos \left ( \varphi -10^{\circ} \right )\sin \left ( 30^{\circ}-\varphi \right )+\sin 50^{\circ}\sin \left ( 60^{\circ}-2\varphi \right )=0,$$ $$\sin\left ( 30^{\circ} -\varphi \right )\left ( \cos \left ( \varphi -10^{\circ} \right )+2\sin 50^{\circ}\cos \left ( 30^{\circ}-\varphi \right ) \right )=0.$$ Поскольку $\cos \left ( \varphi -10^{\circ} \right )$ и $\cos \left ( \varphi -30^{\circ} \right )$ положительны при $0^{\circ}< \varphi < 50^{\circ}$, последнее уравнение имеет единственный корень $\varphi =30^{\circ}$.

Отсюда $\widehat{ABC}=70^{\circ}$, $\widehat{ACB}=60^{\circ}$/

Далее, $\widehat{BEC}=70^{\circ}\Rightarrow \left | CE \right |=\left | CB \right |;$ $$\widehat{ODC}=80^{\circ}\Rightarrow \left | CD \right |=\left | CO \right |;~\widehat{ADE}=50^{\circ}\Rightarrow \left | EA \right |=\left | ED \right |.$$

Равенства длин, которые требуется установить в задаче, подсказывают, какие углы должен иметь треугольник $ABC$. Но даже зная ответ, придумать данное выше тригонометрическое решение трудно. Вместо этого можно рассуждать иначе.

Рис. 2

Рис. 2

Заметим прежде всего, что условия $\widehat{OED}=30^{\circ}, \widehat{ODE}=50^{\circ}$ определяют ответ однозначно. Действительно (рис. 2), если на окружности с центром $O$ закрепить точки $B$ и $C$ так, что $\widehat{BOC}=100^{\circ}$, и перемещать точку $A$ по дуге ${B}'{C}’$ (симметричной дуге $BC$) от точки ${B}’$ к точке ${C}’$, то точка $D\in \left [ {B}’O \right ]$ будет приближаться к $O$, а $E\in \left [ O{C}’\right ]$ — удаляться от $O$; при этом величина угла $\widehat{ODE}$ будет возрастать, а угла $\widehat{OED}$ — убывать; значит, только при одном положении $A$ эти величины могут принять нужные значения ($50^{\circ}$ и $30^{\circ}$).

Рис. 3

Рис. 3

Теперь нужно лишь доказать, что треугольник с углами $\widehat{A}=50^{\circ}$, $\widehat{B}=70^{\circ}$, $\widehat{C}=60^{\circ}$ удовлетворяют условию, то есть что все углы — такие, как указано на рисунке 3:

  1. Достаточно проверить, что $DE$ — биссектриса угла $ADB$: $$\frac{\left | AE \right |}{\left | EB \right |}=\frac{\left | AE \right |}{\left | EC \right |}=\frac{\left | EC \right |}{\left | EB \right |}=\frac{\sin 20^{\circ}\sin 70^{\circ}}{\sin 50^{\circ}\sin 40^{\circ}}=$$ $$\frac{2\sin 20^{\circ}\cos 20^{\circ}}{2\sin 50^{\circ}\sin 40^{\circ}}=\frac{\sin 30^{\circ}}{\sin 50^{\circ}}=\frac{\left | AD \right |}{\left | DB \right |}.$$
    Здесь мы снова используем теорему синусов. А вот чисто геометрическое доказательство.
  2. Рис. 4

    Рис. 4

  3. Треугольник $ECB$ имеет ось симметрии, поскольку $\widehat{CEB}=\widehat{CBE}$. Пусть $K$ — точка, симметричная точке $O$ относительно этой оси (рис. 4). Тогда треугольник $KCD$ равносторонний ($\left | KC \right |=\left | OC \right |=\left | DC \right |=a,~\widehat{KCD}=60^{\circ}$), и потому $\left | KD \right |=a,~\widehat{DKC}=\widehat{KDC}=60^{\circ}$, а $\bigtriangleup KBE\cong \bigtriangleup OEB$, и потому $
    \widehat{BEK}=30^{\circ},~\widehat{EKB}=80^{\circ},~\left | EK \right |=\left | OB \right |=a$. Итак, треугольник $EKD$ равнобедренный, $\widehat{EKD}=40^{\circ}$, поэтому $\widehat{KED}=\widehat{KDE}=70^{\circ},$ $\widehat{ODE}=70^{\circ}- \widehat{ODK}=70^{\circ}-\left ( 80^{\circ} -60^{\circ}\right )=50^{\circ},$ $\widehat{OED}=70^{\circ}-40^{\circ}=30^{\circ}.$

Н. Васильев,
Я. Суконник

M927. Замена пересекающихся отрезков

Задача из журнала «Квант» (1985, №10)

Условие

На плоскости дано конечное множество точек, никакие три из которых не лежат на одной прямой. Проведено несколько отрезков с концами в данных точках. Эти отрезки разрешается менять: если какие-то два из них, AC и BD, пересекаются, их можно стереть и провести

  1. отрезки AB и CD
  2. AB и BC.

(Если «новый» отрезок уже проведён, проводить его второй раз не нужно.)
Можно ли после нескольких таких замен (только по правилу 1 или по правилу 2, но не по обоим) вернуться к исходному набору отрезков?

Решение

  1. Докажем, что через конечное число операций «типа 1» — замены пересекающихся AB и CD — мы придём к конфигурации, в которой уже не будет пересекающихся отрезков.

    Рассмотрим сумму s длин всех отрезков конфигурации. При каждой операции «типа 1» она уменьшается:
    AB + CD < AC + BD (*)
    (для треугольников APB и CPD, где P — точка пересечения AC и BD — рис. 1, выполнены неравенства AB < AP + PB и CD < CP + PD; сложив их, получим (*)).

    рисунок2

    С другой стороны, величина s может принимать лишь конечное число различных значений, поскольку существует лишь конечное число различных конфигураций из отрезков с вершинами в данных точках. Поэтому через конечное число шагов мы придём к конфигурации, с которой уже нельзя проделать операцию, уменьшающую s.

    Это решение даёт очень грубую верхнюю оценку для максимального количества T_n операций, которое может быть проделано с конфигурацией на n точках — можно сказать лишь что оно меньше числа всех конфигураций, то есть 2^{n\cdot(n-1)/2}, n\cdot(n-1)/2 — это число различных отрезков с концами в данных n точках.

    рис1

    Приведём идею другого решения, дающего значительно лучшую оценку. Рассмотрим произвольное разбиение f данных точек на два непустых множества, каждое из которых лежит целиком по одну сторону от некоторой прямой l. Таких прямых для данного разбиения, конечно, бесконечно много, но одну из них всегда можно получить, повернув по часовой стрелке прямую, соединяющую две какие-либо точки A и B на очень маленький угол вокруг середины отрезка AB (рис. 2); эту прямую обозначим l_i. Число прямых l_i, и значит, что число рассматриваемых «выпуклых» разбиений не превосходит числа пар точек n\cdot(n-1)/2.

    Назовём балансом конфигурации суммарное число b пересечений её отрезков со всеми прямыми l_i; ясно, что 0 \le b \le (n\cdot(n-1)/2)^2. При операции типа 1 число пересечений любой прямой l_i с отрезками конфигурации не увеличивается, а по крайней мере для одной прямой оно уменьшается на 2. Следовательно, T_n \le n^2 \cdot (n-1)^2 / 8. Интересно было бы получить ещё более точную оценку для T_n.

  2. рисунок1Приведём пример, показывающий, что для операции «типа 2» — замены пересекающихся отрезков AC и BD не имеющих общий конец AB и BC — процесс может «зациклиться» и тем самым продолжаться неограниченно. Расположим 18 точек в вершинах правильного 18-угольника и обозначим через D(k, l) конфигурацию из 36 отрезков, в которой каждая из 18 точек соединена k-й и l-й от неё по счёту.

    Чтобы пройти за 54 операции путь D(4, 8) \to D(5, 9) \to D(6, 7) \to D(4, 8) (рис. 3), достаточно каждую из операций, изображенных на рисунке 4, проделать по 18 раз (поворачивая картинку каждый раз на 20^{\circ}).

    По-видимому, существуют и примеры с существенно меньшим числом точек n и длинной цикла T, чем n = 18 и T = 54.

  3. рисунок4

    Н.Б. Васильев, В.Е. Колосов

M1626. О сумме длин отрезков в треугольнике, вписанном в окружность

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

Условие

В треугольнике $ABC$ угол $A$ является наименьшим. Точки $B$ и $C$ делят окружность, описанную около этого треугольника, на две дуги. Пусть $U$ — внутренняя точка той дуги с концами $B$ и $C$, которая не содержит точку $A$. Серединные перпендикуляры к отрезкам $AB$ и $AC$ пересекают прямую $AU$ в точках $V$ и $W$ соответственно. Прямые $BV$ и $CW$ пересекаются в точке $T$. Докажите, что $$AU = TB + TC.$$

Решение

Нетрудно доказать, что если $\angle A$ — наименьший из углов $\triangle ABC$, то точка $T$ находится внутри этого треугольника. Пусть прямые $BV$ и $CW$ пересекают окружность, описанную около $\triangle ABC$, вторично в точках $B_1$ и $C_1$ соответственно (рис. 1).

В силу симметрии относительно серединного перпендикуляра к стороне $AB$ имеем $AU = BB_1$. Аналогично, $AU = CC_1$. Следовательно, $BB_1 = CC_1$, а значит, и $TB = TC_1$ ($BCB_{1}C_{1}$ — равнобедренная трапеция). Тогда $TB + TC = TC_1 + TC = CC_1 = AU$, что и требовалось доказать.

Замечания

  1. Если $\angle A = 30 ^ \circ$, а $O$ — центр окружности, описанной около $\triangle ABC$, то $|BT — CT| = OT$.
  2. Если отказаться от требования минимальности угла $A$, то (при условии, что прямые $BV$ и $CW$ действительно пересекаются, а не параллельны) справедливо следующее утверждение: из отрезков $AU$, $TB$ и $TC$ один равен сумме двух других. Например, в ситуации, изображенной на рисунке 2, $TB = AU + TC$.

M1722. Количество целых точек

Задача из журнала «Квант»(2000, №5)

Условие

Пусть a,b — натуральные числа. Проведем через точку (a;b) прямую, отсекающую от первого координатного угла треугольник.
а) Докажите, что количество точек с целыми неотрицательными координатами, которые лежат внутри или на сторонах этого треугольника, больше, чем 2 \cdot a \cdot b + a + b.
б) Докажите, что эта оценка точная: через точку (a;b) можно провести прямую, отсекающую от первого координатного угла треугольник, внутри и на сторонах которого всего 2 \cdot a \cdot b + a + b точек с целыми неотрицательными координатами.

Решение

Рассмотрим прямоугольник OABC с центром в точке P(a;b), и сторонами, параллельными осям координат(рис.1). Внутри и на сторонах этого прямоугольника всего (2 \cdot a + 1) \cdot (2 \cdot b+1) =  4\cdot a \cdot b + 2\cdot a + 2 \cdot b +1 целочисленных точек.
 
method-draw-image (8)
Pис.1
 
Чуть-чуть сдвинем точку A вправо. Через полученную точку A' и точку P проведем прямую до пересечения с осью ординат в точке C'. Если сдвиг был достаточно мал, то в треугольнике OA'C' не появится ни одной точки с целыми координатами, которой не было бы в треугольнике OAC.
При центральной симметрии относительно P любая целочисленная точка прямоугольника OABC переходит в целочисленную точку этого же прямоугольника. Поэтому все отличные от P целочисленные точки прямоугольника разбиваются на пары точек, симметричных относительно P.
Итак, если A' достаточно близка к точке A, то внутри и на границе треугольника OA'C' расположена ровно половина отличных от P целочисленных точек, т.е. 2 \cdot a \cdot b + a + b точек. Вместе с точкой P получаем всего 2 \cdot a \cdot b + a + b + 1 точек. Мы решили пункт б).
 
Теперь займемся пунктом а). Для определенности, пусть прямая отсекает от первого координатного угла треугольник OA_1C_1, где точка A_1 расположена правее точки A(рис.2).
 
method-draw-image (9)
Рис.2
 
Чтобы получить треугольник OA_1C_1 из треугольника OAC, достаточно «отрезать» от последнего треугольник CC_{1}P и добавить треугольник AA_{1}P.
Но при центральной симметрии относительно точки P треугольник CC_{1}P переходит в треугольник, являющийся частью треугольника AA_{1}P(закрашенный на рисунке 2). Целочисленные координаты при этом переходят в целочисленные. Задача решена.