Prove that the 23 people have the same weight.

I know that it must be an old question, and I have encountered it before, in MAT 1993.2 (Oxford admission test). But I dimly remember the solution. The question is

Twenty-three people, each with integral weight, decide to play football, separating into two teams of 11 people each, plus a referee. To keep things fair, the teams chosen must have equal total weight. It turns out that no matter who is chosen to be the referee, this can always be done. Prove that the 23 people have the same weight.

The answers above rely mostly on the fact that the weights are integers. However, the result also holds for real weights as well, and is a common (spectacular regardless, in my opinion) application of linear algebra.

Let $W$ be the column vector of weights. Consider the matrix $A$ ($23 \times 23$ with entries in $\{0,1,-1\}$) such that its $i$th row represents the weight distribution of the teams ($1$ for a team, $-1$ for the other and $A_{i,i}=0$ is the only null entry) when person $i$ is a referee.

Then $AW=0$, so $A$ has rank at most $22$ (unless $W=0$).

Besides, in $\mathbb{F}_2$, $A$ reduces to $A’$ which has only $1$ outside the diagonal and $0$ in the diagonal.

We can check that the cofactor $(1,1)$ of $A’$ is nonzero in $\mathbb{F}_2$, so $A$ has a nonzero cofactor, so its rank is exactly $22$.

Now, $W$ and $(1,1,\ldots,1)$ are in the kernel of $A$. Thus they are proportional, which is the required claim.

Proof by contradiction.

Let there be such a collection of 23 people and with unequal weights.

Then, there is the total weight of $W$, and that is made up of everyone's individual weights $w$. And so, $W=w_1+w_2+w_3 \dots w_{21}+w_{22}+w_{23}$. Let this be the "smallest total weight".

Then let's try to find a smaller total weight. (We shouldn't be able to, however).

To start, all integer weights $w$ are either even or odd. And since one person is referee, then let's see what happens to the weights that are divided into the two teams.

If $w_n$ is referee, then we'd have $W-w_n$ as the remaining weights. Regardless of $w_n$ being even or odd, this remaining weights would have to be even since it's split between two teams.

Now that means that $(W-w_n)+(W-w_m)$ should be even regardless of of $w_n$ or $w_m$ is even or odd... but $(W-w_n)+(W-w_m)=2W-w_n-w_m$ could be odd if, say, $w_n$ was even and $w_m$ was odd. So this means we're looking at all $w$'s being all even, or all odd.

So, all $w$'s are of the same parity.

If all $w$'s are even, when we could have a smaller total weight, $W'$, by simply dividing everyone's weight by 2, and this would be smaller than $W$ - but we assumed at the beginning that $W$ was the smallest --> Contradiction.

If all $w$'s are odd, then we could get another smaller total weight, $W''$, by adding $1$ to everyone's weight and then dividing by $2$ - but, again, we assumed that $W$ was the smallest --> Contradiction.