Про отрезки

[Sasha2]

Имеется 100 отрезков (вобщем можно брать любые 100 отрезков). Какое максимальное количество треугольников можно составить из них:
1) В случае, когда ввершиной треугольника может быть любая точка отрезка (но пересечения запрещены).
2) Когда вершиной треугольника может быть только один из концов отрезков (ну понятно, что и здесь также пересечения отрезков запрещены).

[ИСН]

На плоскости, надо полагать? Иначе не смешно.
Надеюсь, треугольники, составленные из других, не считаются? Уточните этот момент. Допустим, я взял (в первом варианте) равносторонний треугольник (три отрезка) и провёл в нём средние линии (ещё три отрезка). Это я построил четыре треугольника или пять?

[Sasha2]

Да не плоскости. Но треугольники считаются все, главное, чтобы отрезки, которые Вы берете не пересекались.
Вообще для первого случая наверно все просто, берем три отрезка из них делаем треугольник, а далее, любой следующй отрезок может добавить только два треугольника максимум. По моему более эффективного способа нет. Итого всего 195 для первого случая.

[Sasha2]

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

[Someone]

Sasha2 писал(а):

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

Почему два? Берём отрезок $AB$ и на перпендикуляре, проходящем через середину $AB$, по одну сторону от $AB$ последовательность точек $C_1,C_2,\dots,C_n$ (в порядке удаления от $AB$). Первоначально проведены отрезки $AC_k$, $BC_k$ ($1\leqslant k\leqslant n$) и $C_kC_{k+1}$ ($1\leqslant k<n$) или (для первого варианта) отрезок $C_1C_n$. Теперь присоединяем отрезок $AB$. Появляются $n$ новых треугольников $ABC_k$ ($1\leqslant k\leqslant n$). Или я что-то неправильно понял?

[Sasha2]

По условию задачи отрезки НЕ ПЕРЕСЕКАЮТСЯ.

[Someone]

Sasha2 писал(а):

По условию задачи отрезки НЕ ПЕРЕСЕКАЮТСЯ.

А какие отрезки у меня пересекаются?

[Sasha2]

Извините, уважаемый Someone, не понял сразу. Но все равно, вот смотрите да действительно, если провести таким образом, как Вы говорите, то получится еще 2n треугольников, но на сооружение этой конструкции Вы затратите 1) 2n отрезков (без образования вообще каких-либо треугольников) + еще один. То есть всего Ваши 2n + 1 дадут 2n труегольника, а в моем способе из них можно получить 4n+2. Сравнимвайте сами.

[MMyaf]

Пусть все отрезки одинаковой длинны.
1)Для 3 отрезков - 1 треугольник(обычный треугольник)
2)Для 6 отрезков - 4 треугольник (грани тетраэдра)
3)Возьмем тэтраэдр(6 отрезков - 4 треугольник) и на одной из граней с помощью еще трех отрезков построим еще один тэтраэдр, тогда количество отрезков возрастет на 3 отрезка, а количество треугольников на три(грани второго тэтраэдра).
Для 9 отрезков - 7 треугольников
Строя на гранях тэтраэдра такие же тетраэдры(как описано в 3) ), мы будем получать растущую фигуру(совокупность тэтраэдров),причем каждый построенный тэтраэдр будет давать +3 отрезка(использованных)и +3 треугольника.
Таким образом будет использовано 99 отрезков из 100 предложенных.Кол-во треугольников=97

[Someone]

Извините, Sasha2, я контрпример строил к утверждению, что при проведении нового отрезка может получиться не более двух новых треугольников. Если последним проводить отрезок $AB$, то у меня получается $n$ новых треугольников.

Но я не утверждал, что эта конструкция даёт максимальное число треугольников (кстати, у меня их там всё-таки не $2n+1$ отрезков, а $2n+2$ или даже $3n$, а число треугольников - не $2n$, а $3n-2$, что, конечно, далеко от максимального, по крайней мере, в первом случае).

Но Ваш результат для первого случая (когда вершинами треугольников могут быть любые точки отрезков) тоже далёк от максимального. Рассмотрим на прямой $n>1$ точек $A_1,A_2,\dots,A_n$ и ещё одну точку $B$, расположенную вне этой прямой. Проведём все отрезки $A_kB$ ($1\leqslant k\leqslant n$) и отрезок, содержащий все точки $A_1,A_2,\dots,A_n$, всего, таким образом, $n+1$ отрезок. Эти отрезки образуют $C_n^2=\frac{n(n-1)}2$ треугольников $A_iA_jB$ ($1\leqslant i<j\leqslant n$). При $n=99$ получим как раз $100$ отрезков и $\frac{99\cdot 98}2=4851$ треугольник. Не знаю уж, максимальное это число или нет.

[Sasha2]

Ну это только вопрос в том, как считать. Ведь в методе предложенном мной. Тоже все последующие отрезки могут выходить из одной точки. Тогда, наверно просто мно. неправильно подсчитано это число треугольников. Всего действительно одно основание и 99 отрезков, выходящих из одной точки к 99 точкам этого основания, из которых 2 являются концы указанного основания. Просто надо пересчитать, сколько их там всего.

[Руст]

Всё зависит от способа подсчёта и приведённые конструкции не оптимальны. Например с помощью 2n+2 отрезков можно образовать решётку n*n и добавив ещё 4n-2 диагональных получим 4n*n непересекающихся по площади треугольников (треугольники пересекаются только по одномерным или нульмерным граням. А если считать пересекающиеся то рост кубический. Легко доказать (подсчётом числа сторон, одна сторона общая не более чем для двух треугольников) что число непересекающихся треугольников не может расти быстрее квадратичной зависимости, точнее не больше (n*n)/2. Здесь получилось (n*n)/9, поэтому возможно это не оптимально.

[Someone]

Руст писал(а):

с помощью 2n+2 отрезков можно образовать решётку n*n

Извините, Вы неправильно поняли условие. Автор задачи требует, чтобы отрезки не пересекались, то есть, в первом варианте общая точки двух отрезков по крайней мере для одного из них должна быть концевой, а во втором она должна быть концевой для обоих отрезков.

Во втором случае автор ещё не совсем определил способ подсчёта треугольников: не указано, может ли сторона треугольника составляться из нескольких отрезков, если они лежат на одной прямой.

Если на расположение отрезков не накладывать никаких ограничений, то $n$ отрезков могут образовать $C_n^3=\frac{n(n-1)(n-2)}6$ треугольников.

[Sasha2]

Честно говоря, это задача из олимпиад МФТИ для школьников.
Вот ее полное условие:
Даны 100 отрезков. Какое максимальное число прямоугольных
треугольников можно составить из троек этих отрезков? В каждом
треугольнике используются разные отрезки. Один отрезок может
участвовать в составлении нескольких треугольников.

У меня сразу возникает вопрос. Можно ли это условие сделать как то попонятнее. Например, что значит разные (они все должны быть разные, или, чтобы хтя бы две стороны). Наверно вот тут профессиональный математик должен прояснить условие с тем, чтобы оно стало корректным.

[Руст]

Вы начали понимать под разными отрезками разные доли этих отрезков, соответственно я эту идею продолжил. На самом деле это явно не запрещается, всё зависит от придания смысла разные отрезки.