Число областей

[Профессор Снэйп]

VAL в сообщении #609401 писал(а):

Профессор Снэйп в сообщении #609384 писал(а):

В такой формулировке задача вполне решабельна. Четыре точки дадут тетраэдр. Пятую точку можно поместить либо внутрь тетраэдра, либо в "боковую" область, либо в "рёберную", либо в "угловую". Аккуратно разбираете эти 4 варианта и выбираете максимальный результат из четырёх

Еще раз. От этого ничего не зависит: n гиперплоскостей общего положения однозначно определяют количество областей, на которые разбивается пространство.
В данной же задаче вся трудность в том, что плоскости получаются заведомо не общего положения.

Да про плоскости общего положения никто и не спорит. Классическая задача, я её ещё лет 8 назад решал на форуме ММФ НГУ.

Тут же речь идёт не о плоскостях, а о точках "в общем положении". И что это такое, совершенно непонятно.

Насчёт четырёх вариантов. На самом деле их максимум три, так как пятая точка внутри "угловой" области равносильна пятой точке внутри тетраэдра. Надо подумать, нельзя ли ещё подсократить количество. Но в том, что существуют различные комбинации из пяти точек, дающие разное число областей, причём такие, при которых никакие 4 точки не лежат в одной плоскости, я почти уверен. По крайней мере, в случае меньшей размерности это так: четыре точки на плоскости, никакие три из которых не лежат на одной прямой, дают то 16, то 18 областей.

[Alexander Evnin]

Цитата:

VAL в сообщении #609398 писал(а):
Склоняюсь к мысли, что для пяти точек общего положения ответ все же единственный.

А почему тогда для четырёх точек на плоскости ответ разный?

Имеются, очевидно, в виду точки "самого общего положения".

[Профессор Снэйп]

Alexander Evnin в сообщении #609405 писал(а):

Имеются, очевидно, в виду точки "самого общего положения".

Это какой-то устоявшийся термин или Вы сами его только что ввели?

[Alexander Evnin]

Приведу моё решение плоской задачи (с заведомо верным ответом).

Исходные точки будем называть красными.

Всего имеется $N=\frac{n(n-1)}{2}$ пар красных точек. Столько будет и прямых.

Будем последовательно проводить прямые. Если прямая $l$ пересекается с ранее
проведёнными в $k$ точках, то эти точки делят прямую на $k+1$ частей (лучи и
отрезки), каждая из которых, в свою очередь, делит одну <<старую>> часть
разбиения плоскости на две <<новые>>. Поэтому после проведения прямой $l$
количество частей увеличивается на $k+1$.

Пусть $k_i$ - число точек пересечения $i$-й прямой
с ранее проведёнными прямыми. Как уже отмечалось, после проведения $i$-й
прямой количество частей разбиения увеличивается на $k_i+1$.
Поскольку изначально имелась одна часть, после проведения всех $N$ прямых количество частей равно

$$y_n=1+\sum_{i=1}^N(k_i+1)=1+N+\sum_{i=1}^Nk_i.\eqno (1)$$

Будем называть точки пересечения прямых, отличные от красных, синими.
Количество частей будет максимально, если любые две прямые пересекаются, и
через каждую красную точку проходит ровно $n-1$ прямых, а через каждую синюю --- две прямые. Найдём, каким будет при этом количество синих точек (обозначим эту величину через $z$).

Всего пар прямых $\frac{N(N-1)}{2}$. На каждую красную точку приходится
$\frac{(n-1)(n-2)}{2}$ пар пересекающихся прямых, а на каждую синюю точку ---
одна пара. Поэтому
$\frac{N(N-1)}{2}=n\cdot\frac{(n-1)(n-2)}{2}+z,$ откуда

$$z=\frac{N(N-1)}{2}-n\cdot\frac{(n-1)(n-2)}{2}.$$

Теперь заметим, что в сумме $\sum_{i=1}^Nk_i$ каждая синяя точка учитывается
один раз, а каждая красная $n-2$ раза (после того, как первый раз проведена
прямая $AB$ через красную точку $A$, где $B$ --- другая красная точка, через точку $A$ пройдут
ещё $n-2$ прямых, соединяющих $A$ с остальными красными точками).

Поэтому

$$\sum_{i=1}^nk_i=z+n(n-2)= \frac{N(N-1)}{2}-n\cdot\frac{(n-1)(n-2)}{2}+n(n-2).\eqno(2)$$

Для получения окончательного ответа осталось подставить (2) в (1) и вместо $N$ его
выражение через $n$.

-- 23.08.2012, 12:18 --

Цитата:

Alexander Evnin в сообщении #609405 писал(а):
Имеются, очевидно, в виду точки "самого общего положения".

Это какой-то устоявшийся термин или Вы сами его только что ввели?

Только что ввёл.

-- 23.08.2012, 12:37 --

В своё оправдание по поводу формулировки A153445 про точки общего положения скажу, что для образца брал формулировку [oeis]A055503[oeis] Take n points in general position in the plane; draw all the (infinite) straight lines joining them; sequence gives number of connected regions formed.

[VAL]

Alexander Evnin в сообщении #609405 писал(а):

Цитата:

VAL в сообщении #609398 писал(а):
Склоняюсь к мысли, что для пяти точек общего положения ответ все же единственный.

А почему тогда для четырёх точек на плоскости ответ разный?

Имеются, очевидно, в виду точки "самого общего положения".

На текущий момент, я полагаю, что для пяти точек, никакие четыре из которых не лежат в одной плоскости, ответ единственный - 96. (Впрочем, я уже дважды сменил мнение и не уверен, что не сделаю этого впредь )

Конечно же, в пространстве, аналогично плоскому случаю, условие "никакие 4 их $n$ точек не лежат в одной плоскости" недостаточно для однозначности ответа. Но эта неоднозначность, похоже, проявится при $n>5$.

-- 23 авг 2012, 11:46 --

Еще раз аккуратно (насколько это слово и я совместимы) проверил свои выкладки.
Нашел очередную ошибку Оказывается, шесть плоскостей, пересекающихся в одной точке "съедают" не 12, а 10 областей.

Текущий подсчет:
10 плоскостей общего положения дают 176 областей;
5 точек пересечения по 6 плоскостей в каждой уничтожают 50 областей;
10 точек пересечения по 4 плоскости в каждой уничтожают 10 областей;
10 прямых, в которых пересекаются по 3 плоскости в каждой, уничтожают 20 областей;
Итого: $176-50-10-20=96$.

Если одни и те же уничтоженные области не выброшены дважды, ответ окончательный.
А если выброшены...
Я не первый, у кого в этой задаче получилось много ответов с шестеркой в конце

[Sender]

Поместив пятую точку внутрь тетраэдра и применив пространственное воображение, я получил те же 96 областей: каждая из боковых и угловых разделяется на 6 частей, каждая их рёберных - на 4, а внутренняя - на 24.