Combinatorics problem on k sets and partionning a set of numbers, understanding of the proof

Question

The question I'm struggling with is given here :

Remove any number and the remaining numbers can be partitioned into two subsets of equal sum; prove all numbers are equal.

The problem is the following :

Supposed I have a list of n real numbers, where n is odd. The list is constructed such that I can remove any arbitrary number from the list, and the remaining numbers can be partitioned into two equal-sized subsets with equal sums. Prove that all numbers in the list are equal.

Here is my problem. I understand neither the paper given here : http://www.math.cmu.edu/~lohp/docs/math/mop2012/combinatorics-black-soln.pdf

nor the answer of @Mike Earnest.

I don't understand those points :

• why would be $Mx=0$ ?
• and $M{\bf1}=0$?
• Are you looking in the field given by $\text{mod } 2$ ?
• And finally, why since $x$ is a multiple of $1$, does that mean that all weights are equal?

Thanks for the help! I don't know if asking about another answer is allowed on this media, I hope it is not prohibited :)

Answer 1

As in the linked answer, for each $i$ let $P_i$ and $Q_i$ be disjoint sets whose union equals $\{1,\ldots,n\}\backslash\{i\}$, and $M$ the matrix described there. Let's write out what matrix equations $M{\bf x}=0$ and $M{\bf1}=0$ mean; the $i$-th coordinate of $M{\bf x}$ is given by $$M_i{\bf x}=\sum_{j=1}^nM_{ij}x_j=\sum_{j\in P_i}x_j-\sum_{j\in Q_i}x_j,$$ which equals $0$ precisely when the subset sums of $P_i$ and $Q_i$ are equal. So $M{\bf x}=0$ is equivalent to the subset sums of $P_i$ and $Q_i$ being equal for each $i$. Similarly, the $i$-th coordinate of $M{\bf1}$ is given by $$M_i{\bf1}=\sum_{j=1}^nM_{ij}=\sum_{j\in P_i}1-\sum_{j\in Q_i}1=|P_i|-|Q_i|,$$ which equals $0$ precisely when the subsets $P_i$ and $Q_i$ are the same size. So $M{\bf1}=0$ is equivalent to $|P_i|=|Q_i|$ for each $i$.

This shows that the problem translates to linear algebra as follows:

Given a vector $x=(x_1,\ldots,x_n)\in\Bbb{R}^n$ where $n$ is odd. Show that if there exists an $n\times n$-matrix $M$, with entries from $\{-1,0,1\}$ and $M_{ij}=0$ if and only if $i=j$, satisfying $M{\bf 1}=0$ and $M{\bf x}=0$, then $x$ is a scalar multiple of ${\bf 1}$.

The last statement, that $x$ is a multiple of ${\bf1}$, is the same as saying that all the $x_i$ are equal; after all, if $x_1=x_2=\ldots=x_n$ then ${\bf x}=x_1\cdot{\bf1}$.

To prove this, the linked answer shows that $\dim\ker M=1$. Because ${\bf x}$ and ${\bf1}$ are both contained in $\ker M$, it follows that ${\bf x}$ is a scalar multiple of ${\bf1}$.