Proving that cows have same weight without weighing it! My friend gave me this problem and I have no clue how to go about it:
A peasant  has $2n + 1$ cows. When he puts aside any of his cows,
the remaining $2n$, can be divided into two sub-flocks of $n$ cows and each having
the same total weight. How can we prove that the cows all have the same weight? 
How can I approach this?
 A: Let $w_i$ denote the weight of cow $i$, $1\le i\le 2n+1$. 
With $\mathbf e_i$ the $i$th member of the standard basis of $\mathbb R^{2n+1}$
let  $\mathbf w=\sum_i w_i\mathbf e_i$ and $\mathbf j=\sum_i \mathbf e_i$.
By assumption, for each $k$, $1\le k\le 2n+1$, there exists a vector $\mathbf a_k=\sum_ia_{k,i}\mathbf e_i\in \mathbb Z^{2n+1}\subset\mathbb R^{2n+1}$ with 


*

*$a_{k,k}=0$, 

*$a_{k,i}\in\{-1,1\}$ for all $i\ne k$, 

*$\langle \mathbf a_k,\mathbf j\rangle=0$,

*$\langle \mathbf a_k,\mathbf w\rangle = 0$. 


Then the vectors $\mathbf a_k+\mathbf j\equiv \mathbf e_k \pmod 2$, i.e., the $\mathbf a_k+\mathbf j+2\mathbb Z^{2n+1}$ are the standard basis of $\mathbb Z^{2n+1}/2\mathbb Z^{2n+1}\cong \mathbb F_2^{2n+1}$. 
Assume $\sum_k q_k(\mathbf a_k+\mathbf j)=0$ with $q_k\in\mathbb Q$, not all $=0$. By multipying with the common denominator we may assume that all $q_k\in\mathbb Z$, by dividing out common factors we may assume at least one of the $q_k$ is odd. But then taking remainders $\bmod 2$ produces a linear dependence among the $\mathbf a_k+\mathbf j+2\mathbb Z^{2n+1}$. From this contradiction, we conclude that  the  $\mathbf a_k+\mathbf j$ are $\mathbb Q$-linearly independent and hence a basis of $\mathbb Q^{2n+1}\subset\mathbb R^{2n+1}$. 
Thus we can write $\mathbf e_k=\sum_i c_{k,i}(\mathbf a_i+\mathbf j)$ with $c_{k,i}\in \mathbb Q$ and have
$$ 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}$$
and hence 
$$ \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}$$
which does not depend on $k$.
A: Although Hagen has given a perfectly good proof, I'll try to give one that uses fewer formulas.
The weights of the cows can be modelled by an odd number $m=2n+1$ of unknowns $X_i$, and for each $i$ we are given the existence of an equation $$\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}\in\{-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$ is a particular solution of the system. We must now reason about  all solutions to this homogeneous system of equations, showing that they contain nothing more than the scalar multiples of this particular solution.
I will weaken these hypothesis slightly as follows, more with the purpose to indicate what is actually used in the proof than to generalise the problem. I will suppose for the coefficients $(a_{i,j})_{i,j}$ of the system, that


*

*all $a_{i,j}$ are integers (for $1\leq i,j\leq m$);

*the parity of $a_{i,j}$ is even if $i=j$ and odd otherwise;

*$\sum_{j=1}^ma_{i,j}=0$ (so that $1=X_1=X_2=\cdots=X_m$ remains a solution).



Proposition. For such a system of equations, every solution satisfies $X_1=X_2=\cdots=X_m$.

Proof. I will argue a contradiction form the assumption that a non-constant solution (meaning where $X_1=X_2=\cdots=X_m$ does not hold) exists. We have got a homogeneous system of equations with rational coefficients (by hypothesis 1.), so if there are any non-constant solutions, there are non-constant rational solutions (the rank of the system over the real numbers is the same as its rank over the rational numbers). Supposing such a solution exists, we can multiply by an integer to obtain a non-constant integral solution. Now among the non-constant integral solutions, choose one (calling $v_i\in\Bbb Z$ the value of $X_i$ in the solution) for which the "amplitude" $\max_i v_i-\min_i v_i$ is minimal (but positive, as we are restricting to non-constant solutions).
Taking the equation $\sum_{j=1}^ma_{i,j}v_j=0$ that is assumed to hold, and adding $\sum_{j=1}^mv_j$ to both sides of it, we find after and reduction modulo$~2$ and using hypothesis 2. that $v_i\equiv\sum_{j=1}^mv_j\pmod2$. (This is also easy to see directly from the paring up of the remaining cows in the original formulation.) As this holds for all$~i$, we see that all $v_i$ must have the same parity, namely that of $\sum_{j=1}^mv_i$. If this parity were even, one could divide the solution by$~2$ to get another non-constant solution with strictly smaller amplitude, contradicting our choice of a solution with with minimal amplitude. Therefore the parity of each $v_i$ can only be odd. But since our system is homogeneous, the special solution of hypothesis 3. can be added to give a new solution (with $X_i=v_i+1$ for all$~i$) with the same amplitude but now with even parity; again we can divide by$~2$ to contradict minimality of the amplitude of our chosen solution. Having a contradiction in all cases, our assumption of the existence of a non-constant solution must be wrong; QED.
A: Suppose all cows have different weights.
We take the smallest group where this case would be possible, which would be 3 cows.
If none of the cows weights' are the same, as soon as we take away one cow away, the two remaining cows have differing weights.
This is the case n = 1, and it is impossible.
So what happens when we go to n + 1?
The only way to match up the two sides to be equal, is to provide each side with a cow of the weight of the cow on the opposite side, so you would have
W1 + W2 on one side 
and 
W2 + W1 on the other,
with 
W3 removed.
Now the problem is, if we replace any of the W1 or W2 cows with the W3 cows, it would have to be the same weight as the cow it is replacing for this to work.
But if it is possible with a W1 cow, it is not possible with a W2 cow, making the n = 2 case impossible.
You can continue this thought process through the ns and disprove all the cases by induction.
A: We have $2n+1$ equations in $2n+1$ unknowns. This has a unique solution. As all the cows having the same weight is a solution, it is the only solution.
