Раскрасить булев куб в (n+1) цвет

[antake]

Здравствуйте!

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

Вот здесь http://ru-math.livejournal.com/708956.html в комментариях пишут, что можно раскрасить в $(n+1)$ цвет, если $n=2^{k}-1$.

Мне нужно раскрасить хотя бы в линейное по n число цветов. На крайний случай можно даже в полиномиальное)

Спасибо.

[Dave]

Так а в чём проблема? Если Вы знаете раскраску для $2^k-1$, то по заданному $n$ подбираете натуральное число $m$ так, чтобы $2^{m-1}\leqslant n \leqslant 2^m-1$ и используете раскраску куба размерности $2^m-1$. Для неё понадобится $2^m$ цветов, что не больше, чем $2n$, т.е. линейно по $n$.
Другое дело - если раскраску для $2^k-1$ не знаете. Тогда, так и быть, подскажу .
Нижняя оценка $n+1$, вообще говоря, не всегда достижима. Например, при $n=2$ нужно не менее $4$ цветов.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

antake, наберите, пожалуйста, формулы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[Toucan]

Вернул.

[antake]

Уезжал в отпуск, поэтому молчал.
Dave, спасибо, я как раз случай $2^{k}-1$ и не могу решить. Если подскажете, буду очень благодарен!

[Dave]

Насколько я понимаю, задача взята не "с потолка", а представляет собой задачу вычисления хэш-функции, позволяющей отслеживать и исправлять ошибку величиной не более один бит в передаваемой битовой последовательности длины $n$, при этом считается, что сам хэш передаётся по надёжному каналу.
Итак, пусть у нас есть булев куб размерности $n=2^k-1$ и нам нужно найти требуемую раскраску, используя $n+1=2^k$ цветов. Это означает, что нужно построить функцию от $2^k-1$ бит, возвращающую $k$-битное значение, причём значения функции при отличии аргумента не менее, чем на один, но не более, чем на два бита, должны быть различными (т.к. входные строки, отличающиеся на один бит, можно рассматривать как любую вершину и точку, соседнюю с ней, а отличающиеся на два бита - как две точки, соседние с какой-то вершиной; в обоих случаях выходные строки должны быть различными).
Попробуйте найти искомую функцию $F(x_1,x_2,\dots,x_{2^k-1})=(f_1,f_2,\dots,f_k)$ в виде:

$$f_1=\bigoplus_{i \in A_1} {x_i},$$

$$f_2=\bigoplus_{i \in A_2} {x_i},$$

$$\quad \dots$$

$$f_k=\bigoplus_{i \in A_k} {x_i},$$

где $\oplus$ - операция $XOR$, а $A_1,A_2,\dots,A_k$ - неизвестные подмножества множества $\{1,2,\dots,2^k-1\}$, т.е можно считать, что это подмножества исходных битов (не значений этих битов!, а самих битов как неких физических объектов, ячеек памяти, например). При этом нужно, чтобы выполнялись два свойства:
1) Каждый из $2^k-1$ битов принадлежит хотя бы одному из множеств $A_i$ (иначе при изменении этого бита ничего не изменится).
2) Для любых двух различных битов наборы множеств, которым они принадлежат, отличаются (иначе при смене значений двух этих битов в каждой сумме $\oplus$ произойдёт взаимоисключение или вообще ничего не произойдёт).

[antake]

Dave, огромное спасибо! Буду разбираться)
Задача у меня из области расшифровки булевых функций, я не криптограф. Кстати, а Вы не знаете, а это опубликовано где-либо?

[Dave]

Пожалуйста. Алгоритм придумал сам, по поводу публикации не подскажу. Но наверняка этим простейшим случаем уже кто-то занимался, раз уже более 50 лет назад придумали гораздо более сложные Коды Рида — Соломона.

[antake]

Спасибо!
На спецсеме дважды рассказывали коды Рида-Соломона, что ж я их прослушал((