Комбинаторика

artvxvx · Сообщение **artvxvx** » 12 апр 2010, 18:29

Сколькими способами среди вершин данного правильного 18-угольника можно выбрать три вершины так, чтобы образованный ими треугольник был тупоугольным?
Кроме прямого подсчета ничего не придумал. Думаю есть метод проще. Помогите, пожалуйста.

Самоед

artvxvx писал(а):Source of the post
Сколькими способами среди вершин данного правильного 18-угольника можно выбрать три вершины так, чтобы образованный ими треугольник был тупоугольным?
Кроме прямого подсчета ничего не придумал. Думаю есть метод проще. Помогите, пожалуйста.

Думаю, есть метод проще: "Помогите, пожалуйста!".
1) Обозначить все вершины буквами (ABCDE....)
2) Первый тупоугольник - ABC (Решите, для себя - считать разными ABC BAC CAB или одинаковыми)
3) Второй тупоугольник -ABD, третий -ABE,..... и так -приблизительно до 10-ой вершины от вершины A,
4) Потом рассматривайте треугольники ACD и так далее, пока все не переберете......
Эти перебор и прямые вычисления - доказательство к ответу на вопрос задачи. Готовая формула, хотя и окажется верным ответом, не явится правильным решением (решение - логическое доказательство ответа).

СергейП

artvxvx писал(а):Source of the post Сколькими способами среди вершин данного правильного 18-угольника можно выбрать три вершины так, чтобы образованный ими треугольник был тупоугольным?
Кроме прямого подсчета ничего не придумал. Думаю есть метод проще. Помогите, пожалуйста.

Задача решается так. Пронумеруем вершины многоугольника, допустим по часовой стрелке. Тр-ник, образованный 3-мя вершинами вершинами мн-ка будет тупоугоугольным в том и только в том случае, если среди 3 выбранных вершин найдутся такие 2 вершины, что между ними будет не менее 9 вершин мн-ка (3-я вершина тр-ка c другой стороны).
Теперь легко пересчитать кол-во таких тр-ков: 1-ю вершину можно выбрать 18-ю способами, 2 другие подходящие вершины выбираем из следующих 8 вершин $$C_8^2$$

способами, итого получаем
$n=18 \cdot C_8^2$

jmhan · Сообщение **jmhan** » 14 апр 2010, 17:41

СергейП писал(а):Source of the post
Тр-ник, образованный 3-мя вершинами вершинами мн-ка будет тупоугоугольным в том и только в том случае, если среди 3 выбранных вершин найдутся такие 2 вершины, что между ними будет не менее 9 вершин мн-ка (3-я вершина тр-ка c другой стороны).

Неверно, например все треугольники, образованные любой вершиной и двумя соседними - тупоугольные, т.к. угол между соседними гранями 18-иугольника = (18 * 180 - 360) / 18 = 160 градусов. T.e. каждые три соседние вершины образуют тупоугольный треугольник.

СергейП

jmhan писал(а):Source of the post
СергейП писал(а):Source of the post Тр-ник, образованный 3-мя вершинами вершинами мн-ка будет тупоугоугольным в том и только в том случае, если среди 3 выбранных вершин найдутся такие 2 вершины, что между ними будет не менее 9 вершин мн-ка (3-я вершина тр-ка c другой стороны).
Неверно, например все треугольники, образованные любой вершиной и двумя соседними - тупоугольные, т.к. угол между соседними гранями 18-иугольника = (18 * 180 - 360) / 18 = 160 градусов. T.e. каждые три соседние вершины образуют тупоугольный треугольник.

A если немножко подумать
Если не менее 9, то это означает 9 или более. Если тр-к из 3 соседних вершин, например, c номерами 1, 2, 3, то между 1-ой и 3-ей будет 15>9 вершин, o чем у меня и написано.

jmhan · Сообщение **jmhan** » 14 апр 2010, 18:18

Да, не допер... A объясните пожалуйста, как Вы получили эту зависимость (в смысле, что 9 или более)?

СергейП

jmhan писал(а):Source of the post Да, не допер... A объясните пожалуйста, как Вы получили эту зависимость?

Объяснить что? Почему 9 или почему такая формула?
Впрочем, можно попробовать сразу оба момента. Опишем окружность вокруг мн-ка.
Выберем 3 вершины, Пусть угол при одной из вершин тупой, тогда возьмем предыдущую ему вершину (т.e. против часовой стрелки), проведем из нее диаметр.
Тр-к будет тупоугольным тогда и только тогда, когда он весь лежит по одну сторону от этого диаметра, т.e. 2 другие вершины лежат слева (co стороны выбранной точки) от диаметра.
Выбрав для 2-ого острого угла самую дальнюю допустимую вершину, пересчитаем сколько между ними вершин c другой стороне диаметра, их будет 9. C другой стороны, если между 2 соседними вершинами 9 или более вершин мн-ка, то такой тр-к лежит по одну сторону от некоего диаметра, т.e. он тупоугольный.
A теперь формула, перебираем по очереди все 18 вершин, проводим из них диаметр и строим все тр-ки, лежащие слева от этого диаметра, подбирая для выбранной вершины еще 2 из 8 возможных.

yourdomain.com