A peasant owns $2n+1$ cows. When he separates a cow from the rest of the herd, he can split the $2n$ remaining ones into two groups of $n$ cows such that the sum of weights of each group are equal.
Prove that the cows all have the same weight.
This was given at an oral examination. I think some linear algebra is at stake, although I haven't solved the riddle yet.
On
Difficult.
First, let's get rid of irrational numbers. If the weights of the cows are not all rational, then there is a smallest set of irrational numbers r1 .. rk such that the weight of cow number i is the sum $c_{i0} + c_{i1}r_1 + ... + c_{ik}r_k$ for rational numbers $c_{ij}$. Then for every fixed j, all the $c{ij}$ must be equal, so all the weights are the same (if we prove it for rational weights).
If the weights are all rational, we can multiply them by their lowest common denominator and get integers. So we can assume all the weights are integers. We can assume they are not all even (otherwise divide by 2). The sum is either even or odd. If it is even then no cow can have an odd weight (because the remaining 2n cows would have an odd weight), but we excluded that case so the total weight is odd. But then no cow can have an odd weight, so all weights are odd.
If all the weights are odd, we can subtract 1 from each weight without changing the situation. Now we can divide by two once or more than once and end up with all odd numbers again. Eventually all the numbers will be zero.
On
For integer (or rational) weights:
we have $2n+1$ number, we can divide any $2n$ into two groups that the sum will be equal. Suppose numbers are not equal.
We can divide all numbers from our set by some number or we can subtract any number from our set — the property "could be divided into two groups that the sum will be equal" will be conserved.
So, firstly let subtract the least number from all of them. We now have set with $0$.
Not all numbers are zeros though and if all numbers are even we can divide set by $2$. We will do it until we have odd number in our set.
Now we have set with $0$ and with odd number.
If we delete $0$, remaining numbers could be divided, so their sum is even and whole sum is even.
If we delete odd number, remaining numbers could be divided, so their sum is even and whole sum is odd.
We have the contradiction.
For irrationals:
gnasher729's reasoning is good, but I think it is a theorem itself — prove that
for every fixed $j$, all the $c_{ij}$ must be equal
Alternatively, you could prove another theorem:
for any $a_1,\ldots , a_n \in\mathbb{R}$ and for any $\varepsilon>0$ there exists $N\in\mathbb{N}$ that for every number $Na_i, i\in\{1,\ldots,n\}$ exist $A_i\in\mathbb{Z}$ that $|Na_i-A_i|<\varepsilon$
On
And now a real proof:
If all the weights are integers, then either all weights are even, or all weights are odd: If some were even and others odd, then we could remove a cow with an even weight, or a cow with an odd weight, and in one case the remaining cows would have an odd weight, and couldn't be divided into two groups of equal weight.
For all k ≥ 0, if all weights are $0 ≤ w < 2^k$, then all weights are equal: It is trivially true for k = 0 (because all weights must be zero). Assume all weights are $0 ≤ w < 2^{k+1}$: If the weights are all even, we examine 2n+1 cows with weights $w_i / 2$, if the weights are all odd, we examine 2n+1 cows with weights $(w_i - 1)/2$. By induction, these weights are all the same, so the w_i are all the same.
This proves the case if all weights are integers ≥ 0. If there are negative integers, and the smallest is w, then we examine 2n+1 cows with weights $w_i - w$. These weights are all ≥ 0, so all $w_i - w$ are equal, so all $w_i$ are equal.
If the weights are rational numbers, with the smallest common denominator equal to d, then we examine 2n+1 cows with weights $w_i * d$. Those weights are all integers, so all the $w_i * d$ are the same, so all the $w_i$ are the same.
If the weights of the cows are not all rational, then there is a smallest set of irrational numbers $r_1$ ... $r_k$ such that the weight $w_i$ of cow number i is the sum $c_{i0}+c_{i1}r_1+...+c_{ik}r_k$ for rational numbers $c_{ij}$. Then for every fixed j, we can examine 2n+1 cows with weights $c_{ij}$, so all $c_{ij}$ must be equal for fixed j, so the sums $c_{i0}+c_{i1}r_1+...+c_{ik}r_k$ must all be equal.
On
Define the set of cows: $$\mathbb{X} = \{1, \ldots, 2n+1\}$$
Given a subset $I \subset \mathbb{X}$ such that $|I| = n$, one can define the following set:
$$\mathbb{Y}(I) = \{J \subset \mathbb{X}: |J| = n \wedge I \cap J = \emptyset\}$$
Moreover, we can define the following:
$$J_a(I) = J \in \mathbb{Y}(I) : a \not\in I \wedge a \not\in J$$
Finally, define $w_i \in \mathbb{R}$ as the weight of the $i$-th cow and $W(I)$ as $$W(I) = \sum_{i \in I}w_i$$
Fix a set $I \subset \mathbb{X}$ such that $|I| = n$. Then we want that:
$$W(J_a(I)) = W(J_b(I)) ~ \forall a,b \in \mathbb{X} \setminus I ~~~~~(1)$$
Translated into words, we are asking that all groups of $n$ cow (i.e. $J_a(I)$, $J_b(I)$...) alongside the group of cow $I$ have the same total weight.
Notice that, by definition:
$$W(J_a(I)) = W(J_b(I)) + w_b - w_a$$
Then the (1) becomes:
$$w_b = w_a~ \forall a,b \in \mathbb{X} \setminus I$$
If this is true for all $I \subset \mathbb{X}$ such that $|I| = n$, then we are done. In this way, we have that all weights $w_i$ must be equal.
I think user Blue outlined a nice proof in his comment. Let me turn it into an answer.
Let $x_1,\ldots,x_{2n+1}$ be the weights of the cows. Let $X=(x_1,\ldots,x_{2n+1})$. For a given $i\in\{1,\ldots,2n+1\}$, there are some disjoint subsets of $\{1,\ldots,2n+1\}\setminus\{i\}$, say $I$ and $J$ such that $\sum_{k\in I}x_k=\sum_{k\in J}x_k$. We rewrite this as $\sum_{j=1}^{2n+1}a_{ij}x_j=0$ where $a_{ii}=0$, $a_{ij}=1$ if $j\in I$ and $a_{ij}=-1$ if $j\in J$. This defines a matrix $A$ such that $AX=0$
It remains to prove that $A$'s null-space is one-dimensional. This can be done by remarking that it has a non-zero $2n\times 2n$ leading principal minor. Thus $\operatorname{rank}A\geq 2n$, but $(1,\ldots,1)\in \operatorname{Ker}A$. Hence $\operatorname{rank}A= 2n$, and $A$'s null-space is one-dimensional.