4
$\begingroup$

There is a sequence $a_1, a_2, ..., a_n \in \mathbb R$, ($n$ is odd) such that if we delete one (any) number from it, then the rest of the numbers can be divided in two subsets of size $\lfloor \frac{n}{2} \rfloor$ and equal sum (sum of the first subset is equal to the sum of the second subset). How to prove that $a_1 = a_2 = ... = a_n$ ?

What I have tried

I can solve this task assuming that those numbers are integers, but I have no idea how to even start when those numbers are reals. For integers I would prove that all of those numbers have the same parity, then substract from every number the smallest number, so that at least one of them is 0 after this operation. But because all numbers have the same parity and there is 0, so all numbers are even. I can divide all of them by any power of 2, and the sequence will be still ok, so it means that all numbers are equal. This proof also works for rational numbers, because we can delete denominators (by multiplying all numbers by LCM of their denominators).

$\endgroup$
4
  • 2
    $\begingroup$ I can solve this task assuming that those numbers are integers, but I have no idea how to even start when those numbers are reals. For integers I would prove that all of those numbers have the same parity, then substract from every number the smallest number, so that at least one of them is 0 after this operation. But because all numbers have the same parity and there is 0, so all numbers are even. I can divide all of them by any power of 2, and the sequence will be still ok, so it means that all numbers are equal $\endgroup$
    – J. Abraham
    Nov 14, 2016 at 19:04
  • $\begingroup$ The same trick should work for rationals, right? You can clear denominators and get an integer sequence that works. $\endgroup$ Nov 14, 2016 at 19:28
  • $\begingroup$ But what about irrationals? $\endgroup$
    – J. Abraham
    Nov 14, 2016 at 20:05
  • $\begingroup$ What about induction on "n"? $\endgroup$
    – openspace
    Nov 15, 2016 at 7:25

2 Answers 2

5
$\begingroup$

You can reduce the real case to the rational case.

Let $V$ the $\mathbb{Q}$ vector space generated by $\{a_1,\dotsc,a_n\}$. If $\dim V = 0$, then $a_1 = a_2 = \dotsc = a_n = 0$ trivially. So let's consider the case $\dim V = k > 0$. Choose a basis $v_1,\dotsc, v_k$ of $V$, and let $\lambda_1,\dotsc,\lambda_k$ be the coordinate functionals with respect to this basis (so $\lambda_i(v_j) = \delta_{ij}$). Then for every $i$ with $1 \leqslant i \leqslant k$, the sequence $\lambda_i(a_1),\dotsc, \lambda_i(a_n)$ is a sequence of rational numbers with the desired property. So $\lambda_i(a_1) = \dotsc = \lambda_i(a_n)$. Since this holds for all $i$, we have $a_1 = \dotsc = a_n$ (and consequently $k = 1$).

$\endgroup$
8
  • $\begingroup$ Could you please provide some more elementary explanation? I don't know much about functionals etc. $\endgroup$
    – J. Abraham
    Nov 16, 2016 at 15:46
  • $\begingroup$ One doesn't need to know much, just that on a finite-dimensional vector space $V$ over the field $K$ with basis $v_1,\dotsc , v_k$, for every family $t_1,\dotsc, t_k$ of scalars there is a (unique) linear map $f\colon V\to K$ with $f(v_i) = t_i$. Do you know any linear algebra at all, or haven't you learned that yet? $\endgroup$ Nov 16, 2016 at 15:50
  • $\begingroup$ In fact, I don't know anything about linear algebra, except some basic properties of matrices. $\endgroup$
    – J. Abraham
    Nov 16, 2016 at 16:16
  • $\begingroup$ Hmm, inconvenient. Let me see whether I can come up with a linear algebra-free way. $\endgroup$ Nov 16, 2016 at 16:21
  • $\begingroup$ This is wonderfully clever actually. What we need is a linear function on rational sums of the $a_i$ that has an image in $\mathbb{Q}$. We can make one by setting $\lambda(a_1)=1$ (Assume WLOG that $a_1\neq 0$), and then if $a_i$ can be written as a sum of the $a_j$ with $j<i$ and rational coefficients, say $a_i=\sum_{j=1}^{i-1}b_ja_j$, then let $\lambda(a_i)=\sum_{j=1}^{i-1}b_j\lambda(a_j)$, otherwise $\lambda(a_i)=0$. Easy to see this is linear, and therefore solves the problem. That's all the linear algebra you really need. $\endgroup$ Nov 18, 2016 at 14:21
1
$\begingroup$

Here is a proof that relies on group theory

Let $\delta_{i,j} = a_i - a_j$ for $i,j \in [1, n]$, and let $$S_i = {1\over 2} \sum_{j\ne i}a_j$$

Finally let $G$ be the subgroup of $\Bbb R$ generated by $(\delta_{i,j})_{i,j\in [1,n]^2}$

We have that $2S_i + a_i = 2S_j + a_j$ by definition, thus $$\delta_{i,j} = 2(S_j - S_i)$$

Now the hypothesis claims that $S_i$ and $S_j$ both are sums of each $n-1\over 2$ elements. Thus their difference is the sum of $n-1\over 2$ differences of elements, which means that $${\delta_{i,j}\over2} = S_j - S_i \in G$$

Any element of $G$ being a sum of $\delta_{i,j}$ (by definition of $G$), it follows that $$\forall x\in G, {x\over2}\in G$$.

Now $G$ is a finitely generated subgroup of $\Bbb R$, thus there exists a basis of $G$, ie a family of reals $(x_1, \dots x_p)$ such that all element $x\in G$ can be written $$x = \sum_{i=1}^p n_i x_i$$ where the $n_i$ are integers, and so in a unique way.

Now suppose $G \ne \{0\}$. Then $p\ge 1$. We obviously have that $x_1 = 1\times x_1$ which is therefore the unique decomposition of $x_1$ in the basis. However we also have that $${x_1\over2}\in G$$ which means there exists integers $n_1, \dots, n_p$ such that $$x_1 = \sum_{i=1}^p 2n_i x_i$$ which contradicts the uniqueness of the decomposition of $x_1$. Thus $G=\{0\}$, and finally $\delta_{i,j} = 0$ for all $i,j$.

Thus all the masses are equal.

One interresting thing about this proof is that it generalises to $nk+1$ numbers that you can divide into $k$ sets of same mass when you take one out.

Here is another proof that relies on linear algebra : However it does not generalise the result as the other one does

Define $\epsilon_{i, j}$ as such :

  • If $i=j$, then $\epsilon_{i,j} = 0$

  • For $i\in [1,n]$, let $(\epsilon_{i,j})_{j\ne i}$ be such that $\sum_{j\ne i}{\epsilon_{i,j}m_j} = 0$

Thus we have for all $j$ that $$\sum_{j=1}^n \epsilon_{i,j}m_j =0$$ Let $$E = [\epsilon_{i,j}]_{i,j\in [1,n]}\\ A = \begin{pmatrix}a_1\\a_2\\\dots\\a_n\end{pmatrix} \\X = \begin{pmatrix}1\\1\\\dots\\1\end{pmatrix} $$

The equalities above rewrite as $EA = 0$. We also have $EX = 0$ since the two sets have same cardinality (ie $\sum_{j=1}^n\epsilon_{i,j} = 0$).

Let's try to find the rank of $E$ By adding all the collumns to the first one, we get the equivalent matrix $$ \begin{pmatrix}0&\pm1&\dots&\pm1\\0&0&&\pm1\\0&&\dots&\\0&\pm1&&0\end{pmatrix}$$

From there we can see the matrix is of rank $n-1$. Indeed the bottom right $n-1\times n-1$ matrix $$ \begin{pmatrix}0&\pm1&\pm1\\\pm1&\dots&\pm1\\\pm1&\pm1&0\end{pmatrix} $$ is equivalent mod 2 to $$\begin{pmatrix}0&1&1\\1&\dots&1\\1&1&0\end{pmatrix} $$ (0's on the diagonal and 1's everywhere else) which itself is equivalent to $$\begin{pmatrix}1&1&\dots&1\\1&0&&1\\1&&\dots&\\1&1&&0\end{pmatrix}$$ by adding all the collumns to the first line, since $n-1$ is even, and by removing the first line to all others, we finally get $$ \begin{pmatrix}1&1&\dots&1\\0&1&&0\\0&&\dots&\\0&0&&1\end{pmatrix} $$ which is of rank determinant 1 mod 2, which means the determinant of the bottom right matrix $E$ is odd and thus cannot be 0. Thus $E$ is of rank $n-1$. What follows from this is that $\dim \ker E =1$, thus $A\in Vect(X)$, which means all the mass are equal.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .