一个构造问题：二进制序列的正交基

sunwukong

对正整数 n，n 位二进制序列共有 2^n 个： 000…000 000…001 000…010 000…011 …… 111…111 求一组 n 位二进制序列 X[1]、X[2]、……、X[k] ，使得 （一）这组数任意两个的“按位与”结果为 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[1]、X[2]、……、X[k] 所有两两“按位或”结果覆盖了不为零的 n 位二进制序列 （三）k 要最小 容易知道，k 的下限是 Ceil( sqrt(2^n - 1) )，（由 k^2>=2^n-1 求得），是否对所有的正整数 n，k 都能达到这个下限？ [ 本帖最后由 sunwukong 于 2008-9-5 16:34 编辑 ]

mathe

$n>=5$时不可能存在. 条件(2)要求$k>=sqrt(2^n-1)$,条件(1)要求$k<=n$

sunwukong

没考虑好，条件太严格了， 修改一下： 求一组 n 位二进制序列 X[1]、X[2]、……、X[k] ，使得 对任意一个从 1 到 2^n-1 之间的数字化成的 n 位二进制序列 A，A或者等于 X[1]、X[2]、……、X[k] 中的一个，或者存在 i、j（i <> j ），使得 X[ i ] AND X[ j ] = 000…000 ，（这里的 AND 为“按位与”） X[ i ] OR X[ j ] = A ，（这里的 OR 为“按位或”） 求 k 的最小值以及 X[1]、X[2]、……、X[k] 的值。