Гиперплоскости в R^n

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

Пусть $n,k >0$ --- натуральные числа и $a_1, \ldots, a_k \in \mathbb{R}^n$. Пусть в $\mathbb{R}^n$ также заданы $k$ гиперплоскостей, вектора нормалей к которым равны $a_1, \ldots, a_k$ соответственно. Доказать что

1) Количество частей, на которые эти гиперплоскости делят $\mathbb{R}^n$, не превосходит количества линейно независимых подмножеств множества $\{ a_1, \ldots, a_k \}$ (пустое множество также считаем линейно независимым).

2) Если никакие две из данных гиперплоскостей не совпадают и никакие $n+1$ не пересекаются в одной точке, то количество частей, на которые эти гиперплоскости делят $\mathbb{R}^n$, равно количеству линейно независимых подмножеств множества $\{ a_1, \ldots, a_k \}$.

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

Доказать, что максимальное количество частей, на которые $k$ гиперплоскостей могут поделить $\mathbb{R}^n$, равно $2^k$ при $k \leqslant n$ и $\sum_{i=0}^n C_k^i$ при $k > n$ (то есть равно количеству подмножеств $k$-элементного множества, содержащих не более $n$ элементов).

Задача, конечно, является тривиальным следствием предыдущей, но может быть решена и независимо от неё.

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

Жаль, что никто не хочет решать.

Может, так сформулировать?

Доказать, что если $k \in \mathbb{N}$, то количество частей, на которые $k$ прямых могут поделить плоскость, не превосходит

$$ \frac{k^2 + k + 2}{2} $$

причём этот максимум достигается.

[bobo]

Профессор Снэйп писал(а):

Доказать, что если $k \in \mathbb{N}$, то количество частей, на которые $k$ прямых могут поделить плоскость, не превосходит

$$ \frac{k^2 + k + 2}{2} $$

причём этот максимум достигается.

Буду доказывать, что наибольшее число частей равно $\frac{k^2+k+2}{2}$.
Действуем по индукции. При $k=1$ все ясно. Пусть мы провели $k=m$ прямых, никакие 3 не пересекаются в 1-й точке и никакие 2 не параллельны, удовлетворяющих предположению. Проведем еще одну прямую, не параллельную ни одной из $m$ построенных и не проходящую через точки пересечения. Тогда эта прямая рассечет каждую из $m+1$ частей пополам, т.е. их общее число увеличится на $m+1$ : $\frac{m^2+m+2}{2}+m+1=\frac{(m+1)^2+(m+1)+2}{2}$.
Если же провести прямую параллельно одной из уже построенных или через узел, то ясно что прибавится меньше, чем $m+1$ частей.
А с гиперплоскостями я не в теме

[Kid Kool]

bobo писал(а):

Тогда эта прямая рассечет каждую из $m+1$ частей пополам , т.е. их общее число увеличится на $m+1$

Это неправда, иначе бы число частей увеличилось вдвое. Правильнее было бы сказать так: m прямых высекают на данной прямой $m+1$ отрезок, каждый из которых прибавляет не более одной новой части, если рассматривать их (отрезки) последовательно.

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

Доказать, что при $k \in \mathbb{N}$ количество частей, на которые $k$ плоскостей могут поделить $\mathbb{R}^3$, не превосходит

$$ \frac{k^3+5k+6}{6} $$

причём этот максимум достигается.

[Kid Kool]

Ну, это следует из доказанной задачи для плоскости. Здесь мы в индукционном переходе выделяем одну плоскость, оставшиеся плоскости высекают на ней не более $\frac{k^2 + k + 2}{2}$ частей. Если эти части рассматривать по очереди, то, поскольку каждая следующая прибавляет не более 1-ой новой области в пространстве, получаем, что всего прибавилось не более $\frac{k^2 + k + 2}{2}$ частей. Откуда и следует формула.

Добавлено спустя 25 минут 18 секунд:

Теперь примерно понятно, как доказывать задачу №1. Приду домой - отпишусь.

[bobo]

Kid Kool писал(а):

bobo писал(а):

Тогда эта прямая рассечет каждую из $m+1$ частей пополам , т.е. их общее число увеличится на $m+1$

Это неправда, иначе бы число частей увеличилось вдвое. Правильнее было бы сказать так: m прямых высекают на данной прямой $m+1$ отрезок, каждый из которых прибавляет не более одной новой части, если рассматривать их (отрезки) последовательно.

Не понял, при условиях когда никакие 2 не параллельны и никакие 3 не прохрдят ч-з одну точку их число и так увеличится в 2 раза: было $m+1$, стало - $2(m+1)$. Я просто хотел, что бы максимум достигался.

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

Kid Kool писал(а):

Теперь примерно понятно, как доказывать задачу №1. Приду домой - отпишусь.

Задачу номер 3, Вы хотели сказать. То есть задачу из второго сообщения в этой теме.

Добавлено спустя 3 минуты 56 секунд:

Вот, как не странно, похожая задача с тем же ответом:

Сколькими путями шахматный король может пройти из левого нижнего в правый верхний угол шахматной доски, если ему запрещено ходить по диагонали и назад (то есть он может ходить только либо на одну клетку вправо, либо на одну клетку вверх).

[maxal]

Профессор Снэйп писал(а):

Вот, как не странно, похожая задача с тем же ответом:

Сколькими путями шахматный король может пройти из левого нижнего в правый верхний угол шахматной доски, если ему запрещено ходить по диагонали и назад (то есть он может ходить только либо на одну клетку вправо, либо на одну клетку вверх).

Для доски $n\times n$ каждый путь короля - это перестановка $n$ вертикальных (неразличимых) ходов и $n$ горизонтальных ходов, а потому ответом будет

$${2n\choose n}.$$

[Kid Kool]

Профессор Снэйп писал(а):

Задачу номер 3, Вы хотели сказать. То есть задачу из второго сообщения в этой теме.

Задача 3 - это просто обобщение двух указанных Вами задач на общий случай (рассмотрен случай перехода от n=1 к 2 и от n=2 к 3, а общий случай - от k к k+1, используя формулу $C_n^k = C_{n-1}^k + C_{n-1}^{k-1}$). У меня есть соображения, как сделать таким способом именно задачу 1.

[maxal]

Профессор Снэйп писал(а):

Доказать, что максимальное количество частей, на которые $k$ гиперплоскостей могут поделить $\mathbb{R}^n$, равно $2^k$ при $k \leqslant n$ и $\sum_{i=0}^n C_k^i$ при $k > n$ (то есть равно количеству подмножеств $k$-элементного множества, содержащих не более $n$ элементов).

А какой смысл рассматривать отдельно случаи $k><n$? Справедлива общая формула:

$$\sum_{i=0}^n {k\choose i}.$$

[Kid Kool]

Ну что же, покажу как сделать индукционный переход.

Выделим вектор $a_k$, и спроецируем остальные векторы на соответвующую гиперплоскость A, получим векторы $b_i = a_i - a_k(a_i, a_k)$, где i от 1 до k-1 (считаем все векторы единичными). Далее, линейная комбинация векторов $b_i$ равна нулю, тогда и только тогда линейная комбинация с теми же коэффициентами векторов $a_i$ параллельна $a_k$. Поэтому есть взаимно-однозначное соответствие между линейно независимыми наборами из векторов $b_i$ и линейно независимыми наборами из векторов $a_i$, содержащими $a_k$. Повторяя рассуждения предыдущих задач и учтя, что линейно независимые наборы из $a_i$ распадаются на содержащие $a_k$ и не содержащие его, получаем то, что требуется.

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

maxal писал(а):

А какой смысл рассматривать отдельно случаи $k><n$? Справедлива общая формула:

$$\sum_{i=0}^n {k\choose i}.$$

Вы знаете, я с этими обозначениями не знаком. Верно ли, что

$$ {k \choose i} = \begin{cases} \frac{k!}{i!(k-i)!}, & i \leqslant k \\ 0, & i > k \end{cases} $$

или нет?

[maxal]

Профессор Снэйп, верно при условии, что $k\geq 0$ и $i\geq 0$. Более общая формула (для всех целых $k,\ i$) приведена в википедии. Но и это не предел на самом деле - определение биномиального коэффициента можно распространить на комплексные значения $k$ и т.д.