Некогда в лмш в общем тесте была задача: на какое максимально число кусков можно разрезать торт четырьмя прямыми разрезами. Ответ для всех, кто считает, что торт объемный -- 15. Теперь общая картина.
Для начала можно посчитать, чему равно число кусков, на которые разбивают плоскость n прямых общего положения. Эту задачу матшкольникам дают в теме индукция. Можно проверить, что n-ая по счету прямая добавляет n новых кусков (она разрезает именно столько уже имеющихся кусков, что можно проверить посчитав, сколько у нее точек пересечения с уже имеющимися прямыми). Изначально есть один кусок --- вся плоскость. Значит после n прямых разрезов кусков станет P(n)= 1+1+...+n = (n^2+n+2)/2.
Аналогично можно поступить с плоскостями в пространстве. Вначале есть один кусок --- все пространство. После разреза добавляется еще 1 кусок (именно столько уже имеющихся кусков пересекла новая плоскость), потом еще два (именно столько уже имеющихся кусков пересекла новая плоскость), потом еще 4 (именно столько уже имеющихся кусков пересекла новая плоскость) и так далее. Вопрос: сколько имеющихся кусков пересекает n-ая по счету плоскость? Заметим, что уже проведенные плоскости при пересечении с n-ой задают на ней n-1 прямых общего положения, которые разделяют ее на P(n-1) двумерных кусков. Эти двумерные куски соответствуют трехмерным кускам, которые пересекла наша n-ая плоскость. Значит на n-м шаге трехмерного разрезания добавляется P(n-1) новых кусков и ответ к задаче Q(n)= 1+1+2+4+...+P(n-1). Это можно просуммировать по стандартным формулам и получить некий многочлен 3-й степени от n. Можно это сделать методом неопределенных коэффициентов.
Однако, поступим по другому. Заметим, что P(n) = C_n^0 + С_n^1 + C_n^2 (это неспроста!). Тогда Q(n) = 1+ (C_0^0+C_1^0+...+C_{n-1}^0)+(C_1^1+C_2^1+...+C_{n-1}^1)+(C_2^2+C_3^2+...+C_{n-1}^2) = C_n^0 + C_n^1 + C_n^2 + C_n^3 по стандартным формулам для суммы диагонали треугольника Паскаля.
Теперь можно сформулировать общее утверждение: n гиперплоскостей общего положения делят k-мерное пространство на C_n^0+C_n^1+...+C_n^k кусков. Доказательство абсолютно аналогичное. А можно доказать по-другому...
Есть крутая формула Горески-Макферсона, которая позволяет решить эту задачу и аналогичные практически с ходу. Эта формула выражает гомологии дополнения до конфигурации вещественных аффинных плоскостей через гомологии нерва частично-упорядоченного множества всех возможных пересечений этих плоскостей (грубо говоря). В нашем случае надо посчитать число компонент связности дополнения до набора гиперплоскостей, то есть ранг нулевой группы гомологий. При этом ч.у.м плоскостей в этом случае явно описывается и для него все считается. Формулу Горески-Макферсона можно погуглить или прочитать книгу Горески, Макферсон "Стратифицированная теория Морса".
Некогда в лмш в общем тесте была задача: на какое максимально число кусков можно разрезать торт четырьмя прямыми разрезами. Ответ для всех, кто считает, что торт объемный -- 15. Теперь общая картина.
ОтветитьУдалитьДля начала можно посчитать, чему равно число кусков, на которые разбивают плоскость n прямых общего положения. Эту задачу матшкольникам дают в теме индукция. Можно проверить, что n-ая по счету прямая добавляет n новых кусков (она разрезает именно столько уже имеющихся кусков, что можно проверить посчитав, сколько у нее точек пересечения с уже имеющимися прямыми). Изначально есть один кусок --- вся плоскость. Значит после n прямых разрезов кусков станет P(n)= 1+1+...+n = (n^2+n+2)/2.
Аналогично можно поступить с плоскостями в пространстве. Вначале есть один кусок --- все пространство. После разреза добавляется еще 1 кусок (именно столько уже имеющихся кусков пересекла новая плоскость), потом еще два (именно столько уже имеющихся кусков пересекла новая плоскость), потом еще 4 (именно столько уже имеющихся кусков пересекла новая плоскость) и так далее. Вопрос: сколько имеющихся кусков пересекает n-ая по счету плоскость? Заметим, что уже проведенные плоскости при пересечении с n-ой задают на ней n-1 прямых общего положения, которые разделяют ее на P(n-1) двумерных кусков. Эти двумерные куски соответствуют трехмерным кускам, которые пересекла наша n-ая плоскость. Значит на n-м шаге трехмерного разрезания добавляется P(n-1) новых кусков и ответ к задаче Q(n)= 1+1+2+4+...+P(n-1). Это можно просуммировать по стандартным формулам и получить некий многочлен 3-й степени от n. Можно это сделать методом неопределенных коэффициентов.
Однако, поступим по другому. Заметим, что P(n) = C_n^0 + С_n^1 + C_n^2 (это неспроста!). Тогда Q(n) = 1+ (C_0^0+C_1^0+...+C_{n-1}^0)+(C_1^1+C_2^1+...+C_{n-1}^1)+(C_2^2+C_3^2+...+C_{n-1}^2) = C_n^0 + C_n^1 + C_n^2 + C_n^3 по стандартным формулам для суммы диагонали треугольника Паскаля.
Теперь можно сформулировать общее утверждение:
n гиперплоскостей общего положения делят k-мерное пространство на
C_n^0+C_n^1+...+C_n^k кусков. Доказательство абсолютно аналогичное. А можно доказать по-другому...
Есть крутая формула Горески-Макферсона, которая позволяет решить эту задачу и аналогичные практически с ходу. Эта формула выражает гомологии дополнения до конфигурации вещественных аффинных плоскостей через гомологии нерва частично-упорядоченного множества всех возможных пересечений этих плоскостей (грубо говоря). В нашем случае надо посчитать число компонент связности дополнения до набора гиперплоскостей, то есть ранг нулевой группы гомологий. При этом ч.у.м плоскостей в этом случае явно описывается и для него все считается. Формулу Горески-Макферсона можно погуглить или прочитать книгу Горески, Макферсон "Стратифицированная теория Морса".