Конкурсная задача №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).
Докажем, что (*).
Здесь C(n,i) - биномиальные коэффициенты (C(n,i) = 0 при i>n).
Для n = 0 формула (*) очевидна. Пусть верна при некотором n.
Тогда F(k+1,n+1) = F(n,k) + F(n,k+1) =
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) ч.т.д.
В частности, .
Теперь докажем, что 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) = 22n-1.
Обсуждение
Можно получить формулу для 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 балла