|
|
 |
Условие
На координатной плоскости нарисовано n парабол, являющихся графиками квадратных трёхчленов; никакие две из них не касаются. Они делят плоскость на несколько областей, одна из которых расположена над всеми параболами. Докажите, что у границы этой области не более 2(n – 1) углов (то есть точек пересечения пары парабол).
Решение
Индукция по n.
База. При n = 1 утверждение очевидно.
Шаг индукции. Пусть f1(x), f2(x), ..., fn(x) – данные квадратные трёхчлены (n ≥ 2), причём fn(x) – трёхчлен с минимальным старшим членом (если таких несколько, то любой из них). Обозначим границу нашей области через T. Можно считать, что T содержит участки всех графиков.
Пусть S – множество всех таких чисел a, что точка множества T с абсциссой a лежит на графике трёхчлена fn(x). Иначе говоря, число a принадлежит
S тогда и только тогда, когда выполнены неравенства fn(x) ≥ fi(a) при всех i = 1, 2, ..., n – 1. Обозначим через Si множество всех решений i-го неравенства; тогда . Поскольку трёхчлен fn(x) – fi(x) либо обладает отрицательным старшим коэффициентом, либо является на самом деле линейным, Si – это либо отрезок (возможно, вырожденный), либо луч, либо вся прямая. Значит, и S является множеством такого же вида.
Итак, у T не более двух углов, принадлежащих графику fn(x). Если мы удалим этот график, исчезнут эти углы (и, возможно, появятся новые). При этом по предположению индукции новая область будет иметь не более 2(n – 2) углов; значит, исходная имела не более 2(n – 2) + 2 = 2(n – 1) углов.
Замечания
1. Оценка, указанная в условии задачи, достигается. В качестве примера можно взять квадратные трёхчлены 2x², 2x² – (x – 1)(x – 2),
2x² – (x – 3)(x – 4), 2x² – (x – 5)(x – 6), ...
2. Приведём схему другого подхода к задаче, который годится не только для квадратных трёхчленов, но и для любых непрерывных функций f1, f2, ..., fn, графики любых двух из которых пересекаются не более, чем в двух точках.
Пусть T разбивается точками пересечения функций на участки I0, I1, ..., Ik графиков функций fm0, fm1, ..., fmk, (участки занумерованы слева направо). Выписав подряд индексы, мы получим слово M = (m0, m1, m2, ..., mk) в алфавите из n букв {1, 2, ..., n}.
В слове M нет двух подряд идущих одинаковых букв (условие 1). Также нетрудно показать, что из слова M нельзя, вычеркнув несколько букв, получить слово вида (a, b, a, b), где a ≠ b (условие 2). Утверждение задачи теперь можно получить, доказав, что длина слова, удовлетворяющего условиям 1 и 2, не превосходит 2n – 1. Это можно сделать различными методами. См. задачу 98237, где аналогичное утверждение доказано для круговой расстановки.
