2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Сколько диагоналей у выпуклого многоугольника?
Сообщение31.07.2016, 19:00 
Аватара пользователя
Рассмотрим выпуклый $n$-угольник и начнём соединять диагоналями его вершины. Первую вершину надо соединить с $(n-3)$ вершинами (без неё самой и двух смежных, с которами она соединена рёбрами), вторую вершину с $(n-4)$ (потому что с первой она уже соединена на предыдущем шаге), а последнюю соединять ни с чём уже не надо будет. В итоге имеем $\sum\limits_{i=1}^{n-1} (n-2-i) = \frac{2(n-3)-(n-1-1)}{2} \cdot (n-1) = \frac{n-4}{2} \cdot (n-1)$.

Общеизвестно, что правильный ответ $\frac{n(n-3)}{2}$. Где ошибка в моём рассуждении?

 
 
 
 Re: Сколько диагоналей у выпуклого многоугольника?
Сообщение31.07.2016, 19:07 
Hasek в сообщении #1141172 писал(а):
Рассмотрим выпуклый $n$-угольник и начнём соединять диагоналями его вершины. Первую вершину надо соединить с $(n-3)$ вершинами (без неё самой и двух смежных, с которами она соединена рёбрами), вторую вершину с $(n-4)$ (потому что с первой она уже соединена на предыдущем шаге),
Рассмотрим квадрат и начнем соединять диагоналями его вершины. Первую вершину надо соединить с $4-3=1$ вершиной (без неё самой и двух смежных, с которами она соединена рёбрами), вторую вершину с $4-4=0$ ... это похоже на правду?

 
 
 
 Re: Сколько диагоналей у выпуклого многоугольника?
Сообщение01.08.2016, 08:30 
Аватара пользователя
Можно вообще так рассуждать:
Сколько способов выбрать две вершины из $n$? Ну и вычесть определенные случаи

 
 
 
 Re: Сколько диагоналей у выпуклого многоугольника?
Сообщение01.08.2016, 10:46 
Аватара пользователя
Hasek в сообщении #1141172 писал(а):
В итоге имеем $\sum\limits_{i=1}^{n-1} (n-2-i)$.

Прибавлю к сказанному, что в этой странной сумме последнее слагаемое отрицательное.

-- 01.08.2016, 10:49 --

И да, как Вам намекнул Pphantom, придумывая какую-нибудь формулу, надо обязательно "обкатывать" её на простейших примерах - в данном случае многоугольниках с малым количеством сторон.

 
 
 
 Re: Сколько диагоналей у выпуклого многоугольника?
Сообщение01.08.2016, 12:04 
Аватара пользователя
Разобрался: каждая из $n$ вершин должна быть соединена с $(n-3)$ другими, а так как одна диагональ соединяет сразу две вершины, то делим ещё на два, чтобы не учитывать диагонали дважды. Проблема была скорее в каком-то интуитивном понимании происходящего, чем в вычислении.

-- 01.08.2016, 12:32 --

Давайте, раз уж создал тему, немного разовьём задачу. Пусть теперь мне интересно максимальное возможное число точек пересечения диагоналей. Так как каждая точка пересечения однозначно определяет две диагонали, то всего вариантов выбора двух диагоналей из общего количества будет $C_{\frac{n(n-3)}{2}}^{2}$, но здесь учтены и пересечения в вершинах многоугольника у соседних диагоналей, поэтому ещё возможна трактовка числа точек пересечения внутри фигуры как $C_{\frac{n(n-3)}{2}}^{2} - n$. Это правда?

 
 
 
 Re: Сколько диагоналей у выпуклого многоугольника?
Сообщение01.08.2016, 14:44 
Hasek
Разве пар соседствующих (пересекающихся в вершине) диагоналей - $n$?
Снова на квадрате проверьте, вы будете удивлены количеству точек пересечения диагоналей по вашей формуле :-)

 
 
 
 Re: Сколько диагоналей у выпуклого многоугольника?
Сообщение01.08.2016, 16:00 
Аватара пользователя
NSKuber в сообщении #1141376 писал(а):
Hasek
Разве пар соседствующих (пересекающихся в вершине) диагоналей - $n$?
Снова на квадрате проверьте, вы будете удивлены количеству точек пересечения диагоналей по вашей формуле :-)

Да, я снова неправ. По крайней мере, с учётом вершин как точек пересечения, формула $C_{\frac{n(n-3)}{2}}^2$ верна.

 
 
 
 Re: Сколько диагоналей у выпуклого многоугольника?
Сообщение01.08.2016, 19:30 
Аватара пользователя
Я вот не совсем понял задачу, не могли бы Вы пояснить:
Вот провёл я все диагонали в многоугольнике. Посчитал количество точек пересечения, их оказалось $m$ штук, а что Вы понимаете под максимальным числом точек пересечения??

 
 
 
 Re: Сколько диагоналей у выпуклого многоугольника?
Сообщение01.08.2016, 19:45 
MestnyBomzh в сообщении #1141462 писал(а):
а что Вы понимаете под максимальным числом точек пересечения??

То, что в каждой точке не может пересекаться более двух.

-- Пн авг 01, 2016 20:47:36 --

Hasek в сообщении #1141394 писал(а):
По крайней мере, с учётом вершин как точек пересечения, формула $C_{\frac{n(n-3)}{2}}^2$ верна.

Нет. Нарисуйте шестиугольник.

 
 
 
 Re: Сколько диагоналей у выпуклого многоугольника?
Сообщение01.08.2016, 22:58 
Аватара пользователя
ewert в сообщении #1141469 писал(а):
То, что в каждой точке не может пересекаться более двух.


Да, именно так.

ewert в сообщении #1141469 писал(а):
Нет. Нарисуйте шестиугольник.


Вставляю подходящую картинку для наглядности:
Изображение

Я уже успел найти и осознать, что правильная формула $C_n^4$, потому что каждые четыре вершины определяют пару пересекающихся диагоналей, то есть как раз одну точку пересечения. $C_6^4 = \frac{6!}{4!2!} = \frac{5 \cdot 6}{2} = 15$, но на картинке я упорно нахожу лишь $13$ точек пересечения внутри фигуры...

 
 
 
 Re: Сколько диагоналей у выпуклого многоугольника?
Сообщение01.08.2016, 23:13 
Hasek в сообщении #1141510 писал(а):
потому что каждые четыре вершины определяют пару пересекающихся диагоналей

Вот так бы и с самого начала (хотя, справедливости ради, я и сам не сразу вспомнил, что эту задачу следует решать именно так; а ведь здесь, на форуме она где-то уже встречалась, и даже я лично, если не ошибаюсь, именно это тогда и предлагал).

Hasek в сообщении #1141510 писал(а):
но на картинке я упорно нахожу лишь $13$ точек пересечения внутри фигуры...

Это потому, что у Вас шестиугольник шибко правильный. Пошевелите его мысленно -- и центральная точка мгновенно растроится.

 
 
 
 Re: Сколько диагоналей у выпуклого многоугольника?
Сообщение01.08.2016, 23:33 
Аватара пользователя
Понял. Спасибо за указания к решению!

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group