В выпуклом 19-угольнике проводят все его диагонали. На какое наибольшее число частей могут его разбить?

задан 5 Ноя '13 11:24

изменен 5 Ноя '13 21:43

Deleted's gravatar image


126

10|600 символов нужно символов осталось
4

Для $%n$%-угольника ответом будет $%C_n^4+C_{n-1}^2$%. При $%n=19$% это число равно $%4029$%.

Прежде всего, рассмотрим ситуацию общего положения, то есть такой случай, когда никакие три диагонали не пересекаются в одной (внутренней) точке. Такого рода конфигурации всегда существуют. Для построения можно точки выбирать на окружности, и $%n$%-угольник получится выпуклый. Чтобы избежать кратных пересечений диагоналей, точки на окружности будем задавать последовательно. Когда какое-то их количество уже задано, проведём все соединяющие их линии. Их будет конечное число, и окружность они пересекают в конечном числе точек. Следующую точку будем выбирать на окружности, избегая этого конечного множества случаев.

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

Нарисуем контур многоугольника. На этот момент у нас имеется одна часть. Будем последовательно проводить диагонали (в произвольном порядке), следя за тем, как увеличивается количество частей. Пусть мы провели очередную диагональ $%AB$%. Она пересекается во внутренних точках с каким-то числом $%k\ge0$% ранее проведённых диагоналей. При этом отрезок $%AB$% разбивается на $%k+1$% отрезков этими точками пересечения. Каждый из маленьких отрезков подразбивает одну из имеющихся к этому моменту частей разбиения на две. Значит, количество частей разбиения увеличивается на $%k+1$%.

Из этого следует, что итоговое число частей разбиения будет равно сумме вида $%1+(k_1+1)+(k_2+2)+\cdots+(k_m+1)$%, где $%m$% -- число диагоналей, и $%k_i$% -- число внутренних точек пересечения $%i$%-й диагонали с проведёнными ранее диагоналями.

Заметим, что $%m=C_n^2-n$%: это общее число соединений между точками минус число сторон. Осталось просуммировать числа $%k_i$%. Каждая единица этой суммы происходит от пересечения диагонали $%AB$% с ранее проведённой диагональю $%CD$%. Поэтому сумма будет равна числу точек пересечения диагоналей внутри многоугольника. Каждая точка пересечения считается ровно один раз при таком способе. А это число точек пересечения равно $%C_n^4$% по той простой причине, что всякая такая точка пересечения однозначно определяется вершинами четырёхугольника, выбираемыми произвольно из числа $%n$% вершин многоугольника. Мы выбираем $%4$% точки, и в получившемся четырёхугольнике проводим диагонали, получая тем самым точку пересечения. Из этого соображения также видно, что появление "кратных" пересечений уменьшает общее количество точек пересечения, а потому и итоговое количество частей.

Теперь осталось сложить $%C_n^4$% с числом $%1+C_n^2-n$%. Это и будет ответ. Второе слагаемое тождественно преобразовывается к виду $%C_{n-1}^2$%.

ссылка

отвечен 6 Ноя '13 5:55

С^2 c индексом n - это общее число соединений между точками. Как это понимать?

(18 Ноя '13 17:42) Иван Иванович

Это число сочетаний из $%n$% по $%2$%, равное $%n(n-1)/2$%. Стандартное понятие, и стандартное обозначение.

(18 Ноя '13 17:46) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,116
×52

задан
5 Ноя '13 11:24

показан
4515 раз

обновлен
18 Ноя '13 17:46

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

по почте:

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

по RSS:

Ответы

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

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