Дан выпуклый nn-угольник, n , n≥6. Рассмотрим его диагонали. Посчитайте количество троек попарно непересекающихся диагоналей. Диагонали, имеющие общую вершину, считаются пересекающимися.

задан 2 Мар 19:37

с какого конкурса?

(2 Мар 20:14) mihailm

Хочу уточнить условие. Рассматриваются только диагонали? Стороны не входят в это число? Меня смутило ограничение n>=6. Если стороны также можно брать, то, начиная с 6, получаются случаи, когда не пересекаются три линии. А если брать чисто диагонали, то там нужно что-то типа n>=8.

(2 Мар 20:17) falcao

только диагонали

(2 Мар 22:19) f4ke
10|600 символов нужно символов осталось
0

Итак, пусть $%n\ge8$%, и рассматриваются только тройки диагоналей, без участия стороны. Пусть три диагонали проведены. Они попарно не пересекаются даже по концам. Получается 6 концевых точек. Среди них одна диагональ "внутренняя" и две "крайние" в понятном смысле. Выберем одну из двух крайних диагоналей, и обозначим точки по часовой стрелке буквами A, B, C, D, E, F, чтобы AB была выбранной крайней диагональю. Подсчитаем количество получившихся конфигураций из 6 пронумерованных точек, и в конце разделим на 2, чтобы получить ответ.

Точку A выбираем $%n$% способами, остальное $%C_{n-1}^5$% способами. Точки нумеруем по часовой стрелке, начиная с A, и требуем, чтобы ни $%AB$%, ни $%DE$% не оказались сторонами. Случаю, когда $%AB$% -- сторона, соответствует $%nC_{n-2}^4$% вариантов: точка A выбирается $%n$% способами, как и выше, точку $%B$% однозначно, и остальному соответствует число сочетаний. Случай, когда стороной оказывается $%DE$%, соответствует такому же количеству вариантов. Эти величины надо вычесть, и в соответствии с формулой включений и исключений, надо учесть случай, когда и $%AB$%, и $%DE$% будут сторонами. Он при вычитании был учтён дважды, то есть его надо вернуть. Нетрудно видеть, что здесь получится $%nC_{n-3}^3$%.

Итого с учётом последующего деления пополам будет $$ \frac{n}2\cdot({C_{n-1}^5-2C_{n-2}^4+C_{n-3}^3})=\frac{n(n-3)(n-4)(n-5)(n-6)(n-7)}{240}. $$

ссылка

отвечен 3 Мар 17:20

а если брать и стороны, то сколько получится?

(5 Мар 18:36) f4ke

видимо со сторонами тоже, хотя в условии не сказано про это

(5 Мар 18:43) f4ke

а если пересекающиеся?

(5 Мар 20:24) mihailm

@f4ke: если можно брать и стороны (что естественно при условии n>=6, как я уже отмечал), то задача становится проще. Там есть $%C_n^6$% способов выбрать 6 точек из $%n$%. В получившемся 6-угольнике можно тремя способами провести "диагонали" без пересечений. То есть там будет $%3C_n^6$%. Но вообще-то составителям нужно быть внимательнее.

(5 Мар 21:08) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,227
×1,559
×343

задан
2 Мар 19:37

показан
274 раза

обновлен
5 Мар 21:08

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru