Условие
99 прямых разбивают плоскость на
n частей. Найдите все возможные значения
n, меньшие 199.
Решение
Индукцией по
m легко доказать, что
m прямых разбивают плоскость на 1 +
m +
x
частей, где
x — количество точек пересечения этих прямых с учётом их
кратностей (это означает, что точка пересечения
k прямых считается за
k - 1
точек пересечения).
Используя эту формулу и индукцию по
m, можно доказать, что если среди данных
m прямых есть три прямые, пересекающиеся в трёх различных точках, то эти
m
прямых разбивают плоскость по крайней мере на 2
m + 1 частей. База индукции:
m = 3; далее мы пользуемся тем, что проведение каждой новой прямой добавляет по
крайней мере две новые части.
Обращаясь к условию задачи, мы видим, что нас интересуют только конфигурации
прямых, среди которых нет троек прямых, пересекающихся в трёх разных точках.
Таким образом, либо все 99 прямых параллельны, либо все 99 прямых
пересекаются в одной точке, либо 98 прямых параллельны и одна прямая их
пересекает. Первая конфигурация разбивает плоскость на 100 частей, а обе
остальные — на 198 частей.
Источники и прецеденты использования
