Una suma cero subconjunto de una suma-conjunto completo

Question

Yo había visto este problema mucho tiempo atrás y no era capaz de resolverlo. Por alguna razón me acordé de ti y pensé que podría ser interesante para los visitantes aquí.

Al parecer, este problema es de una matemática de la revista de la universidad en los Estados unidos (lo siento, ni idea acerca de cualquiera).

Así que el problema es:

Supongamos $S \subset \mathbb{Z}$ (conjunto de números enteros) tales que

1) $|S| = 15$

2) $\forall ~s \in S, \exists ~a,b \in S$ tal que $s = a+b$

Demostrar que para cada una de dichas $S$, hay un no-vacío subconjunto $T$ $S$ tal que la suma de los elementos de $T$ es cero y $|T| \leq 7$.

Actualización (13 De Septiembre)

Aquí es un enfoque que parece prometedor y otros pueden ser capaces de llevarlo adelante, tal vez.

Si se mira el conjunto como un vector $s$, entonces existe una matriz $A$ con la diagonal principal están todos los $1$, cada fila contiene exactamente un $1$ e una $-1$ (o un solo $2$) en los no-diagonal posición tal que $As = 0$.

El problema es equivalente a probar que para cualquier matriz $A$ el espacio fila de a $A$ contiene un vector con todos los ceros, excepto por una $1$ $-1$ o un vector con todos los ceros excepto $\leq 7$.

Esto implica que los números en el conjunto $S$ sí no te importa y tal vez podemos reemplazar con los elementos de un campo diferente (como dicen de reales, o los números complejos).

Answer 1

Una débil declaración, donde nos permiten elementos en $T$ a repetirse, se puede demostrar de la siguiente manera:

Ya podemos ver el conjunto de $\{-s | s\in S \}$ podemos suponer que existen en la mayoría de las $7$ números positivos en $S$. Deje que cada número positivo ser un vértice, a partir de cada vértice $s$ nos dibuje una flecha para cualquier vértice $a$ tal que $s=a+b$. Ya que si $s>0$, $a,b$ debe ser positivo, hay al menos una flecha desde cualquier vértice. Así que debe haber un ciclo de $s_1,\cdots,s_n=s_1$$n\leq 8$. Podemos dejar que la $T$ se compone de $s_i-s_{i+1}$, $1\leq i\leq n-1$.

Answer 2

Esto no es una respuesta, pero claramente es demasiado largo para los comentarios.

Aquí están algunos de los enfoques que he estado jugando con; aprecio cualquier comentario, consejo o sugerencia.

Claramente la condición s_i = s_j + s_k es la clave de este problema. Parece que en orden a este estado como un problema (en lugar de como una conjetura), debe de haber sido resuelto por alguien, de lo contrario ¿de donde |T| $\leq$ 7? Puesto que no sabemos con certeza si el problema ha sido resuelto, estoy suponiendo que |T| $\leq$ 7 es posiblemente mal y tratando de averiguar las consecuencias de la enfermedad.

Esta condición es muy restrictiva, y sus consecuencias no son del todo evidentes. Una pregunta que tengo es, ¿cuántos independiente de los elementos de un conjunto que satisface la condición? La idea de un elemento independiente no es riguroso para un juego como este, pero la idea es averiguar cómo formular la idea de elemento independiente por lo que es riguroso. Dado un conjunto de enteros H, con |H| menos de 15, es posible añadir los números (por la combinación de elementos de H), de modo que H tiene 15 elementos y cumple la condición; si es así, ¿se puede decir algo sobre el tamaño original de H?

En esta dirección, he hecho la siguiente (un poco trivial) observaciones:

Un conjunto que satisface la condición contiene:

• al menos dos (diferentes) números positivos
• al menos dos (diferentes) números negativos
• al menos dos (diferentes) de los números que son la suma de un positivo y un número negativo

Esto se deduce del hecho de que cada conjunto contiene un mayor número positivo que debe ser la suma de los números positivos (de manera similar para el negativo); y el menor número positivo debe ser la suma de positivos y negativos (similares de menor número negativo). No estoy seguro de cómo esto se relaciona con el (mal definido) noción de "elemento independiente", pero se siente como un comienzo en esa dirección.

Otra idea es que la condición s_i = s_j + s_k puede ser "desempaquetado" aplicando recursivamente a s_j y s_k. Mi esperanza es que puedo mostrar de que siempre habrá un elemento que puede ser "desempaquetado" por lo que es igual a 8 elementos en S, uno de los cuales es en sí mismo. Este sería, por supuesto, demostrar que la suma de los otros 7 es cero.

s_i = s_j + s_k

= s_l + s_m + s_n + s_p

= s_p + s_r + s_s + s_t + s_u + s_v + s_w + s_i

La siguiente idea es mostrar que cualquier conjunto que satisface la condición contendrá lo que yo llamo un "7 ciclo", el cual está inspirado en el totalmente anti-simétrica de la unidad de tensor. "7 ciclo" es un tipo de simetría para el índice de s_i = s_j + s_k, voy a escribir lo que un 7 ciclo que parece, debido a que es más claro que explicar.

s₁ = s₂ + s₃

s₂ = s₃ + s₄

s₃ = s₄ + s₅

s₄ = s₅ + s₆

s₅ = ₆ + s₇

s₆ = ₇ + s₁

s₇ = s₁ + s₂

Si es posible demostrar que cualquier conjunto que satisface la condición contiene un 7 ciclo, entonces es claro que la suma de s₁...s₇ será cero (ya que es igual al doble de sí mismo).

Otra idea es una combinatoria, teoría de grafos enfoque. Claramente, un conjunto que satisface la condición genera un grafo dirigido (como se señaló en el MO enlace). Para mayor claridad, cada número de la S corresponde a un vértice, y si, por ejemplo, s₁ = s₂ + s₃, entonces habrá bordes dirigido desde s₂ s₁ y s₃ s₁.

Una pregunta que tengo, que me parece que no puede progresar, es: ¿cuál es el mínimo número de vértices que tienen bordes salientes? (un vértice tiene un borde saliente si se puede agregar a un elemento de S para obtener otro elemento de S, también los supuestos utilizados en la previamente dado "más débiles de la declaración", llevó a la conclusión de que cada vértice tiene un borde saliente, y esto fue utilizado para mostrar |T| $\leq$ 7). Mi esperanza es que una vez que sé que el mínimo número de vértices con bordes salientes, puedo usar algún tipo de razonamiento combinatorio para mostrar que no va a ser un ciclo cerrado con una longitud máxima.

Buscar en google "suma cero subconjunto" lleva rápidamente a las referencias para la EGZ teorema, y por pensar en el problema al revés, es lógico que dado que este es uno de los mejores resultados de suma cero problemas; que si este problema ya ha sido resuelto este resultado podría estar involucrado en la solución de alguna manera. Yo no puedo envolver mi cabeza alrededor de exactamente cómo va a participar, pero ya que es un resultado de tratar con los enteros mod N, la idea sería de alguna forma demostrar que la condición de las fuerzas de algunos (posiblemente elaboradas) aritmética modular de la estructura en el conjunto S que satisface. (mi entendimiento es que EGZ dice que dado un conjunto arbitrario de 2n - 1 enteros en $\mathbb{Z}$ mod n, habrá un subconjunto de n elementos cuya suma es congruente a 0 mod n)

Otra idea es la de reformular el problema en términos de polinomios. Dado un conjunto S que satisface la condición, considere el 15 de grado del polinomio cuyas raíces son los elementos de S. Entonces estas raíces poseen la simetría que cada raíz es la suma de los otros dos raíces; estos tipos de polinomios podría tener alguna propiedad que obliga a la suma de más de 7 elementos a ser cero.

No me siento fuertemente que cualquiera de estos enfoques puede resultar en última instancia el éxito, pero espero que por hacer este post me pueden ayudar a mantener esta pregunta vida e inspirar a otros a trabajar en él.