Две задачи

[Drimacus]

Хочу решить две задачи.

1. На какое наибольшее число частей могут разделить выпуклый $n$-угольник все проведенные диагонали?
Здесь я думаю хочу рассуждать так. Если какие-нибудь три диагонали пересеклись, то небольшим шевелением вершин многоугольника можно добиться ситуации когда эти три диагонали образуют треугольник. Таким образом число частей увеличилось, поэтому лучше всего с точки зрения количества частей рассматривать тот многоугольник, у которого никакие три диагонали не пересекаются в одной точке. Дальше будем считать, что никакие три диагонали в одной точке не пересекаются.
Теперь проведем все диагонали из одной вершины в остальные. Тогда с каждой новой диагональю у нас увеличивалось число кусков на 1, т.е. изначально был один "кусок" это целый многоугольник, а дальше плюс треугольник, итого будет $1+n-3 = n-2$ частей. А теперь возникает вопрос что делать дальше? Хочется рассуждать как в задаче о делении плоскости набором прямых - с каждой проведенной новой диагональю число частей будет расти на 1, т.к. если вести потихоньку новую диагональ, то она разделит один старый кусок надвое строго в тот момент, когда произойдет первое пересечение с какой-нибудь старой диагональю, а затем еще одно пересечение и т.д. Таким образом, хочется сказать, что каждое новое пересечение даст ровно один новый кусок, а раз так, то кусков будет $n-2+A$, где $A$ - число точек пересечения всех диагоналей. Как бы теперь посчитать это число?
А пока вопрос - можно ли рассуждать так, как выше?

2. Существует ли замкнутая ломаная с $10000$ звеньями, пересекающая каждое свое звено ровно 13 раз?
Здесь что-то у меня нет идей. Сначала пробовал рассмотреть правильный $10000$-угольник и как-то проводить "симметричные" ломаные наподобие пятиконечных звезд, но так получаются только четное число пересечений каждого звена (хотя вроде бы для маельньких четных чисел такие ломаные действительно можно реализовать). А с нечетными не получается. Допускаю, что здесь ответ нет и есть какая-то простая идея, но она ускользает от меня.

-- 13.01.2024, 02:27 --

В первой задаче кажется придумал, как находить точки пересечения диагоналей, если они все различны. Нужно рассмотреть все четырехугольники с вершинами в вершинах исходного многоугольника. Тогда, поскольку у четырехугольника одна точка пересечения диагоналей, то перебирая все четверки вершин, получим точки пересечения всех диагоналей. Вернее, это в случае если разным четырехугольникам соответствуют разные диагонали, но это вроде бы очевидно так. Тогда ответ $A = C^4_n$, число различных четверок из $n$. Вроде ошибок не вижу, но на всякий пусть кто нибудь проверит.
Вопрос с ломанной все еще открыт. Хотя кажется для четного числа звеньев можно придумать пример, когда самопересечение ровно 1 раз, тогда, возможно, я не прав и ответ с 13 тоже может существовать (по крайней мере, для 6 с одним вроде придумывается).
И вообще, интересно обобщить вопрос: сколько звеньев может быть у замкнутой ломаной (и существует ли она вообще), если она пересекет каждое свое звено ровно $k$ Раз?

[Gagarin1968]

Drimacus
Вы новичок на форуме, поэтому используйте одну тему для одной задачи, иначе будет путаница в ответах.
Что касается первой задачи, это известная задача.

Drimacus в сообщении #1625713 писал(а):

можно ли рассуждать так?

Не совсем так.
Идея поочерёдного проведения диагоналей верная. Но проводя новую диагональ, мы пересекаем уже проведённые диагонали. Предположим, число этих точек пересечения $k$.
Эти точки делят новую диагональ на отрезки. Понятно, что эти каждый из этих отрезков делит одну из старых частей на две новых.
Тогда вопрос: на сколько увеличивается число частей при проведении этой новой диагонали? Я имею в виду, что если до проведения новой диагонали многоугольник был разбит на $a$ частей, а после её проведения оказался разбит на $b$ частей, то чему равно $b-a$?
И второй вопрос: сколько диагоналей имеет выпуклый $n$-угольник в общем случае (если никакие три диагонали не пересекаются в одной точке)?
P.S. Похожую задачу, как я помню, много лет назад разбирал на другом форуме безвременно ушедший от нас falcao. Я искал, но не нашёл.

[Drimacus]

Gagarin1968
Да, я кривовато выразился, имел в виду, что когда мы зафиксировали число частей "сейчас" и проводим новую диагональ, то новые куски она порождает своими отрезками, на которые она разделится при пересечении других диагоналей, таковых отрезков будет $k+1$, где $k$ - число пересечений только что проведенной диагонали со старыми.

Таким образом имеем взаимно-однозначное соответствие между новыми точками пересечения диагоналей и тем, на сколько увеличилось число кусков. Получается, в предположении что никакие три диагонали не проходят через одну точку, число кусков будет таким: cколько получилось при делении непересекающимися диагоналями + число точек пересечения диагоналей. Последнее равно $C^4_n$, как уже писал выше.
Итого $n-2+C^4_n$.

-- 13.01.2024, 13:22 --

Gagarin1968 в сообщении #1625746 писал(а):

И второй вопрос: сколько диагоналей имеет выпуклый $n$-угольник в общем случае (если никакие три диагонали не пересекаются в одной точке)?

Диагоналей в любом $n$-угольнике будет $C^2_n-n$, причем и невыпуклом тоже, и пересекаемость диагоналей в одной точке тоже не влияет на это.
Возможно, вы имели в виду сколько точек пересечения будет в таком многоугольнике? Ну я вроде бы уже ответил - $C^4_n$, т.к. при таком условии точка пересечения диагоналей соответствует взаимно-однозначно некоторому четырехугольнику с вершинами из вершин исходного.

-- 13.01.2024, 13:33 --

Теперь вижу свою ошибку - число частей, на которое делит разбившаяся диагональ, равно именно $k+1$, как уже сказал, т.е. я в сумме забыл учесть эту единицу. Итого правильно будет $C^4_n+C^2_n-n+1$, где $C^2_n-n$ - это число диагоналей, которое учет забытой единички, а $+1$ - это исходный кусок, бывший всем многоугольником. Вроде бы так уже правильно? Для $n=5,6$ проверил руками, ответы сходятся с реальностью.

[Gagarin1968]

Drimacus в сообщении #1625749 писал(а):

Диагоналей в любом $n$-угольнике будет $C^2_n-n$

Drimacus
Что-то меня немного переклинило. Я посчитал, что общее число диагоналей $n$-угольника равно $\dfrac {n(n-3)}{2}$ и тупо 5 минут смотрел на Вашу формулу, пока не понял, что это одно и то же выражение.

Drimacus в сообщении #1625749 писал(а):

Итого правильно будет $C^4_n+C^2_n-n+1$... Вроде бы так уже правильно?

Да, разумеется, правильно. Только я бы немного упростил: $\displaystyle C^2_n-n+1=C^2_{n-1}$, поэтому искомое число кусков равно $\displaystyle C^4_n+C^2_{n-1}$

[Drimacus]

Gagarin1968

Да, спасибо, задача решена.
В порядке простого замечания - с числом диагоналей действительно можно и через $n(n-3)/2$, т.к. каждой вершине соответствует $n-3$ проведенных отрезков, при этом каждый отрезок считается дважды, так даже проще. С другой стороны, формулу с парами вершин можно использовать индуктивно для многогранников старшей размерности.

[MGM]

1. Наибольшее число оно же и наименьшее.
Или условие неверное.
Так как в вашем условии нельзя ничего менять.

[Ende]

MGM
Предупреждение за вводящий в заблуждение комментарий в ПРР(М).

[Drimacus]

MGM в сообщении #1626034 писал(а):

1. Наибольшее число оно же и наименьшее.
Или условие неверное.
Так как в вашем условии нельзя ничего менять.

А можно по делу писать? Если вам непонятно, когда число частей бывает немаксимальным, то рассмотрите правильный шестиугольник и общий выпуклый шестиугольник. Число частей будет сильно разным. Об этом еще в моем первом сообщении написано - про пересечения трех и более диагоналей.
Потом, когда разберетесь с шестиугольником и вообще правильным $2k$-угольником можете подумать, отличается ли случай общего $2k+1$-угольника от случая правильного $2k+1$-угольника.