Разбиение множества гиперплоскостью Всем доброго дня, ночи… и вообще! Несколько предварительных слов. Формулируемое ниже утверждение относится к разбиениям множеств в $ E^n $ и выглядит очевидным. Мне не без труда удалось найти его несложное комбинаторное доказательство (обобщение которого позволяет уточнять приведенную границу). Выкладываю этот результат 1)как задачу с предложением ознакомиться и порешать, 2) с просьбой проанализировать на предмет тривиальности, а также на предмет прямого следования из известных результатов. За эту задачу я взялся по необходимости – оценка нужна, а на что опереться, не нашел. Формулировка утверждения. Пусть $ I^n $ – множество векторов из $ E^n $ (n-мерное евклидово пространство) со значениями компонент из $ I= \lbrace -1,0,1 \rbrace. $ Для произвольных $ X \subseteq I^n, h \in I^n $ введем обозначения: $ X_{-1}(h)= \lbrace x \in X | (x,h) <0 \rbrace $, $ X_0(h)= \lbrace x \in X | (x,h)=0 \rbrace $ , $ X_1(h)= \lbrace x \in X | (x,h)>0 \rbrace$ ; $ N_i(X,h) = | X_i(h)|, i \in I; N(X)= \sum_i N_i(X,h) = |X| . $ Тогда при всех $ X (|X| \ge 4) $ выполняется неравенство $ min_h max_i N_i(X,h)/ N(X) \le 1/2 $ .http://www.mathforum.ru/forum/read/1/64905/64905/#64905Tue, 12 May 2026 16:28:29 +0300 Phorum 5.2.10 http://www.mathforum.ru/forum/read/1/64905/64955/#64955 Не учелhttp://www.mathforum.ru/forum/read/1/64905/64955/#64955
Цитата
yog-urt
при всех n существует множество из 3-х элементов, для которого данная оценка не верна.
Этот момент в вашем доказательстве не учтен.
Действительно, это очень серьезный косяк и легко устранить его боюсь не удастся. Доказательство ошибочно. Если честно, то я позабыл об условии $|X|\ge4$, да и базу индукции даже не проверял, предполагая что неравенство верно для любой мощности. Просто вопиющая безалаберность с моей стороны. Большое спасибо!]]> anton25 Высшая математикаThu, 09 May 2013 00:25:23 +0400 http://www.mathforum.ru/forum/read/1/64905/64951/#64951 Добавление - вопросhttp://www.mathforum.ru/forum/read/1/64905/64951/#64951при всех n существует множество из 3-х элементов, для которого данная оценка не верна.
Этот момент в вашем доказательстве не учтен.]]> yog-urt Высшая математикаWed, 08 May 2013 23:58:34 +0400 http://www.mathforum.ru/forum/read/1/64905/64941/#64941 С благодарностью…http://www.mathforum.ru/forum/read/1/64905/64941/#64941 двойственных оценок для построения алгоритмов я как-нибудь проиллюстрирую на примере интересных и полезных задач.
Вопрос о тривиальности я ставил не в смысле сложности (значимости), а именно в смысле возможности полной тривиальности для сведущего (типа «чего тут мусолить, когда и так ясно: рассекли пополам и положили набок на подходящие точки» или «да это уже было известно в 18 веке»). Прихожу к мысли, что, хоть результат «промежуточный», но три строчки обоснования ему уделить придется.
Еще раз спасибо.

PS Момент в доказательстве, который требует осмысления: это универсальность (?) представления множеств X.]]> yog-urt Высшая математикаWed, 08 May 2013 23:16:46 +0400 http://www.mathforum.ru/forum/read/1/64905/64935/#64935 Небольшая добавкаhttp://www.mathforum.ru/forum/read/1/64905/64935/#64935$\frac{1}{2}$ на меньшее число (разумеется предварительно доказав базу индукции для этого числа при некотором $n$), то оно полностью сохранится. Т.е., например, можно для какого-то $n$ посчитать верхнюю границу на ЭВМ и тогда полученный ответ будет являться верхней границей при всех $N>n$]]> anton25 Высшая математикаWed, 08 May 2013 22:22:39 +0400 http://www.mathforum.ru/forum/read/1/64905/64926/#64926 ...http://www.mathforum.ru/forum/read/1/64905/64926/#64926Много разных обозначений, но насколько я понял требуется доказать, что $min_{h\inI^n}\left(max_{i\inI}\frac{|X_i(h)|}{|X|}\right)\le\frac{1}{2}$, где $|\,|$ обозначает мощность. Если так, то похоже прокатывает обычная мат. индукция по размерности пространства:
При $n=2$ непосредственно проверяем и убеждаемся. Предположим, что неравенство справедливо при $n=k$ с искомым $h$ (или фиксированным если их несколько). Тогда при $n=k+1$ имеем $I^{k+1}=A_{-1}\cupA_0\cupA_1$, где $A_i=I^k\times\{i\}$, $i\inI$. Пусть $H=h\times\{0\}$ и пусть $X=X^{A_{-1}}\cupX^{A_0}\cupX^{A_1}$, где $X^{A_i}\subseteqA_i$. Тогда для любых $i,j\inI$ в силу предположения и того факта, что для любого $v\inI^{k+1}$ скалярное произведение $(v,H)$ не зависит от последних компонент векторов, получаем $|X_i^{A_j}(H)|\le\frac{1}{2}\cdot|X^{A_j}|$, откуда $\frac{|X_i(H)|}{|X|}=\frac{|X_i^{A_{-1}}(H)|+|X_i^{A_0}(H)|+|X_i^{A_1}(H)|}{|X^{A_{-1}}|+|X^{A_0}|+|X^{A_1}|}\le\frac{\frac{1}{2}\cdot|X^{A_{-1}}|+\frac{1}{2}\cdot|X^{A_0}|+\frac{1}{2}\cdot|X^{A_1}|}{|X^{A_{-1}}|+|X^{A_0}|+|X^{A_1}|}=\frac{1}{2}$. Индукция завершена.

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

P.S. Надеюсь меня простят за вольности в обозначениях вроде $I^k\times\{i\}$ и $h\times\{0\}$ и надеюсь их смысл понятен.

P.S.2 Изменения при редактировании: база не $n=4$, а, конечно, $n=2$]]> anton25 Высшая математикаWed, 08 May 2013 20:45:18 +0400 http://www.mathforum.ru/forum/read/1/64905/64905/#64905 Разбиение множества гиперплоскостьюhttp://www.mathforum.ru/forum/read/1/64905/64905/#64905Несколько предварительных слов. Формулируемое ниже утверждение относится к разбиениям множеств в $ E^n $ и выглядит очевидным. Мне не без труда удалось найти его несложное комбинаторное доказательство (обобщение которого позволяет уточнять приведенную границу). Выкладываю этот результат 1)как задачу с предложением ознакомиться и порешать, 2) с просьбой проанализировать на предмет тривиальности, а также на предмет прямого следования из известных результатов. За эту задачу я взялся по необходимости – оценка нужна, а на что опереться, не нашел.
Формулировка утверждения.
Пусть $ I^n $ – множество векторов из $ E^n $ (n-мерное евклидово пространство) со значениями компонент из $ I= \lbrace -1,0,1 \rbrace. $ Для произвольных $ X \subseteq I^n, h \in I^n $ введем обозначения: $ X_{-1}(h)= \lbrace x \in X | (x,h) <0 \rbrace $, $ X_0(h)= \lbrace x \in X | (x,h)=0 \rbrace $ , $ X_1(h)= \lbrace x \in X | (x,h)>0 \rbrace$ ; $ N_i(X,h) = | X_i(h)|, i \in I; N(X)= \sum_i N_i(X,h) = |X| . $
Тогда при всех $ X (|X| \ge 4) $ выполняется неравенство $ min_h max_i N_i(X,h)/ N(X) \le 1/2 $ .]]> yog-urt Высшая математикаWed, 08 May 2013 01:26:46 +0400