Prove that the elements of X all have the same weight

Question

I have had this problem on my mind for weeks and haven't been able to find a solution. Let $X$ be a set with $2n+1$ elements, each of which has a positive "weight" (formally, we could say there exists a weight function $w:X\to \mathbb{R}^+$). Suppose that for every $x\in X$, there exists a partition of $X\setminus\{x\}$ into two subsets each containing $n$ elements such that the two sums of the weights of the elements in each subset are equal (or using mathematical symbols, $\forall x\in X$, $\exists Y,Z\subset X$, such that $Y\cup Z=X\setminus\{x\}$, $|Y|=|Z|=n$, and $\sum_{y\in Y}w(y)=\sum_{z\in Z}w(z)$). Prove that the elements of $X$ must have the same weight.

The converse is obvious. If the elements of $X$ have the same weight, then clearly any partition of $X\setminus\{x\}$ into two subsets of equal size will suffice. It's this direction that's troublesome. I have tried using induction, and I have tried turning it into a linear algebra problem, but I haven't had luck with either of these methods. If anyone can think of a solution, I'd love to hear it.

Answer 1

Assume the elements are not all the same. Multiply them all by a factor large enough that their nearest integers are not all the same. Now apply the simultaneous version of Dirichlet's approximation theorem to find an integer $q$ to multiply them by, such that the resulting numbers all differ by less than $\frac1{2n}$ from the nearest integer. These rescalings preserve the premise. Since the differences from the nearest integers add up to less than $1$, the condition in the premise must hold for the nearest integers, which are by construction not all the same. Thus it suffices to prove the claim for integer elements.

So assume integer elements. Subtract the smallest element from all elements; this preserves the premise. Now one element is $0$. If they're not all $0$, divide through by the greatest power of $2$ that divides all of them; this also preserves the premise. Now one of them is odd and the $0$ is even; but the premise implies that they're either all even or all odd; a contradiction; hence they were all $0$ and thus originally all equal.

Answer 2

Since the Question is tagged in linear algebra, here's a linear algebra answer:

Let the weights be $w_1, w_2, \dots, w_{2n+1}$. Let $\mathbf w$ be the vector of these weights. Assume that for every $x \in X$, there is a partition of $X \backslash \{x\}$ into 2 sets having equal total weight. So there is a $(2n+1) \times (2n+1)$ matrix $M$, such that it's diagonal entries are $0$, and all other entries are $\pm1$ with $M \mathbf w = \mathbf 0$. $M$ has an equal number of $+1$s and $-1$s in each row.

If the nullity of $M$ is $0$, then we reach a contradiction, because all the weights are positive.

Now, let $N$ be the $2n \times 2n$ submatrix of $M$, consisting of the first $2n$ rows and columns. $\det N\pmod2$ is the number of dearrangements of $2n$, which is odd. So $N$ is invertible. This gives us that the nullity of $M$ is at most $1$.

When $M$ has an equal number of $+1$s and $-1$s in each row, we have the null-space being a single dimensional subspace of $\mathbb R^{2n+1}$. This is obviously the space spanned by $(1,1, \dots, 1)$, given by the converse part of the question.

So finally, we have that if such a division is possible, then all elements in $X$ have the same weight.

Remark: A natural question to ask is whether the result remains true if we weaken the assumption that $X\backslash \{x\}$ is broken into sets of equal size. Remarkably, the result still holds but requires a lot more work to show.

Answer 3

The weights $w_i$ span a vector space $V:=\langle w_1,w_2,\ldots,w_{2n+1}\rangle$ over ${\mathbb Q}$ of dimension $d\leq2n+1$. Let $(\xi_1,\ldots,\xi_d)$ with $\xi_k\in{\mathbb R}$ be a basis of $V$. Then there are rational numbers $a_{ik}$ such that $$w_i=\sum_{k=1}^d a_{ik}\,\xi_k\qquad(1\leq i\leq 2n+1)\ .$$ Any integer relation $$\sum_{i=1}^{2n+1} n_i\,w_i=0\tag{1}$$ among the $w_i$ then implies $\sum_{k=1}^d\left(\sum_{i=1}^{2n+1}n_i a_{ik}\right)\xi_k=0$, hence $$\sum_{i=1}^{2n+1}n_i a_{ik}=0\qquad(1\leq k\leq n)\ ,$$ saying that each $(2n+1)$-tuple ${\bf a}_k:=(a_{ik})_{1\leq i\leq 2n+1}$ satisfies $(1)$. This allows to conclude that each ${\bf a}_k$ $(1\leq k\leq d)$ satisfies the premises of the question. After dividing $\xi_k$ by the LCM of the $a_{ik}$ we may assume that all $a_{ik}$ are integers.

We now make use of @joriki 's elegant argument to show that the ${\bf a}_k$ are in fact constant. So there are numbers $m_k$ $(1\leq k\leq d)$ with $a_{ik}=m_k$ $(1\leq i\leq 2n+1)$. It follows that $$w_i=\sum_{k=1}^d m_k\,\xi_k\qquad(1\leq i\leq 2n+1)\ .$$