Question

Пожалуйста, срочно! 30 баллов! Сколько всего существует: а) незамкнутых ломаных, соединяющих 8 точек? б) замкнутых ломаных, соединяющих 8 точек

Answer 1

Ответ:

а) 20160

б) 2700

Объяснение:

a) Восемь точек - это восемь элементов из которых можно получить возможное число перестановок.

P = 8! = 1*2*3*4*5*6*7*8 = 40320

На самом деле их в два раза меньше, т. к. тут учтены ломаные одинаковые, но имеющие разное "направление" 1-2-3-4-5-6-7-8 и 8-7-6-5-4-3-2-1 например.

Т. е. 20160

б) Замкнутых будет в 8 раз меньше, т. к. повторяющиеся 1-2-3-4-5-6-7-8   = 2-3-4-5-6-7-8-1  = 3-4-5-6-7-8-1-2 и т д это одна и та же линия просто отсчет точек в разном порядке.

21600 / 8 = 2700

Answer 2

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

$V - E + F = 2$

Где:

• $V$ - количество вершин (точек)
• $E$ - количество рёбер (ломаных)
• $F$ - количество граней (областей, ограниченных ломаными)

а) Для незамкнутых ломаных, соединяющих 8 точек, у нас будет 8 вершин и $E$ рёбер. Поскольку ломаная незамкнутая, то у нас будет одна грань. Подставив это в формулу Эйлера:

$8 - E + 1 = 2$ $E = 7$

Таким образом, существует 7 незамкнутых ломаных, соединяющих 8 точек.

б) Для замкнутых ломаных, у нас также будет 8 вершин и $E$ рёбер. Но в данном случае у нас будет несколько граней. Давайте посмотрим, сколько граней у нас образуется при замыкании ломаной.

Когда замкнутая ломаная замыкается, она разделяет плоскость на $F$ граней. Каждая вершина участвует в формировании по крайней мере 3 граней (одна снаружи и две внутри). Таким образом, можно сказать, что каждое ребро добавляет к $F$ по крайней мере $\frac{3}{2}$ граней.

Используя формулу Эйлера и факт, что $E = 8$, мы можем записать:

$8 - 8 + F \geq 2$ $F \geq 2$

Так как грани целочисленны, минимальное значение для $F$ равно 2. Это означает, что будет по крайней мере 2 грани.

Итак, существует как минимум 2 замкнутые ломаные, соединяющие 8 точек.

Итого: а) 7 незамкнутых ломаных б) Минимум 2 замкнутые ломаные