Vectores dentro del hipercubo unitario.

Question

El siguiente problema me ha estado molestando durante un tiempo, y finalmente he renunciado a resolverlo por mi cuenta. Sin embargo, todavía me gustaría ver una solución:

Para un número entero arbitrario $n$ considere un conjunto de todos los n-vectores con coordenadas $1$ et $-1$ Por ejemplo, para $n=2$ :

$(1,1),\ (1,-1),\ (-1,1),\ (-1,-1)$

La suma de los vectores es obviamente $0$ (vector cero). Ahora, cambia arbitrariamente algunas de las coordenadas a 0 (pueden ser diferentes coordenadas en diferentes vectores), por ejemplo

$(0,1),\ (1,0),\ (-1,1),\ (-1,-1)$

Demostrar que existe un subconjunto no vacío de vectores cuya suma sigue siendo $0$ .

(En nuestro caso: $(0,1) + (1,0) + (-1,-1)=(0,0)$ .

Answer 1

Como ha señalado Eric Naslund en los comentarios, esta pregunta se ha formulado y respondido antes en MathOverflow: Una adivinanza sobre los ceros, los unos y los menos . A continuación cito la breve respuesta de Yuval Filmus, que también ha escrito una explicación de una página .

• Escriba cada original como una diferencia de dos $0$ / $1$ vectores.
• Adapte esta representación a las líneas modificadas cambiando sólo los subtramos .
• Ahora tiene una función de $\{0,1\}^n$ a $\{0,1\}^n$ . Encuentra un ciclo.

Darij Grinberg añade: "La función del paso 3 es la que asigna cada minuendo al correspondiente sustraendo modificado".