олимпиада - На какое наибольшее число частей можно разбить многоугольник?

Для $%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$%.