Demostrando que las vacas tienen el mismo peso sin pesado!

Question

Mi amigo me dio este problema y no tengo ninguna pista de cómo hacerlo:

Un campesino tiene $2n + 1$ vacas. Cuando pone a un lado ninguna de sus vacas, el % restante $2n$, puede dividirse en dos sub-rebaños de vacas de $n$ y cada uno con el mismo peso total. ¿Cómo podemos demostrar que las vacas todas tienen el mismo peso?

¿Cómo puedo plantear esto?

Answer 1

Deje $w_i$ el valor del peso de la vaca $i$, $1\le i\le 2n+1$. Con $\mathbf e_i$ $i$th miembro de la norma base de la $\mathbb R^{2n+1}$ deje $\mathbf w=\sum_i w_i\mathbf e_i$$\mathbf j=\sum_i \mathbf e_i$. Por supuesto, para cada $k$, $1\le k\le 2n+1$, existe un vector $\mathbf a_k=\sum_ia_{k,i}\mathbf e_i\in \mathbb Z^{2n+1}\subset\mathbb R^{2n+1}$ con

• $a_{k,k}=0$,
• $a_{k,i}\in\{-1,1\}$ todos los $i\ne k$,
• $\langle \mathbf a_k,\mathbf j\rangle=0$,
• $\langle \mathbf a_k,\mathbf w\rangle = 0$.

Entonces los vectores $\mathbf a_k+\mathbf j\equiv \mathbf e_k \pmod 2$, es decir, el $\mathbf a_k+\mathbf j+2\mathbb Z^{2n+1}$ son el estándar de la base de $\mathbb Z^{2n+1}/2\mathbb Z^{2n+1}\cong \mathbb F_2^{2n+1}$. Suponga $\sum_k q_k(\mathbf a_k+\mathbf j)=0$$q_k\in\mathbb Q$, no todos los $=0$. Por multipying con el denominador común podemos asumir que todos los $q_k\in\mathbb Z$, dividiendo los factores comunes podemos suponer que al menos una de las $q_k$ es impar. Pero luego de tomar los restos de $\bmod 2$ produce una dependencia lineal entre la $\mathbf a_k+\mathbf j+2\mathbb Z^{2n+1}$. A partir de esta contradicción, llegamos a la conclusión de que el $\mathbf a_k+\mathbf j$ $\mathbb Q$- linealmente independientes y, por tanto, una base de $\mathbb Q^{2n+1}\subset\mathbb R^{2n+1}$. Por lo tanto, podemos escribir la $\mathbf e_k=\sum_i c_{k,i}(\mathbf a_i+\mathbf j)$ $c_{k,i}\in \mathbb Q$ $$ 1=\langle \mathbf e_k,\mathbf j\rangle=\sum_ic_{k,i}(\langle \mathbf a_i,\mathbf j\rangle +\langle\mathbf j,\mathbf j\rangle)=(2n+1)\sum_ic_{k,i}$$ y por lo tanto $$ \begin{align}w_k&=\langle \mathbf e_k,\mathbf w\rangle\\&=\sum_i c_{k,i}\langle \mathbf a_i,\mathbf w\rangle +\sum_i c_{k,i}\langle \mathbf j,\mathbf w\rangle\\ &=\rlap{\qquad0}\hphantom{\sum_i c_{k,i}\langle \mathbf a_i,\mathbf w\rangle}+\langle \mathbf j,\mathbf w\rangle\cdot \sum_ic_{k,i}\\&=\frac{\langle \mathbf j,\mathbf w\rangle}{2n+1}\end{align}$$ que no depende de la $k$.

Answer 2

Aunque Hagen ha dado una perfectamente buena prueba, voy a tratar de dar uno que utiliza un menor número de fórmulas.

Los pesos de las vacas puede ser modelado por un número impar $m=2n+1$ de desconocido $X_i$, y para cada una de las $i$ nos da la existencia de una ecuación $$\sum_{j=1}^ma_{i,j}X_j=0$$ with fixed coefficients $a_{i,j}$ such that $a_{i,i}=0$, while $a_{i,j}\en\{-1,+1\}$ for $j\neq i$ (the sets of $j$ for which $a_{i,j}=-1$ respectively $a_{i,j}=+1$ give the partition of remaining cows in two groups of equal total weight. Since both groups have the same number ($n$) of elements, one has $\sum_{j=1}^ma_{i,j}=0$, and since this holds for all$~i$ this means that $1=X_1=X_2=\cdots=X_m$ es una solución particular del sistema. Ahora debemos pensar en todas las soluciones del sistema de ecuaciones homogéneo, mostrando que no contienen nada más que la de los múltiplos escalares de esta solución.

Voy a debilitar estas hipótesis ligeramente de la siguiente manera, más con el propósito de mostrar lo que realmente se utiliza en la prueba de generalizar el problema. Voy a suponer para los coeficientes $(a_{i,j})_{i,j}$ del sistema, que

1. todos los $a_{i,j}$ son enteros (por $1\leq i,j\leq m$);
2. la paridad de $a_{i,j}$ es incluso si $i=j$ e impares de otro modo;
3. $\sum_{j=1}^ma_{i,j}=0$ (de modo que $1=X_1=X_2=\cdots=X_m$ sigue siendo una solución).

La proposición. Para un sistema de ecuaciones, cada una de las soluciones satisface $X_1=X_2=\cdots=X_m$.

Prueba. Voy a argumentar una contradicción formulario de la suposición de que un no-constante de la solución (que significa donde $X_1=X_2=\cdots=X_m$ no posee) existe. Tenemos un sistema de ecuaciones homogéneo con coeficientes racionales (hipótesis 1.), así que si hay algún no-constante de soluciones, hay no-constante de soluciones racionales (el rango del sistema a través de los números reales es la misma que la de su rango sobre los números racionales). Suponiendo que tal solución existe, podemos multiplicar por un número entero para obtener un no-constante integral de la solución. Ahora entre los no-constante de soluciones integrales, elegir uno (llamando $v_i\in\Bbb Z$ $X_i$ de la solución) para que la "amplitud" $\max_i v_i-\min_i v_i$ es mínima (pero positivo, ya que estamos restringiendo a los no-constante de soluciones).

Tomando la ecuación de $\sum_{j=1}^ma_{i,j}v_j=0$ que se supone que es pulsado, y la adición de $\sum_{j=1}^mv_j$ a ambos lados de la misma, nos encontramos y después de la reducción del modulo$~2$ y el uso de hipótesis 2. que $v_i\equiv\sum_{j=1}^mv_j\pmod2$. (Esto también es fácil ver directamente desde la pareja de el resto de las vacas en la formulación original.) Como esto vale para todos los$~i$, vemos que todos los $v_i$ debe tener la misma paridad, es decir, que de $\sum_{j=1}^mv_i$. Si esta paridad fueron incluso, uno podría dividir la solución en$~2$ conseguir otro que no sea constante con la solución estrictamente menor amplitud, contradiciendo nuestra elección de una solución con un mínimo de amplitud. Por lo tanto, la paridad de cada una de las $v_i$ sólo puede ser impar. Pero dado que nuestro sistema es homogéneo, la solución especial de hipótesis 3. puede ser añadido para dar una nueva solución (con $X_i=v_i+1$ todos los$~i$) con la misma amplitud, pero ahora, con la paridad, de nuevo, podemos dividir por$~2$ contradecir minimality de la amplitud de nuestra solución elegida. De haber una contradicción en todos los casos, nuestra hipótesis de la existencia de un no-constante de la solución debe estar equivocado; QED.

Answer 3

Supongamos que todas las vacas tienen pesos diferentes.

Tomamos el grupo más pequeño, donde en este caso sería posible, que sería de 3 vacas.

Si ninguna de las vacas pesos' son el mismo, tan pronto como nos llevamos una vaca de distancia, las dos restantes las vacas tienen diferentes pesos.

Este es el caso n = 1, y es imposible.

Entonces, ¿qué sucede cuando vayamos a n + 1?

La única manera de hacer coincidir los dos lados iguales, es proporcionar a cada lado con una vaca de el peso de la vaca en el lado opuesto, por lo que tendría

W1 + W2 en un lado

y

W2 + W1 en el otro,

con

W3 eliminado.

Ahora el problema es que, si nos sustituir alguna de las W1 o W2 vacas con el W3 vacas, tendría que ser el mismo peso que el de la vaca es la sustitución para que esto funcione.

Pero si es posible con una W1 vaca, no es posible con una W2 vaca, haciendo que el n = 2 caso imposible.

Usted puede continuar este proceso de pensamiento a través de la ns y refutar todos los casos por inducción.

Answer 4

Contamos con las ecuaciones de $2n+1$ $2n+1$ incógnitas. Esto tiene una solución única. Como todas las vacas tienen el mismo peso es una solución, es la única solución.