La existencia de suma cero subconjunto

Question

Hace algún tiempo escuché esta pregunta y trató de jugar un rato con él. Nunca he logrado hacer que el progreso real. Aquí va:

Dado un determinado conjunto (no vacío) de números reales, $S=\{a_1,a_2,\dots, a_n\}$, con la propiedad de que para cada una de las $i$ existe $j,k$ (no necesariamente distintos), de modo que $a_i=a_j+a_k$ (es decir, cada elemento en $S$ puede ser escrita como una suma de dos elementos en $S$, tenga en cuenta que esta condición es extremadamente satisfecho si $0\in S$, a continuación, todos los $x\in S$ puede ser escrito como $x+0$).

Deben existir $\{i_1,i_2,\dots, i_m\}$ (distinta) de modo que $a_{i_1}+a_{i_2}+\cdots +a_{i_m}=0$?

ETA: UNA posible reformulación puede ser hecho en términos de gráficos. Podemos tomar el conjunto de vértices $\{1,\dots ,n\}$, y para cada ecuación de $a_i=a_j+a_k$ S añadir un borde a $[ij]$ y su "doble" $[ik]$. La idea es encontrar un ciclo en este gráfico, cuyo doble es una coincidencia.

Answer 1

Me parece que esta pregunta intrigante. Aquí es una manera de refundición como un entero de programación lineal pregunta:

Deje $M$ ser un no-negativo $n \times n$ entero de la matriz con todas las de la columna de cantidades iguales a 2. Hay necesariamente un vector con las entradas de 0's y 1's en la imagen $V$ $M - I$ (como una transformación lineal en $\mathbb R^n$)?

Dada una matriz $M$, puede formar el cociente grupo $\mathbb Z^n / V$. Ya que es gratis abelian grupo, puede ser incorporado en $\mathbb R$, dando la instalación como se indica. Por el contrario, si hay una colección de números reales, la satisfacción de ecuaciones, como se describe, usted puede pensar en él como la definición de un endomorfismo de la libre abelian grupo generado por el designado de los vectores.

No hay más que yo podría decir, pero ya que la pregunta es tan vieja, puedo pensarlo un poco más, y luego publicar una versión reformulada como una continuación de la pregunta. El tipo de personas que ven una relación con su experiencia puede ser diferente.

Answer 2

Un resultado más débil puede ser obtenida si no requerimos que el conjunto de soluciones distintas:

Lema. Existen $i_1, \ldots, i_m$ (no es necesario distintas), de modo que $a_{i_1}+a_{i_2}+ \ldots +a_{i_m}=0$.

prueba. Tenga en cuenta la suma de todas las ecuaciones $a_i=b_i+c_i$$a_i \in S$, donde $b_i,c_i \in S$ garantizado por la definición de $S$, tenemos

$\sum_i a_i = \sum_i (b_i+c_i)$.

Notó que el conjunto múltiple {$b_i,c_i$} debe contener todos los elementos en $S$, de lo contrario, podemos eliminar los elementos en $S \setminus$ {$b_i,c_i$}, la obtención de otro $S^*$ que se cumple la propiedad.

Ahora ya $S \subseteq$ {$b_i,c_i$}, nos cancelar $\sum_i a_i$ con los mismos números en {$b_i,c_i$}, lo que hace que la igualdad de la forma $a_{i_1}+a_{i_2}+ \ldots +a_{i_m}=0$ con $a_{i_k} \in$ {$b_i,c_i$}, es decir,$a_{i_k} \in S$. Ya hay un total $2|S|$ elementos en conjunto múltiple {$b_i,c_i$} y $0 \notin S$, tenemos el lema. $\square$

---

-- Editado en 2010/03/07 --

Esta conjetura está relacionado con un caso especial de el arco iris de la conjetura, que está altamente relacionado con la Caccetta-Häggkvist conjetura; ver una encuesta por Sullivan.

Para un dígrafo $G$ y el borde de los conjuntos de $E_1, \ldots, E_k \subseteq E(G)$, denotan $G_i = (V(G), E_i)$, y nosotros decimos que un subgrafo $H$ $G$ es el arco iris si $|E(H) \cap E_i| \leq 1$ por cada $i$$|E(H)| \geq 1$. Deje $\delta_i^+(v)$ denotar la outdegree de $v$ en el gráfico $G_i$.

El arco iris de la conjetura de los estados que,

Conjetura. Para un simple dígrafo $G$,

• Hay un arco iris (di)ciclo de trabajo en $G$, o
• Existe un nodo $v$ s.t. |{$w|\exists \text{ rainbow path from } v \rightarrow w $}| $\geq \sum_{i=1}^k \delta^{+}_{i}(v)$.

Ahora, mediante la construcción de un dígrafo $G$ con borde dirigido a $(u,v)$ $E_w$ si $u+w = v$, hay un dicycle en $G$ fib hay un conjunto $U$ s.t. $\sum_{x\in U} x = 0$ $x \in S$. Desde la segunda condición del arco iris conjetura no puede ser satisfecho por $k=|S|$ e $\delta_{i}^+(v) \geq 1$ todos los $i$$^@$, no debe ser un dicycle en $G$, con distintos colores, es decir, un subconjunto $U$ con distintos números.

@ La condición de $\delta_{i}^+(v) \geq 1$ es malo.

En la encuesta por Sullivan, la conjetura se resuelven para el caso especial en que $\delta_{i}^+(v) \leq 1$ todos los $v$ y todos los $i$, que es el caso, ya que para un determinado$u$$w$, no es más que una solución a la ecuación de $u+v=w$, que corresponde al borde dirigido a $(u,v) \in E_w$.

Answer 3

Para cada conjunto finito de números reales, $S =\{a_1,a_2,...,a_n\}$ que se cumple la condición de que el problema, le corresponde un grafo dirigido $G_S$ con la siguiente construcción:

Cada elemento de a $S$ se asocia con un vértice en $G_S$, de acuerdo a la regla de que si $a_i \in S $$ V_i \in G_S$. Un vértice $V_i \in G_S$ está conectado a otro vértice $V_k \in G_S$ por una arista $E_j$ si y sólo si $a_i + a_j = a_k$. Claramente, la existencia de un ciclo cerrado en el $G_s$ sin repetir los bordes corresponde a una suma cero subconjunto de $S$.

Un hecho útil, lo que yo me refiero como el "vértice de reemplazo truco", es que si $V_i \rightarrow(E_j)\rightarrow V_k$, entonces por la definición de la propiedad de $S$, también tenemos $V_j \rightarrow(E_i)\rightarrow V_k$.

He de decir que un camino de $P$ es "bien comportado" si no índice de $S$ aparece más de una vez en $P$, a menos que se produzca en un vértice adyacente/edge par de la forma $ \cdots \rightarrow V_i \rightarrow (E_i) \rightarrow \cdots$

Elegir un vértice arbitrario $V_a \in G_S$, y elegir un arbitrario entrante borde a $V_a$, decir $E_b$. A continuación, el camino inicial es:

$$P=V_c \rightarrow (E_b) \rightarrow V_a $$

A menos $0 \in S$, entonces cada posible camino inicial, se porta bien.

Añadir un vértice/edge par de a $P$ si $P$ es todavía bien comportado, a continuación, repita hasta que no lo es. Debido a la definición de la propiedad de $S$, siempre es posible encontrar otro vértice para agregar a cualquier ruta, y desde $S$ es finito, este proceso debe, finalmente, terminar.

$Claim:$ Si $P$ se porta bien, pero $P'=V_y \rightarrow (E_x) \rightarrow P$ es, $P'$ o bien contiene un ciclo cerrado con no repetir los bordes, o puede ser transformado en uno que hace aplicando el vértice de reemplazo truco.

$Proof:$ Si el índice de $x$ no aparece en $P$ pero $y$ hace, entonces podemos usar el vértice de reemplazo truco para asegurarse de que $V_y \in P$, y obtener así un ciclo cerrado, que por virtud de la $P$ se portaron bien, está garantizado que no tienen repita los bordes:

$$V_y \rightarrow E_x \rightarrow \cdots \rightarrow V_y$$

Si el índice de $y$ no aparece en $P$ pero $x$ hace, entonces de igual manera, utilizamos el vértice de reemplazo truco para obtener:

$$V_x \rightarrow E_y \rightarrow \cdots \rightarrow V_x$$

En el caso de que $x=y$, obtenemos:

$$V_x \rightarrow E_x \rightarrow \cdots \rightarrow V_x$$

De lo contrario, en el caso de que los índices de $x$ $y$ ambos aparecen en $P$, elija el elemento con índice de $x$ o $y$, lo que primero ocurra en $P$, y si ese elemento es un borde, que la convierten en un vértice usando el truco. A continuación, retire todos los elementos de a $P$ que se producen después de que el vértice, y volver a uno de los casos anteriores, donde sólo uno de los índices que aparece en $P$.

EDIT: Esto es una actualización masiva/reescritura de una pendiente de respuesta de la mina de años atrás. Mis disculpas si esto hace que los comentarios de edad, ya no es relevante.

Answer 4

Yo también no tienen una solución a la cuestión planteada.

Voy a tratar de relajar la condición finita, creo que puedo encontrar un infinte establecer Un ejemplo que no tiene un cero subsum con los distintos elementos.

Vamos A Un = {1, -2, 3, -5, 8, -13, ... }.

Más formalmente $a_n = a_{n-2} - a_{n-1}$, formando un alternando la secuencia de Fibonacci. Así, para cualquier $a_k \in A$, $a_k = a_{k+1} + a_{k+2}$.

Esto parece obra por la suma de cualquier subconjunto de A, excepto la suma de Un sí mismo, que se aproxima a 0. Esto está bien si usted está buscando solamente un subconjunto finito, como la notación indica que a mí.

Espero que esta ayuda, ya que me dice que el infinito condición es importante para ser capaz de escribir cualquier elemento como una suma de otros dos.

No me permiten formar un conjunto finito con la propiedad de que si me fije 0 a y cortar en algún lugar, y no parece haber ningún soluciones no triviales para el segundo requisito, pero no forma un contraejemplo a la pregunta como se indica (como se haría con cualquier conjunto que contiene 0).

Answer 5

Quizás se me interpreta mal la pregunta, pero no es $S$={$1,2, \ldots n$} un contraejemplo? Gracias por los comentarios de abajo.

Edit: todavía no he resuelto el problema, pero me las arreglé para traducir el problema a una teoría de grafos problema. Vamos $S$={$a_1, \dots, a_n$} ser de un tamaño mínimo de contraejemplo. Construir un gráfico de $G$ con conjunto de vértices $[n]$ y el conjunto de borde de la siguiente manera. Para cada una de las $i, j \in [n]$ poner un borde con la etiqueta $k$ $i$ $j$ si $a_k=a_i+a_j$. Nota, que $G$ pueden incluir bucles. El gráfico de $G$ satisface las siguientes condiciones

1. El conjunto de los bordes de las etiquetas es igual a $[n]$ (por hipótesis),
2. Sin vértices $i$ es incidente a un borde con borde de etiqueta $i$ ($0 \in S$),
3. Sin vértices $i$ es de grado 0 ($S - a_i$ es menor contraejemplo).

Conjetura: Vamos a $G$ un gráfico satisfactorio (1),(2) y (3). Entonces existe un subconjunto $A$ de los bordes de las $G$ tal que

(a) el conjunto de vértices de $G[A]$ (el subgrafo inducido por $A$) contiene el conjunto de los bordes de las etiquetas de $G[A]$

(b) $G[A]$ tiene el grado máximo de 2,

(c) cada vértice de $G[A]$ que no es un borde de etiqueta de $G[A]$ tiene grado 1 en $G[A]$.

Si tal conjunto existe, $S$ contiene una suma cero en el conjunto. La suma cero ajuste es el conjunto indexado por los vértices de $G[A]$ que no están de borde etiquetas de $G[A]$ junto con el grado 2 vértices de $G[A]$. Supongo que la conjetura es falsa, ya que no hace uso de ninguna de las propiedades de los números reales. En particular, esto implicaría que el problema original es verdadera para cualquier campo.