Булев куб

[Sonic86]

serval в сообщении #489750 писал(а):

Вот эти векторы для $N=6$ в порядке их появления при переборе сочетаний:

Ура! Молодец! Только, вектор

serval в сообщении #489750 писал(а):

$(0,0,0,0,0,0)$

левый
Видите закономерность теперь? Если нет, то такая подзадача:
Дан вектор $\bar x$ длины $n$ с $k$ единицами из упорядоченного списка. Найти вектор, следующий за вектором $\bar x$ в списке.

[serval]

Цитата:

левый

Это была заготовка для "правого". Исправил.

Цитата:

такая подзадача

Даже приблизительно не понял намека

Цитата:

А вопрос в чём?

1. Любые ли $5$ из этих $20$ векторов линейно независимы?

[ИСН]

Нет, и я об этом уже говорил:
(1,1,1,0,0,0)+(0,0,0,1,1,1) = (1,0,1,0,1,0)+(0,1,0,1,0,1)

-- Ср, 2011-10-05, 17:53 --

Даже не любые 4, как видим.

[INGELRII]

serval
Вообще, легко заметить, что из условия "дан $N$-мерный булев гиперкуб, мы берем все те его вершины, в координатной записи которых ровно $k$ единиц" следует, что все такие вершины будут лежать на $N-1$ мерном сечении этого куба гиперплоскостью той же размерности $N-1$, перпендикулярной главной диагонали куба.

То есть они являют собой вершины некоторого $N-1$ мерного многогранника. А такие вершины в общем случае трудновато упорядочить линейно! По крайней мере таким способом, который можно было бы назвать естественным. Ну по крайней мере назвать естественным и не покривить при этом душой )))

Уравнение секущей гиперплоскости будет, кстати, $x_1+x_2+...+x_N=3$ Гениально и просто.

[serval]

Заблудились. Эти $20$ вершин придутся на всю поверхность куба, а мне нужно на одну грань.

Цитата:

я об этом уже говорил

Тогда:
2. Разбить эти вершины на группы по принадлежности граням.

Цитата:

следует, что все такие вершины будут лежать на $N-1$ мерном сечении этого куба гиперплоскостью той же размерности $N-1$, перпендикулярной главной диагонали куба.

Это очень интересное следствие, но его-то я и не вижу. Можете изложить последовательно?
К тому же, я могу указать, по крайней мере, два множества таких точек лежащих каждое в своем сечении (их векторы нормали различны).

Цитата:

Уравнение секущей гиперплоскости будет, кстати, $x_1+x_2+...+x_N=3$

Т.е. эта плоскость не проходит через начало координат?

[Sonic86]

serval в сообщении #489809 писал(а):

Т.е. эта плоскость не проходит через начало координат?

Нет.

[serval]

Цитата:

Нет.

(Оффтоп)

Велик и могуч русский язык

[Sonic86]

serval в сообщении #489812 писал(а):

Велик и могуч русский язык

Эта плоскость не проходит через начало координат Извините, я просто уже в контекст въехал и часть текста начинаю опускать

[ИСН]

serval, у Вас каша какая-то в вопросах. (Это не обязательно негативная характеристика; у исследовательских задач такое бывает.)
То грани нужны, то плоскости, проходящие через начало координат (каковыми являются некоторые грани, но большинство-то нет), то какая-то окружность, с бородою и с ружьём! Make up your mind, что ли, ну.
В одну двумерную грань (я уверен, что это уже кем-то говорилось, но лень искать) входят максимум две такие вершины, и они-то, конечно, линейно независимы. В одну пятимерную - входит дофига, и пример линейной зависимости между ними легко можно переделать из моего примера.

[serval]

Цитата:

у Вас каша какая-то в вопросах

Если с вашей общей помощью мне удастся ее упорядочить, то ответ, возможно, я найду сам

Цитата:

То грани нужны, то плоскости, проходящие через начало координат

Чтобы разобраться с плоскостями сначала я пытаюсь разобраться с гранями: выделить группы по $N-1$ вершине грани чтобы добавив к каждой из таких групп начало координат задать искомые плоскости.

Цитата:

то какая-то окружность

Разве принадлежность вершин одной грани и равенство длин их радиус-векторов не является достаточным условием того, что они лежат на окружности?

Цитата:

входит дофига

Как их сгруппировать по указанным мной условиям?

Цитата:

пример линейной зависимости

Пример - это хорошо, но недостаточно. Мне нужен метод.

[INGELRII]

serval
Ну есть у нас точки, про которые мы знаем, что их координаты состоят из нулей и единиц, причем единиц ровно 3. Так чему равна сумма всех координат? 3. Отсюда и уравнение приведенной мною гиперплоскости! Ее нормальный вектор имеет координаты ${1,1,...,1}$. Это и есть главная диагональ куба. Вот.

Вы, само собой, можете выделить в этой гиперплоскости подпространства, по которым точки будут сгруппированы. Да, эти подпространства будут иметь между собой самые разные углы - по вашей прихоти, в том числе и прямые, и ничего удивительного в этом нет. (Замечу, что в общем случае две гиперплоскости в многомерном пространстве имеют между собой не один, а несколько углов)

Но все эти взятые вами из любых соображений грани все равно будут лежать в "моей" гиперплоскости.

И повторюсь, что все ваши точки таким образом являются вершинами многомерного многогранника. Как уж вы собираетесь упорядочить их линейно - не представляю. Ведь даже вершины банального додекаэдра в три-дэ можно упорядочить несколькими способами, и потом с пеной у рта спорить, чей способ является истинно пролетарским, а чей нет. Что уж говорить о высших размерностях!

Вы придумали такую идею: разбить ту самую гиперплоскость на подпространства (грани) и внутри них упорядочивать (опять же: как?). Но тогда вы тут же встанете перед вопросом: а как упорядочивать сами грани? Из каких соображений? Who watches the Wathcmen? (с)

С другой стороны, если отречься от попыток сделать этот порядок естественным, то вариантов сразу появляется тьма. Мой фаворит - лексикографический порядок. Да, "соседние" по нему вершины будут порой разделены между собой в реальности большим расстоянием. И одной грани принадлежать они не будут. Но! Линейный порядок налицо: смотрим на две вершины и говорим "эта вот предшествует той в списке".

А если вы по-прежнему хотите заполучить некий идеальный платоновский порядок в этой задаче, сразу говорю: нет его.

[serval]

Спасибо, мне нужно подумать.