encontrar un grupo de números de N más bajos para que no 2 pares tienen el mismo bit a bit o

Question

Estoy tratando de encontrar el grupo más bajo de N números (es decir, N = 1000) para que no 2 pares del grupo tienen el mismo bit-wise o.

más específico que un grupo

$A = \{a_1,a_2,a_3,..,a_N\} $

tal que para cualquier $ 1\le i,j,k,m \le n $

$ i \ne j , k \ne m $

$OR(a_i,a_j) \ne OR(a_k,a_m)$

$a_1 .. a_n$ más bajo posible

ejemplo para N = 3

A = {0,1,2}

como Or(0,1) = 1, Or(0,2) = 2, Or(1,2) = 3

Answer 1

La pregunta "¿Podemos encontrar $1000$ números en el rango de $[0,2^{n}-1]$?" puede ser reformulado como "que Podemos encontrar en $1000$ subconjuntos de a $\{1,\dots, n\}$ tal que

• No existen distintos $A,B,C,D$ $A \cup B=C \cup D$
• No existen distintos $A,B,C$ $A \cup B=A \cup C$

En extremal la teoría de conjuntos, así como una colección de subconjuntos se llama fuertemente la unión libre de la familia. Calderero y Shearer tienen algunos asintótica construcciones de bastante grande (aproximadamente el $2^{0.31n}$ subconjuntos) de las colecciones de la satisfacción de esta propiedad. No estoy muy familiarizado con los detalles de las construcciones, pero podría ser posible extraer algo en el no-régimen asintótico de ellos.

Answer 2

La reescritura de un inicio: Si se siguen con avidez, obtendrá el conjunto de $2^k$. Dado que usted ha $0$$1$, usted puede tener cualquier número de $n$ $1$ $2^0$ posición debido a $n \text{ or } 0 = n \text{ or } 1$. Del mismo modo, usted no puede tener un número con un $1$ $2^1$ posición. $3$ viole esta, sino $4$ es aceptable. Ahora usted no puede tener cualquier otro número con un $1$ $2^2$ posición.

Sería mejor (obtener un menor número de arriba) para que cada número tiene más bits. Dado $N$ números, usted tiene $\frac 12N(N-1)$ pares que deben tener diferentes ORs. Usted puede dejar que cada uno tiene $ b$ uno bits y $c$ cero bits. Usted necesita por lo menos ${b+c \choose b}=N$. Entonces, si todas las Sro son diferentes en casa. Los codiciosos estrategia anterior es $b=1,c=N$ debe ser un buen patrón de los números con las $b$ bits que garantiza que no hay colisiones, pero no he encontrado. Me la práctica, creo que elegiría $b$$c$, todos los $N$ números de ha $b$ uno bits y escoger al azar de la ${b+c \choose b}$ e intentarlo. Si falla demasiadas veces, aumentar el $c$ e inténtelo de nuevo.