** Конкурсная задача №76 **  (8 баллов)   

На какое наибольшее число частей могут разбивать n-мерное пространство 2n
гиперплоскостей, имеющих общую точку?

Примечание:\\
Гиперплоскоскостью называется плоскость, размерность которой на единицу 
меньше размерности пространства.


** Решение **

Обозначим через f(k,n) наибольшее число частей, на которые могут разбивать 
k-мерное пространство n гиперплоскостей, имеющих общую точку, а через F(k,n) -
число частей, на которые разбивают k-мерное пространство n гиперплоскостей
общего положения (всякие m пересекаются по плоскости размерности k-m, если
m не превосводит k, и не имеют общей точки, если m>k).\\
Ясно, что F(k,0) = 1, а F(0,n) = 1.\\
Кроме того, для F(k,n) справедлива рекуррентая формула:\\ 
F(n+1,k+1) = F(n,k) + F(n,k+1).\\
В самом деле, добавляемая n+1-я гиперплоскость, пересекает n предыдущих
гиперплоскостей. При этом к уже имеющемуся разбиению из F(k+1,n) частей 
добавляется столько частей, на сколько разбивается новая гиперплоскость,
пересекаясь с уже имеющимися, т.е. F(k,n).\\
Докажем, что <m>F(k,n) = sum{i=0}{k}{C(n,i)}</m> (*).\\
Здесь C(n,i) - биномиальные коэффициенты (C(n,i) = 0 при i>n).
Для n = 0  формула (*) очевидна. Пусть верна при некотором n.\\
Тогда F(k+1,n+1) = F(n,k) + F(n,k+1) =\\  
<m>sum{i=0}{k}{C(n,i)} + sum{i=0}{k+1}{C(n,i)} =</m>\\
C(n,0) + (C(n,0) + C(n,1))+ (C(n,1) + C(n,2)) + ... + (C(n,k) + C(n,k+1))  =\\
C(n+1,0) + C(n+1,1) + C(n+1,2) + ... + C(n+1,k+1) ч.т.д.\\
В частности, <m>F(k-1,2k-1) = 1/{2} sum{i=0}{2k-1}{C(2k-1,i)} = 2^{2k-2}</m>.

Теперь докажем, что f(k,n) = 2F(k-1,n-1).\\
Для этого зафиксируем одну из n гиперплоскостей, проходящих через данную точку.
По каждую сторону от зафиксированной гиперплоскости располагается ровно 
половина из f(k,n) частей.  Проведем еще одну гиперплоскость, параллельную
зафиксированной. При пересечении с остальными гиперплоскостями на новой
гиперплоскости возникнет F(k-1,n-1) частей разбиения, биективно соответствующих
половине из частей f(k,n) частей.

Окончательно получаем: f(n,2n) = 2F(n-1,2n-1) = 2<sup>2n-1</sup>.


** Обсуждение **

Можно получить формулу для f и не прибегая к связи с F, а напрямую, опираясь
на рекуррентное соотношение f(k+1,n+1) = f(k,n) + f(k,n+1) и начальные 
условия f(k,1) = 2 и f(1,n) = 2.\\
Однако обходной маневр, изложенный в решении, позволяет упростить обоснование
достижимости полученных значений f(k,n). Для того чтобы число частей разбиения
было максимальным, достаточно, чтобы на гиперплоскости, параллельной любой
из данных, индуцировалось разбиение гиперплоскостями (размерности k-2) общего
положения.


** Награды **

Задача №76 то ли не приглянулась, то ли не поддалась марафонцам.
В итоге я получил всего два решения. 
За правильное решение задачи Виктор Филимоненков и Анатолий Казмерчук 
получают по 8 призовых баллов.

** Эстетическая оценка задачи - 4.5 балла **