Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


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

Теперь докажем, что 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 балла

 

 


Страница: [[marathon:problem_76]]

marathon/problem_76.txt · Последние изменения: 2007/10/30 14:15 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006