Retire cualquier número y los números restantes se pueden repartir en dos subconjuntos de igual suma; probar que todos los números son iguales.

Question

Se supone que tengo una lista de $n$ números reales, donde $n$ es impar. La lista está estructurada de tal forma que me puede quitar cualquier número arbitrario de la lista, y el resto de los números se puede dividir en dos de igual tamaño subconjuntos con sumas iguales. Demostrar que todos los números en la lista son iguales.

Este debe ser de alguna manera relacionados con el álgebra lineal. Una manera de que yo pueda pensar de interpretar esto es que la lista es esencialmente un $1 \times n$ fila, y existen $n$ $n \times 1$ con los vectores uno a cero en algunos de entrada y $1$'s y $-1$'s en otras entradas con las entradas sumar a $0$, de tal manera que el producto de la fila y la columna del vector es $[0]$.

En otras palabras, las entradas/$1 \times 1$ columnas en la fila son linealmente dependientes una vez que eliminar cualquier entrada arbitraria/columna. No estoy seguro de cómo esto se podría estar relacionado con la prueba, aunque.

Gracias de antemano!

Answer 1

Deje $x=(x_1,x_2,\dots,x_n)$ ser el vector de números reales.

Para cada una de las $1\le i \le n$, existen distintos conjuntos de $P_i,Q_i\subset \{1,2,\dots,n\}$ cuya unión es $\{1,2,\dots,n\}\setminus \{i\}$ tal que $\sum_{j\in P_i}x_j=\sum_{j\in Q_i}x_j$. Deje $M$ $n\times n$ matriz definida por
$$ M_{i,j}=\begin{cases} 1 & x_j\in P_i\\ -1 & x_j\in Q_i\\ 0 & i=j\end{casos} $$ Dejando $\bf 1$ ser el vector de todos, entonces tenemos que $$ Mx=0\qquad \text{y}\qquad M{\bf 1}=0 $$ Si podemos mostrar que el espacio nulo de a $M$ tiene dimensión $1$, esto resultará $x$ es un escalar varios de $\bf 1$, por lo que todos los pesos son iguales.

Basta probar que $M'$, el superior de $(n-1)\times (n-1)$ submatriz de a $M$, es invertible. Dejando $J$ $(n-1)\times (n-1)$ matriz de todos, y $I$ $(n-1)\times (n-1)$ identidad, entonces cada elemento de a $M'$ es congruente mod $2$ para el elemento correspondiente de $J-I$, lo $\det M'\equiv \det(J-I)\pmod 2$. Considerando $J-I$ como una matriz de más de $\mathbb F_2$, (teniendo en cuenta que cada entrada de $J^2$$n-1\equiv 0\pmod 2$) $$ (J-I)^2 = J^2-2JI+I^2=I, $$ lo que demuestra $J-I$ es invertible mod $2$, lo $\det(J-I)\equiv 1\pmod 2$. Esto demuestra $\det M'\equiv 1\pmod 2$, lo $\det M'$ es distinto de cero, como se requiere.