一个构造问题：二进制序列的正交基
对正整数 n，n 位二进制序列共有 2^n 个：000…000
000…001
000…010
000…011
……
111…111
求一组 n 位二进制序列 X、X、……、X ，使得
（一）这组数任意两个的“按位与”结果为 0，即
X[ i ] AND X[ j ] = 000…000，i <> j（这里的 AND 为“按位与”）
（二）对任意一个从 1 到 2^n-1 之间的数字化成的 n 位二进制序列 A，存在 i,j，使得
X[ i ] OR X[ j ] = A ，（这里的 OR 为“按位或”，i ,j 可以相等）
或者换个说法：这组 n 位二进制序列 X、X、……、X 所有两两“按位或”结果覆盖了不为零的 n 位二进制序列
（三）k 要最小
容易知道，k 的下限是 Ceil(sqrt(2^n - 1) )，（由 k^2>=2^n-1 求得），是否对所有的正整数 n，k 都能达到这个下限？
[ 本帖最后由 sunwukong 于 2008-9-5 16:34 编辑 ] $n>=5$时不可能存在.
条件(2)要求$k>=sqrt(2^n-1)$,条件(1)要求$k<=n$ 没考虑好，条件太严格了，:L 修改一下：
求一组 n 位二进制序列 X、X、……、X ，使得
对任意一个从 1 到 2^n-1 之间的数字化成的 n 位二进制序列 A，A或者等于 X、X、……、X 中的一个，或者存在 i、j（i <> j），使得
X[ i ] AND X[ j ] = 000…000，（这里的 AND 为“按位与”）
X[ i ] OR X[ j ] = A ，（这里的 OR 为“按位或”）
求 k 的最小值以及 X、X、……、X 的值。
页:
[1]