Número de vectores de manera que no hay dos subconjunto sumas son iguales

Question

Considerar la totalidad de los $10$tupla de vectores de cada uno de sus elementos es de $1$ o $0$. Es muy fácil seleccionar un conjunto $v_1,\dots,v_{10}= S$ de $10 dólares de dichos vectores, de modo que no hay dos subgrupos distintos de los vectores de $S_1 \subconjunto S$ y $S_2 \subconjunto S$ tienen la misma suma. Aquí $\sum_{v \en S_i} v$ asume simple elemento sabio, además de más de $\mathbb{R}$. Por ejemplo, si tomamos los vectores que son las columnas de la matriz identidad como $S$ esto va a hacer.

¿Cuál es el máximo número de vectores uno puede elegir que tienen esta propiedad? Hay un recuento de argumento que soluciona esto?

---

Una pequeña aclaración. La suma de dos vectores en este problema es otro vector.

---

Los registros actuales:

• Límite inferior: $19$. Primero dado por Brendan McKay más en MO.
• Límite superior: $30$. Primero dado por Brendan McKay más en MO.

---

Publicado a http://mathoverflow.net/questions/157634/number-of-vectors-so-that-no-two-subset-sums-are-equal

Answer 1

ACTUALIZACIÓN:

Mi mejor resultado (para los vectores con $10$ de los elementos) es de $18$.

(Pero Brendan McKay obtenidos conjunto de 19 de vectores: ver arriba citado http://mathoverflow.net enlace).

Ejemplo de $18$ suma-libre de vectores binarios:

$\qquad(0,0,0,0,1,1,0,0,1,1)$,
$\qquad(0,0,0,1,1,0,1,0,0,1)$,
$\qquad(0,0,1,1,0,1,0,0,1,1)$,
$\qquad(0,0,1,1,1,1,0,1,1,0)$,
$\qquad(0,1,0,0,1,1,1,0,1,0)$,
$\qquad(0,1,0,1,0,0,0,1,0,0)$,
$\qquad(0,1,0,1,0,0,1,1,1,0)$,
$\qquad(0,1,0,1,1,0,0,0,0,1)$,
$\qquad(0,1,1,0,1,0,0,1,0,1)$,
$\qquad(0,1,1,1,0,1,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,0,1)$,
$\qquad(1,0,0,0,1,0,1,1,1,1)$,
$\qquad(1,0,0,1,0,0,0,1,0,1)$,
$\qquad(1,0,1,0,0,1,0,1,0,1)$,
$\qquad(1,1,0,0,0,1,1,0,0,1)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,1,1,0,0,0,0)$,
$\qquad(1,1,1,0,1,0,1,0,0,0)$.

Ejemplo de $17$ suma-libre de vectores binarios:

$\qquad(0,0,0,0,0,0,1,1,1,1)$,
$\qquad(0,0,0,0,1,0,0,0,1,1)$,
$\qquad(0,0,0,1,1,1,1,0,1,0)$,
$\qquad(0,0,1,1,1,0,0,0,1,1)$,
$\qquad(0,1,0,1,1,1,0,1,0,1)$,
$\qquad(0,1,1,0,0,0,0,1,1,1)$,
$\qquad(0,1,1,1,0,0,0,1,1,0)$,
$\qquad(0,1,1,1,0,0,1,0,1,0)$,
$\qquad(1,0,1,1,0,0,0,1,0,0)$,
$\qquad(1,0,1,1,1,0,0,0,0,1)$,
$\qquad(1,0,1,1,1,0,0,1,1,0)$,
$\qquad(1,1,0,0,0,1,0,0,0,0)$,
$\qquad(1,1,0,0,1,0,0,0,1,1)$,
$\qquad(1,1,0,1,0,0,1,0,0,0)$,
$\qquad(1,1,0,1,0,0,1,1,0,0)$,
$\qquad(1,1,1,0,1,1,1,1,0,0)$,
$\qquad(1,1,1,1,1,1,1,1,0,1)$.

Y el ejemplo de $11$ suma-libre de vectores binarios (solo por curiosidad):

$\qquad(1,0,0,0,0,0,0,0,0,0)$,
$\qquad(0,1,0,0,0,0,0,0,0,0)$,
$\qquad(0,0,1,0,0,0,0,0,0,0)$,
$\qquad(0,0,0,1,0,0,0,0,0,0)$,
$\qquad(0,0,0,0,1,0,0,0,0,0)$,
$\qquad(0,0,0,0,0,1,0,0,0,0)$,
$\qquad(0,0,0,0,0,0,1,0,0,0)$,
$\qquad(0,0,0,0,0,0,0,1,0,0)$,
$\qquad(0,0,0,0,0,0,0,1,1,0)$,
$\qquad(0,0,0,0,0,0,0,1,0,1)$,
$\qquad(0,0,0,0,0,0,0,0,1,1)$.

---

Por $3,4,5,6,7,8,9,10$-dimensiones de los vectores de mis mejores resultados son de $4,5,7,9,12,14,16,18$ en consecuencia.

Answer 2

Un SSD-secuencia es una secuencia de enteros positivos números en los que los distintos subconjuntos de distintas sumas de dinero. Si llenamos nuestra vectores con las representaciones binarias de los elementos de una secuencia, que claramente final con una suma disjuntos conjunto de vectores. Para istance, tomando el SSD-secuencia de $3,5,6,7$ tenemos que $011,101,110,111$ son cuatro suma disjuntos vectores en $\{0,1\}^3$. Erdos conjeturó que $$M_n = \min\{\max(S)\;|\; S \mbox{ es un SSD secuencia de longitud } n\}$$ satisface $M_n \geq c\cdot 2^n$ constantes $c$, y el problema sigue abierto. Por otro lado, es fácil ver que $M_n\leq\frac{1}{2}2^n$ simplemente tomando potencias de dos (o la matriz de identidad en nuestro problema inicial). Bohman demostrado en 1996 que el $k$ elementos $s_i=a_k-a_{k-i}$ son un SSD, donde $1\leq i\leq k$ y $\{a_n\}_{n\in\mathbb{N}}$ es el Conway-Tipo de secuencia $$ 0, 1, 2, 4, 7, 13, 24, 44, 84, 161, 309, 594, 1164, 2284, 4484, 8807, 17305, 34301, 68008, 134852, 267420, 530356, 1051905, 2095003, 4172701, 8311101, 16554194, 32973536, 65679652, 130828948, 261127540, 521203175, 1040311347, 2076449993, \ldots$$ definido por $a_0=0,a_1=1$ y $$ a_{n+1} = 2a_n - a_{n-\lfloor\frac{1}{2}+\sqrt{2n}\rfloor}. $$ Esto le dio a la envolvente de $M_n\leq 2^{n-2}$ para $n\geq 20$, para istance. Tomando $k=11$ obtenemos el once elementos SSD conjunto: $$\{594,593,592,590,587,581,570,550,510,433,285\}$$ y tomando representaciones binarias tenemos once suma disjuntos vectores en $\{0,1\}^{10}$ - en general, $n+2$ suma-discontinuo vectores en $\{0,1\}^n$ para $n\geq 20$ - no tantos, pero aún mejor que el trivial obligado.

Es evidente que estamos desperdiciando una gran cantidad de información, ya que, por istance, $\{3,4,5,6,8\}$ no es un SSD (debido a $5+6=8+3$), pero las representaciones binarias de $\{3,4,5,6,8\}$ dar un cinco-elementos de suma disjuntos conjunto de vectores en $\{0,1\}^4$.

Ya hay $4$ suma-discontinuo vectores en $\{0,1\}^3$, una inteligente-tensor de truco da que hay, al menos, $\left\lfloor\frac{4n}{3}\right\rfloor$ suma-discontinuo vectores en $\{0,1\}^n$. En el caso $n=10$, estos trece vectores son: $$\begin{array}{*10{c}} 1,0,0,0,0,0,0,0,0,0\\ 0,1,1,0,0,0,0,0,0,0\\ 0,1,0,1,0,0,0,0,0,0\\ 0,1,0,0,0,0,0,0,0,0\\ 0,0,1,1,0,0,0,0,0,0\\ 0,0,0,0,1,1,0,0,0,0\\ 0,0,0,0,1,0,1,0,0,0\\ 0,0,0,0,1,0,0,0,0,0\\ 0,0,0,0,0,1,1,0,0,0\\ 0,0,0,0,0,0,0,1,1,0\\ 0,0,0,0,0,0,0,1,0,1\\ 0,0,0,0,0,0,0,1,0,0\\ 0,0,0,0,0,0,0,0,1,1 \end{array}.$$ Por la misma razón, ya que hay $7$ suma-discontinuo vectores en $\{0,1\}^5$, hay por lo menos $14$ suma-discontinuo vectores en $\{0,1\}^{10}$ y, al menos, $\left\lfloor\frac{7n}{5}\right\rfloor$ suma-discontinuo vectores en $\{0,1\}^n$.

Monte-Carlo cálculos de abajo parecen sugerir que hay al menos $2n-3$ suma-discontinuo vectores en $\{0,1\}^n$ para $n\geq 4$. Con el fin de fijar la notación, deje de $I_n$ ser el número máximo de suma disjuntos vectores en $\{0,1\}^n$. Si logramos demostrar $$I_{n+1}\geq I_n+2,\etiqueta{1}$$ vamos a comprobar el $2n-3$-bound.

Una manera sencilla de lograr $(1)$ sería tomar los vectores a dar $I_n$, aumentarlos con un cero en la primera coordenada, a continuación, tomar las dos vectores adicionales $(1,0,0,\ldots)$ y $(1,1,1,\ldots)$. Unluckyly, este ingenuo de la construcción no funcionan ya $(1,1,1,1)=(1,0,0,0)+(0,1,0,0)+(0,0,1,1)$, pero puede ser que podamos solucionarlo.

También hay un gráfico de la teoría de la interpretación que pueden ser útiles. Considere la posibilidad de un bipartito grafo no dirigido de $G$, con $m$ red de nodos y $n$ ($10$ en el problema original) azul nodos (emisores), donde diferentes nodos azules tienen distintos barrios y no son sólo los bordes entre un azul y un nodo rojo nodo. Cada emisor puede dar un $+1$,$0$ o $-1$ peso a los elementos del conjunto de su sus bordes; el peso de un azul vértice es la suma de los weigths de sus entrantes bordes. Suma propiedad libre: si para cada no-trivial de peso-asignación existe un azul vértice con cero peso, nos dan $m$ suma-distintos elementos de $\{0,1\}^n$. Para istance, el siguiente "suma-gratis" gráfico:

da $I_3\geq 4$ por el conjunto de suma libre de vectores de $110,101,110,001$ correspondiente a los barrios de la red de nodos. El gráfico correspondiente a la unidad SSD-$011,101,110,111$ es incluso mejor:

En este papel Lev muestra, a través del método probabilístico, $$ I_n \geq \frac{1}{\log_2 9}\cdot(1+o(1))\cdot n\log_2(n), $$ y creo que vale la pena reproducir sus argumentos, en concreto a $n=10$ caso. Vamos $S=\{-1,0,1\}^{17}$. Para cualquier $s\in S$, vamos $m^+$ ser el número de resultados positivos de coordenadas de $s$ y $m^ -$ $ $ el número de negativos coordenadas de $s$. Por un azar elegido vector $d\en\{0,1\}^{17}$ la probabilidad de ser ortogonal a $s$ es igual a:

$$ \frac{1}{2^{m^+ + m^-}}\sum_{j=0}^{\min(m^, m^+)}\binom{m^+}{j}\binom{m^-}{j}=\frac{1}{2^{m^+ + m^-}}\binom{m^+ + m^-}{m^+},$$

por lo tanto la probabilidad de que de 10 $$ elegido al azar de los vectores sean ortogonales simultáneamente a $s$ es muy pequeña. Dado que el número de elementos de la $S$ de un determinado $(m^, m^+)$-tipo es de solo $\binom{17}{m^+ + m^-}\binom{m^+ + m^-}{m^+}$, con el fin de demostrar $I_{10}\geq 17$ es suficiente para mostrar que:

$$\sum_{1\leq m^+ + m^- \leq 17}\binom{17}{m^+ + m^-}\binom{m^+ + m^-}{m^+}\left(\frac{1}{2^{m^+ + m^-}}\binom{m^+ + m^-}{m^+}\right)^{10} <1,$$

eso es cierto por cálculo directo. Por otra parte, ahora estoy notando que a través de un argumento probabilístico (el Hoeffding obligado) Seva MO empujó el límite superior de $30 dólares.

Answer 3

Dado un subconjunto particular $S'\subconjunto S$, usted puede pensar de cada posición en la suma como una medida: el $i$-ésima medición indica cuántos elementos de $S'$ $1$ en la $i$-ésima posición. Equivalentemente, el $i$-ésima medición le da el tamaño de la $S'\cap A_i$, donde $A_i=\{x\in S \;|\; \pi_i(x)=1\}$. Cómo de grande puede $S$ si se puede identificar un subconjunto arbitrario usando $n$ esas mediciones? Bueno, si $|S|=k$, luego de cada medición puede tener $k+1$ de los diferentes resultados, y así la mayor parte de la información se puede dar es de $\log_2(k+1)$ de bits. Ya que se necesita para distinguir entre $2^k$ subconjuntos, usted necesita para obtener $k$ bits de información en total, por lo que $$ n \log_2(k+1) \ge k, $$ o $$ \frac{k}{\log_2(k+1)} \le n. $$ Para $n=10$, por ejemplo, esto implica $|S| \le 59$.

Answer 4

Una ligera mejora para el límite superior, mostrando que la respuesta es $\le de 47$. Supongamos por el contrario que un conjunto $S$ de $48$ vectores que existen. El conjunto $S$ ha $$ \sum_{k=1}^{24}{48\elija k}=156\,861\,290\,196\,877 $$ subconjuntos de más de $24$ elementos. La suma de los vectores de los subconjuntos pertenecen al conjunto $\{0,1,\ldots,24\}^{10}$ que ha $25^{10}=95\,367\,431\,640\,625$ elementos. Por lo tanto, la colisión es inevitable por el principio del palomar.