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

[Alexander Evnin]

Ещё проще к результату приводит соотношение $F_k(n)=F_{k-1}(n)+C_n^k$. (см. мой текст по указанной ссылке).

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

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

Я понимаю под этим ровно то, что Вы написали: Никакие 4 не лежат в одной плоскости.

Ну а почему не может быть так, что в задаче не хватает данных? Почему не возможна ситуация, когда для двух наборов из пяти точек, каждый из которых характеризуется словами "общее положение", получается разное число областей?

-- Чт авг 23, 2012 03:41:05 --

Тетраэдр с точкой внутри и два тетраэдра с общей гранью - вроде в обоих случаях пять точек расположены так, что никакие четыре не лежат в одной плоскости. Но аффинными преобразованиями эти два набора из пяти точек друг в друга не переводятся, поскольку у них выпуклая оболочка принципиально разная (тетраэдр и шестигранник). Почему для этих двух случаев должны получаться одинаковые ответы?

[Alexander Evnin]

А почему в случае плоскости получается всегда одно и тоже число областей (независимо от вида выпуклой оболочки)?

[VAL]

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

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

Я понимаю под этим ровно то, что Вы написали: Никакие 4 не лежат в одной плоскости.

Ну а почему не может быть так, что в задаче не хватает данных? Почему не возможна ситуация, когда для двух наборов из пяти точек, каждый из которых характеризуется словами "общее положение", получается разное число областей?

Почему не возможна? Очень может быть, что так и есть.

Цитата:

Тетраэдр с точкой внутри и два тетраэдра с общей гранью - вроде в обоих случаях пять точек расположены так, что никакие четыре не лежат в одной плоскости. Но аффинными преобразованиями эти два набора из пяти точек друг в друга не переводятся, поскольку у них выпуклая оболочка принципиально разная (тетраэдр и шестигранник). Почему для этих двух случаев должны получаться одинаковые ответы?

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

Другое дело, что общее положение пяти точек, может не гарантировать однозначной конфигурации возникающих плоскостей.
Возьмем, например, шесть вершин правильного шестиугольника. Никакие три из них не лежат на одной прямой. В этом смысле они являются точками общего положения. В то же время, число областей, на которые разбивается плоскость, прямыми, проходящими через каждую пару точек, очевидно меньше, чем в случае шести точек "более общего положения".

Вполне вероятно, что такая же картина может быть и обсуждаемой задаче.
Так, в конфигурации, предложенной уважаемым ИСН, число областей, разумеется, обязано быть кратно четырем (из соображений симметрии). В то же время, я пока не вижу, что мешает возникновению 106-и областей при ином начальном расположении точек.
Единственное, что на данный момент строго доказано - это оценка сверху.

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

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

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

Боюсь, что я плохо выразился и Вы меня не поняли. Когда я писал про тетраэдры, то имел в виду множества их вершин. То есть писал я, фактически, про точки.

-- Чт авг 23, 2012 10:32:05 --

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

А почему в случае плоскости получается всегда одно и тоже число областей (независимо от вида выпуклой оболочки)?

А с чего Вы взяли, что это так? Наоборот, VAL заметил, что это не так для шести точек на плоскости.

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

Да и для четырёх тоже не так. Нетрудно посчитать, что вершины квадрата дают 16 областей на плоскости, а вершины треугольника + точка в центре треугольника - 18 областей. В обоих случаях никакие три точки не лежат на одной прямой!

[Alexander Evnin]

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

Аналогично, в пространственном случае имеем следующее. Никакие 4 точки не лежат в одной плоскости и если проводить всевозможные плоскости через тройки этих точек, то любые три из них имеют общую точку, но никакие четыре не имеют общей точки, отличной от исходных.
Мне кажется, что для таких точек количество частей будет максимальным.

Наверное, более корректно было бы сформулировать задачу следующим образом.
Имеется 5 точек. Через каждые три из них проведена плоскость. На какое наибольшее (по всем пятёркам точек) количество частей эти плоскости могут разбить пространство?

Общий случай для плоского варианта этой задачи имеется в книге
L. Comtet. Advanced Combinatorics.

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

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

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

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

Аналогично, в пространственном случае имеем следующее...

Ну Вы даёте! Я ещё в четвёртом сообщении темы спросил, что понимается под "общим положением", а Вы только сейчас ответили. Причём, как выяснилось из дискуссии, вопрос был вполне правомерным и уточнение существенным!!!

-- Чт авг 23, 2012 12:13:59 --

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

Имеется 5 точек. Через каждые три из них проведена плоскость. На какое наибольшее (по всем пятёркам точек) количество частей эти плоскости могут разбить пространство?

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

[Alexander Evnin]

Цитата:

Аккуратно разбираете эти 4 варианта

Лично мне не хватает геометрического (пространственного) воображения, чтобы это сделать!
Но хотелось-то решить задачу в общем случае (для $n$ точек).
Ведь если мы решаем задачу о числе областей после проведения $n$ плоскостей общего положения, то
никакого геометрического воображения не требуется, как и перебора различных возможных конфигураций.

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

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

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

И этот вопрос можно тоже поисследовать. Опять же разобрав все 4 варианта!

Кропотливо это всё

(Оффтоп)

Помню, давным-давно в военкомате нам давали какой-то тест на пространственное воображение. Мы всё-таки из физматшколы были туда приписаны, и наш военкомат был один из редких, который набирал на службу в частях РЛС, операторов радаров и т. п. Так вот, тот тест выявил у меня полное отсутствие оного воображение. Если меня действительно приспичит решать эту задачу, я постараюсь всё свести к алгебраическим методам

-- Чт авг 23, 2012 12:49:59 --

A153445 Вашо???

[Alexander Evnin]

Цитата:

...никакие четыре не имеют общей точки, отличной от исходных

Здесь вышло неточно. Следует уточнить, что четыре плоскости, о которых идёт речь, не имеют двух общих исходных точек! Общая точная формулировка оказывается чрезвычайно громоздкой. Не предложите ли более краткий вариант?

[VAL]

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

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

Аналогично, в пространственном случае имеем следующее. Никакие 4 точки не лежат в одной плоскости и если проводить всевозможные плоскости через тройки этих точек, то любые три из них имеют общую точку, но никакие четыре не имеют общей точки, отличной от исходных.
Мне кажется, что для таких точек количество частей будет максимальным.

Это, конечно, верно. Но... малосодержательно.
Очевидно, что в пространстве может не более 4-х точек "более общего положения".

Цитата:

Наверное, более корректно было бы сформулировать задачу следующим образом.
Имеется 5 точек. Через каждые три из них проведена плоскость. На какое наибольшее (по всем пятёркам точек) количество частей эти плоскости могут разбить пространство?

Склоняюсь к мысли, что для пяти точек общего положения ответ все же единственный.
Аргументация такая:
Тройки плоскостей, определенных тройками исходных точек пересекаются всего 15 точках.
Во-первых, это 5 исходных точек. В каждой из них сходится 6 плоскостей.
Во-вторых, это 10 точек, каждая из которых представляет собой пересечение прямой, заданной парой исходных точек, и плоскости, заданной тремя остальными точками. В этих точках пересекается по 4 плоскости. (В случае, рассмотренном ИСН, эти 10 точек суть середины ребер и центры граней исходного тетраэдра.)
Больше точек пересечения троек интересующих нас плоскостей просто нет.

Но в случае правильного тетраэдра с центром областей не может быть 106.
По-видимому при подсчете числа областей нужно учитывать не только особые точки, но и особое расположение линий пересечения плоскостей.
Каждая прямая, в которой пересекаются 3 плоскости уменьшает число областей на 2.
Тогда их должно получится $176-5\cdot12-10\cdot1-10\cdot2=86$ (вот и 86 получилось). Но я полагаю, что выпадения областей, обусловленные особыми точками и особыми прямыми, не являются независимыми. И правильный ответ все же 96.

[Alexander Evnin]

A153445 Да, здесь и формулировка неудачная (не объясняется, что понимается под точками общего положения) и результат, как я сейчас вижу, сомнительный.

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

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

Склоняюсь к мысли, что для пяти точек общего положения ответ все же единственный.

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

-- Чт авг 23, 2012 12:56:31 --

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

A153445 Да, здесь и формулировка неудачная (не объясняется что понимается под точками общего положения) и результат, как я сейчас вижу, сомнительный.

Аяяй! Надо Максалу написать, чтоб лучше за проектом следили!! Публикация сомнительных результатов в OEIS подрывает авторитет OEIS!!!

[VAL]

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

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

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