M1231. О разбиении плоскости графиками многочленов второй степени

Условие

На какое наибольшее число частей могут разбить плоскость Oxy графики n квадратных трехчленов вида y=ax^{2}+bx+c (n=1, 2, 3, ...)?

Ответ: n^{2}+1.

Решение

Докажем по индукции, что число частей не превосходит n^{2}+1. Для n=1 это ясно: парабола делит плоскость на две части.
Пусть доказано, что n-1 графиков делят плоскость не более, чем на (n-1)^{2}+1 частей. Проведем последний, n-й график. Он пересекается с каждым из n-1 предыдущих максимум в двух точках, т.е. он будет разбит не более чем на 2(n-1)+1=2n+1 кусков (включая два крайних, уходящих в бесконечность). Каждый из этих кусков параболы делит одну из имеющихся частей плоскости на две. Таким образом, при проведении последней параболы число частей увеличится не более чем на 2n+1, т.е. не превзойдет (n-1)^{2}+1+2n+1=n^{2}+1.
К задаче M1231
Легко строится пример, когда все графики попарно пересекаются в двух точках (см. рисунок) — при этом получится максимальное число частей, указанное в ответе.
Точно такие же образом можно подсчитать максимальное число частей, на которые делят плоскость n прямых, n окружностей и т.п.

Н.Васильев

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *