Разрезы вдоль

[Terraniux]

1. Плоскость разрезана вдоль 1000 прямых общего положения. Доказать, что среди получившихся частей будет не менее 998 треугольников.
2. Пространство разрезано вдоль 1000 плоскостей общего положения. Каково наибольшее гарантированное число тетраэдров среди получившихся частей?

[Ktina]

Terraniux
Если, к примеру, все прямые попарно параллельны, то не получится ни одного треугольника. Или я не понимаю условия задачи. Что означает "общего положения".

[Aritaborian]

Как раз и означает, что никакие две прямые не параллельны (а также что никакие три не пересекаются в одной точке).

[Ktina]

(Оффтоп)

Aritaborian

[Mihr]

По-моему, тут всё получается по индукции. Первые три прямые вырезают один треугольник, а каждый следующий разрез добавляет, как минимум, один треугольник.

[atlakatl]

Есть три «прямых общего положения» (ПОП, - определение Aritaborian разумно, Ktina зря сокрушается). Они формируют один треугольник.
Каждая новая ПОП пересекается с каждой предыдущей ПОП.
Каждая тройка ПОП образует свой треугольник. 4-я ПОП формирует уже 2 новых треугольника. 5-я – ещё три.
Для n ПОП получаем $1+2+3+4+…+ (n-2)= ((n-2)+1)\cdot(n-2)/2$.
Для 1000 ПОП имеем $((1000-2)+1)\cdot(1000-2)/2=498501$ треугольник.

[Ktina]

atlakatl

(Оффтоп)

Это я над собой сокрушаюсь, что мне не было известно такое простое определение

[Mihr]

atlakatl,
здесь речь не о треугольниках, стороны которых лежат на построенных прямых (а вершинами служат точки пересечения этих прямых), а о треугольниках, появляющихся при разрезании плоскости вдоль построенных прямых. Таковых существенно поменьше.

[atlakatl]

Mihr в сообщении #953392 писал(а):

о треугольниках, появляющихся при разрезании плоскости вдоль построенных прямых

Поясните на примере четырёх прямых. - Не могу понять, о чём Вы...
Допёр. Тогда всё не так просто. Индукция имеет место быть, но довольно сложная.

[Terraniux]

Mihr в сообщении #953349 писал(а):

По-моему, тут всё получается по индукции. Первые три прямые вырезают один треугольник, а каждый следующий разрез добавляет, как минимум, один треугольник.

Разрезы могут еще и убирать треугольники, это уже на четвертом шаге видно. Они еще будут добавлять, но это нужно доказывать, какие случаи и т.д.
Поэтому таким простым рассуждением сходу не решить задачу.

[Mihr]

Terraniux,
да я и не думал, что эта задача такая уж простая простая. И, честно говоря, не пытался её "копать". Просто сказал, что, вероятно, она решается так. Но вот как именно разрез может "убрать треугольник", я не сообразил. Если новый разрез проходит по существующему треугольнику (причем не через его вершину), то должен разделить его на треугольник и четырехугольник, а значит при этом число треугольников не меняется. Но кроме того, он разрезает и бесконечные области, отрезая от них, как минимум, один новый треугольник - так мне показалось. Хотя, конечно, могу ошибиться. Сможете ли Вы пояснить, как может новый разрез уменьшить число треугольников? У меня не получилось представить себе такую картинку.

[arseniiv]

$n$-я прямая делится предыдущими на $n-2$ отрезка и два луча. Либо отрезок лежит в пустом внутри треугольнике — и тогда баланс нулевой, либо отрезок стягивает пустой внутри угол — тогда появляется треугольник, либо отрезок лежит в многоугольнике, и тогда треугольник может как появиться, так и не появиться. Других случаев быть бы не должно. Надо попробовать показать, что пересечение угла хотя бы раз происходит — или контрпример есть?

Mihr, о, я вас повторяю.

-- Вс дек 28, 2014 23:04:46 --

arseniiv в сообщении #953620 писал(а):

Других случаев быть бы не должно.

Вру. Отрезок может родить многоугольник из неограниченной области. Хотя это никак не сказывается на моём предложении.

[Terraniux]

Mihr
Да, если он пройдет внутри треугольника, то отсечет треугольник и четырехугольник - неточно сформулировал фразу, то, что Вы сказали, и имелось в виду, т.е. баланс сохранится, и надо искать новые треугольники на других пересечениях, что не так просто.

[arseniiv]

(О, а можно вот как попробовать: ставим новую прямую далеко-далеко (пересекает только бесконечные области), смотрим варианты. Потом приближаем её и смотрим, как конфигурация может измениться (при переходе через пересечение или несколько), а как не может.)

[vmg]

1) Прямая, пересекающая треугольник, отрезает от него меньший треугольник. Если какая-то другая прямая пересекает новый треугольник, то от него отрезается меньший и т.д. То есть внутри первоначального треугольника обязательно есть (меньший) треугольник. 2) Выберем произвольную из 1000 прямых. Ее пересекают 999 прямых в 999 точках, которые высекают на выбранной прямой 998 отрезков (и 2 луча). Выбранная прямая и две прямые, проходящие через соседние точки, образуют треугольник. Таких не пересекающихся по внутренним точкам треугольников 998, внутри каждого из которых есть (меньший) треугольник.