Насколько я понимаю, задача взята не "с потолка", а представляет собой задачу вычисления хэш-функции, позволяющей отслеживать и исправлять ошибку величиной не более один бит в передаваемой битовой последовательности длины
, при этом считается, что сам хэш передаётся по надёжному каналу.
Итак, пусть у нас есть булев куб размерности
и нам нужно найти требуемую раскраску, используя
цветов. Это означает, что нужно построить функцию от
бит, возвращающую
-битное значение, причём значения функции при отличии аргумента не менее, чем на один, но не более, чем на два бита, должны быть различными (т.к. входные строки, отличающиеся на один бит, можно рассматривать как любую вершину и точку, соседнюю с ней, а отличающиеся на два бита - как две точки, соседние с какой-то вершиной; в обоих случаях выходные строки должны быть различными).
Попробуйте найти искомую функцию
в виде:
где
- операция
, а
- неизвестные подмножества множества
, т.е можно считать, что это подмножества исходных битов (не значений этих битов!, а самих битов как неких физических объектов, ячеек памяти, например). При этом нужно, чтобы выполнялись два свойства:
1) Каждый из
битов принадлежит хотя бы одному из множеств
(иначе при изменении этого бита ничего не изменится).
2) Для любых двух различных битов наборы множеств, которым они принадлежат, отличаются (иначе при смене значений двух этих битов в каждой сумме
произойдёт взаимоисключение или вообще ничего не произойдёт).