Existencia de un subconjunto de suma cero

Question

Hace algún tiempo escuché esta pregunta y traté de jugar con ella. Nunca logré avanzar realmente. Aquí va:

Dado un conjunto finito (no vacío) de números reales, $S=\{a_1,a_2,\dots, a_n\}$ con la propiedad de que para cada $i$ existe $j,k$ (no necesariamente distintos) para que $a_i=a_j+a_k$ (es decir, cada elemento de $S$ puede escribirse como una suma de dos elementos en $S$ Obsérvese que esta condición se cumple trivialmente si $0\in S$ como entonces cada $x\in S$ puede escribirse como $x+0$ ).

¿Debe existir $\{i_1,i_2,\dots, i_m\}$ (distintos) para que $a_{i_1}+a_{i_2}+\cdots +a_{i_m}=0$ ?

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

Answer 1

La respuesta es afirmativa; efectivamente,

Si $S$ es un subconjunto finito no vacío de cualquier grupo abeliano tal que cada elemento de $S$ es una suma de otros dos elementos (posiblemente, iguales entre sí), entonces $S$ tiene un subconjunto no vacío y de suma cero.

Para una prueba completa, véase esto preimpresión reciente por János Nagy, Péter Pach y yo mismo. La prueba es demasiado larga para presentarla aquí, pero al menos, para indicar la dirección general, aquí está nuestro lema principal.

Lema. Supongamos que $M$ es una matriz cuadrada entera de orden $n$ representable como $A-I$ où $A$ tiene todos sus elementos no negativos y todas las sumas de las filas son iguales a $2$ y $I$ es la matriz de identidad. Entonces existen vectores no nulos $u,v\in\{0,1\}^n$ tal que $M^Tu=v$ es decir, existe un sistema de filas de $M$ tal que su suma es un vector no nulo, cero-uno.

De hecho, para nuestros propósitos bastaría con tener cualquier vector no nulo $u$ satisfaciendo $M^Tu\in\{0,1\}^n$ teniendo $u$ sí mismo para ser cero-uno es un extra (comparar con la respuesta de Bill Thurston arriba).

La demostración del lema principal es completamente elemental, por inducción en $n$ .

Históricamente, la pregunta parece tener su origen en un problema aportado por Dan Schwarz a la EGMO 2012 (Olimpiada Europea de Matemáticas para Niñas):

¿Existe un conjunto de enteros tal que cada elemento del conjunto es una suma de otros dos elementos, mientras que el conjunto no contiene un subconjunto finito no vacío de suma cero?

La respuesta a esta pregunta es positiva, ya que se permite que el conjunto sea infinito.

Answer 2

El prueba brillante de Seva, János y Péter me parece bastante corto. Aquí está.

Demostramos la siguiente afirmación que, obviamente, implica la demanda.

Dejemos que $S$ sea un conjunto finito no vacío de variables. Supongamos que para cada $a\in S$ tenemos una forma lineal $\ell_a:=b(a)+c(a)-a$ para ciertos $b(a),c(a)\in S\setminus\{a\}$ (posiblemente $b(a)=c(a)$ ). Entonces existe un conjunto no vacío $A\subset S$ tal que todos los coeficientes de la forma lineal $\sum_{a\in A}\ell_a$ pertenecen a $\{0,1\}$ .

Por inducción, podemos suponer que esto se cumple para valores menores de $|S|$ .

Consideremos el multiconjunto $T=\{b(a),c(a):a\in S\}$ . Tenemos $|T|=2|S|$ . Si $T$ -multiplicidad de cada elemento $x\in S$ es igual a 2, tenemos $\sum_{a\in S} \ell_a=\sum_{x\in S} x$ , por lo que podemos tomar $A=S$ . Si $T$ -multiplicidad de algunos $x\in S$ es igual a 0, basta con eliminar $x$ de $S$ ( $S$ sigue siendo no vacía) y aplicar la inducción.

Queda por considerar el caso cuando $T$ -multiplicidad de algunos $z\in S$ es igual a 1. Digamos, $z=b(x)$ , $\ell_x=z+y-x$ para ciertos $y\notin \{x,z\}$ . Denote $T=S\setminus \{x,z\}$ . Para $a\in T$ consideremos la forma lineal $\ell_a'$ obtenido a partir de $\ell_a$ sustituyendo $x$ por $y$ si es necesario (tenga en cuenta que si esto ocurre para $\ell_y$ es decir, $\ell_y=x+t-y$ entonces $\ell_y+\ell_x=z+t$ y podemos tomar $A=\{x,y\}$ .) Por inducción, la suma de varias de estas formas $\ell_a'$ tienen coeficientes 0 y 1. Para las formas correspondientes $\ell_a$ esto significa lo que necesitamos, o que el coeficiente de $y$ en su suma es igual a -1 y el coeficiente de $x$ es igual a 1 o 2. En este último caso, añada $\ell_x$ a su suma.

Answer 3

Se puede obtener un resultado más débil si no exigimos que el conjunto de soluciones sea distinto:

Lema. Existen $i_1, \ldots, i_m$ (no necesariamente distintos) para que $a_{i_1}+a_{i_2}+ \ldots +a_{i_m}=0$ .

prueba. Consideremos la suma de todas las ecuaciones $a_i=b_i+c_i$ sobre todo $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)$ .

Se ha observado que el conjunto múltiple { $b_i,c_i$ } debe contener todos los elementos de $S$ , de lo contrario podemos eliminar los elementos en $S \setminus$ { $b_i,c_i$ }, obteniendo otra $S^*$ que satisface la propiedad.

Ahora bien, como $S \subseteq$ { $b_i,c_i$ }, anulamos $\sum_i a_i$ con los mismos números en { $b_i,c_i$ }, lo que hace que la igualdad sea 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$ . Dado que hay totalmente $2|S|$ elementos en el multiconjunto { $b_i,c_i$ } y $0 \notin S$ tenemos el lema. $\square$

---

-- Editado en 2010/03/07 --

Esta conjetura está relacionada con un caso especial de la Conjetura del arco iris que está muy relacionado con la conjetura de Caccetta-Häggkvist; véase un encuesta por Sullivan.

Para un dígrafo $G$ y conjuntos de bordes $E_1, \ldots, E_k \subseteq E(G)$ , denotan $G_i = (V(G), E_i)$ y decimos que un subgrafo $H$ de $G$ es arco iris si $|E(H) \cap E_i| \leq 1$ para cada $i$ y $|E(H)| \geq 1$ . Sea $\delta_i^+(v)$ denotan el grado exterior de $v$ en el gráfico $G_i$ .

La conjetura del Arco Iris afirma que,

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

• Hay un (di)ciclo del arco iris 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 construyendo un dígrafo $G$ con borde dirigido $(u,v)$ en $E_w$ si $u+w = v$ , hay un diccionario en $G$ si existe un conjunto $U$ s.t. $\sum_{x\in U} x = 0$ , para $x \in S$ . Dado que la segunda condición de la conjetura del arco iris no puede satisfacerse para $k=|S|$ y $\delta_{i}^+(v) \geq 1$ para todos $i$$^@$ debe haber un dicycle en $G$ con colores distintos, es decir, un subconjunto $U$ con números distintos.

@ La condición $\delta_{i}^+(v) \geq 1$ se equivoca.

En el encuesta por Sullivan, la conjetura se resuelve para el caso especial de que $\delta_{i}^+(v) \leq 1$ para todos $v$ y todos $i$ que es el caso ya que para un determinado $u$ y $w$ hay a lo sumo una solución a la ecuación $u+v=w$ que corresponde a la arista dirigida $(u,v) \in E_w$ .

Answer 4

Esta pregunta me parece intrigante. He aquí una forma de reformularla como una pregunta de programación lineal entera:

Dejemos que $M$ sea un valor no negativo $n \times n$ matriz entera con todas las sumas de las columnas iguales a 2. ¿Existe necesariamente un vector con entradas 0's y 1's en la imagen $V$ de $M - I$ (como una transformación lineal en $\mathbb R^n$ )?

Dada una matriz $M$ se puede formar el grupo cociente $\mathbb Z^n / V$ . Como es un grupo abeliano libre, se puede incrustar en $\mathbb R$ , dando la configuración como se indica. A la inversa, si hay una colección de números reales que satisfacen las ecuaciones como se describe, se puede pensar en ella como definiendo un endomorfismo del grupo abeliano libre generado por los vectores designados.

Podría decir más cosas, pero como esta pregunta es tan antigua, quizá la medite un poco más y luego publique una versión reformulada como pregunta de seguimiento. Los tipos de personas que ven una relación con su experiencia pueden ser diferentes.

Answer 5

Tal vez entiendo mal la pregunta, pero ¿no es $S$ ={ $1,2, \ldots n$ ¿un contraejemplo? Gracias por los comentarios de abajo.

Editar: Todavía no he resuelto el problema, pero he conseguido traducirlo a un problema de teoría de grafos. Sea $S$ ={ $a_1, \dots, a_n$ } sea un contraejemplo de tamaño mínimo. Construir un gráfico $G$ con un conjunto de vértices $[n]$ y el conjunto de bordes de la siguiente manera. Para cada $i, j \in [n]$ poner un borde con la etiqueta $k$ entre $i$ y $j$ si $a_k=a_i+a_j$ . Tenga en cuenta que $G$ puede incluir bucles. El gráfico $G$ cumple las siguientes condiciones

1. El conjunto de etiquetas de borde es igual a $[n]$ (por hipótesis),
2. Ningún vértice $i$ es incidente a una arista con etiqueta de arista $i$ (si no $0 \in S$ ),
3. Ningún vértice $i$ es de grado 0 (si no $S - a_i$ es un contraejemplo menor).

Conjetura: Dejemos que $G$ sea un gráfico que satisfaga (1),(2) y (3). Entonces existe un subconjunto $A$ de bordes de $G$ tal que

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

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

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

Si ese conjunto existe, entonces $S$ contiene un conjunto de suma cero. El conjunto de suma cero es simplemente el conjunto indexado por los vértices de $G[A]$ que no son etiquetas de borde de $G[A]$ junto con los vértices de grado 2 de $G[A]$ . Supongo que la conjetura anterior es falsa, ya que no utiliza ninguna propiedad de los números reales. En particular, implicaría que el problema original es cierto para cualquier campo.