3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is genius, thank you! At the end when you say "hence they were all 0", I presume you mean they must have been all 0 after subtracting the smallest element since, before that, they could have all been m for some nonnegative integer m. $\endgroup$ – Anonymous Jul 15 '18 at 4:34
  • 1
    $\begingroup$ @JulianBenali: Yes. I said "If they're not all $0$" (referring to the shifted elements) in order to prove that it leads to a contradiction; I concluded from the contradiction that the assumption was false, i.e. the shifted elements were all $0$ after all, and thus the original elements were all equal. Sorry, perhaps my attempt to keep the proof concise came at a cost to clarity :-) $\endgroup$ – joriki Jul 15 '18 at 5:55
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1, very nice! I don't understand the comment "This requires a bit of work". Since $M$ has an equal number of $+1$s and $-1$s in each row, the constant vectors are in its null space; and since the nullity is at most $1$, this is the entire null space. What further work is required? $\endgroup$ – joriki Jul 14 '18 at 11:28
  • $\begingroup$ @joriki One needs to prove that there isn't a matrix $M'$ (with a different number of $+1$s and $-1$s in each row) which admits a totally different one-dimensional solution space. What needs work is to say that matrices that don't conform to this equal number of $+1$s and $-1$s have nullity $0$. $\endgroup$ – Praneet Srivastava Jul 14 '18 at 11:39
  • $\begingroup$ But why would we want to prove that such matrices have nullity $0$? Or was that just a side remark? The proof of the original claim doesn't require further work, right? $\endgroup$ – joriki Jul 14 '18 at 11:41
  • $\begingroup$ @joriki You're right. That addition was to prove something stronger, as a point of interest. I've edited my answer to reflect that; see the remark at the end. $\endgroup$ – Praneet Srivastava Jul 14 '18 at 12:07
  • $\begingroup$ Aha, I see -- interesting. The edit made it clearer. $\endgroup$ – joriki Jul 14 '18 at 12:09
1
$\begingroup$

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)\ .$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.