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