5
$\begingroup$

Let $S$ be a finite collection of real numbers (not necessarily distinct). If any element of $S$ is removed then the remaining real numbers can be divided into two collections with same size and same sum ; then is it true that all elements of $S$ are equal ?

(I know the result is true if the "reals" are replaced by "integers".)

$\endgroup$
9
  • 1
    $\begingroup$ @user137481 your S doesnt seem to satisfy the requirement that if any element of S is removed. For example, if 4 is removed, 1+2+3+5 is 11, cannot be divided into two collections. $\endgroup$
    – k99731
    Nov 3, 2014 at 4:51
  • $\begingroup$ @Souvik Dey Do you know the proof of the statement in the intergers case? $\endgroup$
    – k99731
    Nov 3, 2014 at 4:54
  • $\begingroup$ Sounds like a linear algebra problem to me. $\endgroup$
    – bof
    Nov 3, 2014 at 11:26
  • $\begingroup$ In other words you are asking: if $A$ is a $(2n+1)\times(2n+1)$ matrix with all diagonal entries $0$ and all other entries $\pm1$, with an equal number of $+1$'s and $-1$'s on each row, must $A$ have rank $2n$, meaning that the equation $A\mathbf x=\mathbf0$ has no solutions other than $x_1=x_2=\cdots=x_n$? So it doesn't matter if the numbers are rational or real or complex, does it? $\endgroup$
    – bof
    Nov 3, 2014 at 13:00
  • 1
    $\begingroup$ @k99731 Outline of a proof of the integer case would be: Because the sum of remaining elements if any element is removed has to be even, either all elements in $S$ are odd or all elements in $S$ are even. If they are odd, apply map $x\mapsto (x-1)/2$ to get a new collection $S'$, and if they are even, apply map $x\mapsto x/2$ to get a new collection $S'$. Repeating this, the maxmimum number decreases until its $0$ or $1$ and the minimum number increases until its $0$ or $1$. Thus we end up with a set with only $0$s or only $1$s. Each map used was bijective, so elements in $S$ were equal. $\endgroup$
    – JiK
    Nov 4, 2014 at 9:36

3 Answers 3

7
$\begingroup$

Call an $n$-tuple ${\bf a}=(a_1,a_2,\ldots,a_n)\in{\mathbb R}^n$ good if it has the property of the "collection" $S$ described in the question. Then obviously $n$ is odd. Let ${\bf 1}:=(1,1,\ldots,1)\in{\mathbb R}^n.$

Claim 0: When ${\bf a}$ is good then the $n$-tuples $$\lambda{\bf a}+\mu{\bf 1}\qquad(\lambda, \mu\in{\mathbb R})$$ are good as well.

Claim 1: If ${\bf a}\in{\mathbb Z}^n$ is good then ${\bf a}=a\>{\bf 1}$ for some $a\in{\mathbb Z}$.

Proof. After adding some ${\bf p}=p{\bf 1}$, $p\in{\mathbb Z}$, to ${\bf a}$ we may assume that all entries $a_k$ are nonnegative. Call $|{\bf a}|:=\sum_{k=1}^n a_k$ the norm of ${\bf a}$. We proceed by induction on the norm. When $|{\bf a}|=0$ the claim is true. Therefore assume that the claim is true for all nonnegative $n$-tuples ${\bf a}'$ with $|{\bf a}'|<|{\bf a}|$. Since $|{\bf a}|-a_k$ is even for all $k$ it follows that either all $a_k$ are even, or all $a_k$ are odd (whence $\geq1$). In the first case ${\bf a'}:={1\over 2}{\bf a}$, and in the second case ${\bf a}':={\bf a}-{\bf 1}$, is a good nonnegative integer $n$-tuple with smaller norm. It follows that the claim holds for ${\bf a}$.

Claim 2: If ${\bf a}\in{\mathbb Q}^n$ is good then ${\bf a}=a\>{\bf 1}$ for some $a\in{\mathbb Q}$.

Claim 3: If ${\bf a}\in{\mathbb R}^n$ is good then ${\bf a}=\alpha\>{\bf 1}$ for some $\alpha\in{\mathbb R}$.

Proof. Let ${\bf a}\in{\mathbb R}^n$ be good. The set $$V:=\left\{\sum_{k=1}^n r_k \ a_k\>\biggm|\>r_k\in{\mathbb Q}\right\}\subset{\mathbb R}$$ is a finitely generated vector space over ${\mathbb Q}$, whence finite-dimensional. Let $(e_i)_{1\leq i\leq r}$ be a basis of $V$, and let $(\phi_i)_{1\leq i\leq r}$ be the corresponding dual basis (the $r$ coordinate functionals).

Since ${\bf a}$ is good it follows by linearity that for each $i$ the $n$-tuple $\bigl(\phi_i(a_1),\phi_i(a_2),\ldots,\phi_i(a_n)\bigr)\in{\mathbb Q}^n$ is good. Claim 2 then implies that there are numbers $q_i\in{\mathbb Q}$ $\>(1\leq i\leq r)$ with $$\phi_i(a_k)=q_i\qquad(1\leq k\leq n)\ .$$ The latter can be rewritten as $$a_k=\sum_{i=1}^r q_i\> e_i=:\alpha\in{\mathbb R}\qquad(1\leq k\leq n)\ ,$$ and this is tantamount to ${\bf a}=\alpha\>{\bf 1}$.

$\endgroup$
4
  • $\begingroup$ Is your good $n$-tuple the set $S$ of my question ? $\endgroup$
    – Souvik Dey
    Nov 14, 2014 at 12:07
  • $\begingroup$ @Souvik Dey: Yes; I have modeled your "set" or "collection" $S$ by an $n$-tuple. $\endgroup$ Nov 14, 2014 at 13:13
  • 1
    $\begingroup$ This is a very clever and well presented solution. $\endgroup$ Nov 14, 2014 at 13:32
  • $\begingroup$ Surely it's the case that in general, if $(b_i)$ is a basis for $\ker A$ over $\mathbb Q$, where $A$ has rational entries, then $(b_i)$ is also a basis for $\ker A$ over $\mathbb R$, no? In which case Claim 2 immediately implies Claim 3. $\endgroup$
    – Jack M
    Jan 11, 2016 at 19:45
2
$\begingroup$

Yes, all elements of $S$ must be equal.

Clearly, $S$ has an odd number of elements; say $S=\{x_1,\dots,x_{2n+1}\}$. The condition "if any element of $S$ is removed then the remaining real numbers can be divided into two collections with same size and same sum" means that the column vector $\mathbf X=[x_1,\dots,x_{2n+1}]^T$ satisfies a matrix equation of the form $A\mathbf X=\mathbf0$ for some $2n+1\times 2n+1$ matrix $A$ with all diagonal entries $0$, all off-diagonal entries $\pm1$, and equal numbers of $+1$s and $-1$s on each row. All we have to do is show that such a matrix must have rank $2n$; its right null space must then be $1$-dimensional, so it contains only the constant vectors $[x,x,\dots,x]^T$. In fact, working in$\!\mod2\,$ arithmetic for simplicity, it's easy to see that the matrix can be reduced by elementary row operations to an upper triangular form with $2n$ ones and a zero on the diagonal. (Namely, swap the first two rows, and subtract them from all rows below them; swap the next two rows, and subtract them from all rows below them; and so on.)

To put it more generally, if $A$ is a square matrix of odd order $2n+1$, and if all diagonal entries are even integers, and all off-diagonal entries are odd integers, then the rank of $A$ is at least $2n$.

Alternatively, if the equation $A\mathbf X=\mathbf0$ had a nonconstant solution, it would also have a nonconstant integer solution; but the OP has already proved (see also JiK's comment on the question) the result for integers.

$\endgroup$
2
  • $\begingroup$ Is it clear that the rank of $A$ over $\mathbb{Q}$ must be at least as great as its rank over $\mathbb{F}_2$? $\endgroup$ Nov 14, 2014 at 15:37
  • 1
    $\begingroup$ @MichaelJoyce I don't know any theory, I'm not an algebraist. In this case, what the "mod 2" computation means in real arithmetic is that A is row-equivalent to a matrix of integers where all entries below the diagonal are even and there are 2n odd entries on the diagonal. So there's a 2n X 2n submatrix with all odd integers on the diagonal and even integers below; the determinant of that submatrix is an odd integer, so it's nonzero. $\endgroup$
    – bof
    Nov 14, 2014 at 16:16
0
$\begingroup$

I am not sure whether whether it is true or not. Hope this help. I think the statement is true.

I have to use your result.

Easily see that the property is true if reals is replaced by rationals.

Lemma 0: (if this is wrong, you dont need to read anymore)

If S satisfies the property, then $a S + b$ for real $a$, $b$ also satisfies the property. Here $a S$ means ${a s_1, a s_2, ...}$.

I now introduce something call relative irrational. $r_1$ and $r_2$ are relative irrational if $a r_1+b \neq r_2$ for any rational $a$, $b$. I dont know whether this is well-defined. If not, I guess my proof will fail immediately.

Claim: for any real x, there is a finite sequence of irrational $r_1$, $r_2$, $r_3$, ..., $r_n$ and a rational $q_0$ such that $x=q_1 r_1 + ... + q_n r_n+q_0$, where $q_1, ..., q_n$ are rational. For finite number of real in S, there is of course finite number of $r$. Let the number of relatively irrational used be $n$. Then for any $s \in S$, $s=q_1 r_1 + ... + q_n r_n+q_0$ for some rationals $q_1, ..., q_n$.

When we removing arbitrary element from S, it can be divided into two collections with same size and sum. Considering their sum, we can find that the sum of coefficients of $r_k$ of one side is equal to that of the other. Also, the sum of rational of one side is equal to the other.

We focus on the sum of rational first. It is easily to see that (or I am wrong) the rational terms of each $s \in S$ are equal, using the result given, since the collection composed by rational part of each $s \in S$ satisfies the property. Similarly, for any $r_k$, the collection composed by $q_k$ satisfies the property. Then all $q_k$ are equal in each $s \in S$.

$\endgroup$
7
  • $\begingroup$ Does the "Claim: for any real $x$ ..." part mean that $q_1,q_2,\dots,q_n$ are fixed and then there are irrational $r_1,r_2,\dots,r_n$ for each $x$? $\endgroup$
    – JiK
    Nov 3, 2014 at 10:39
  • $\begingroup$ @JiK I want to say for each $x$ there is finite $n$ such that we can pick a representation $x=q_1 r_1 + ... + q_n r_n + q_0$, where $q$'s are rationals and $r$'s are irrationals. $\endgroup$
    – k99731
    Nov 3, 2014 at 10:48
  • $\begingroup$ Let me try to rephrase my question: Can you pick for example $n=1$, $q_1=1$, $r_1=x$, $q_0=0$ for irrational $x$ and $n=0$, $q_0=x$ for rational $x$? $\endgroup$
    – JiK
    Nov 3, 2014 at 10:50
  • $\begingroup$ @JiK Yes(Comments must be at least 15 characters in length.) $\endgroup$
    – k99731
    Nov 3, 2014 at 10:54
  • 1
    $\begingroup$ What you are driving at is the following: The numbers in $S$ generate a finite-dimensional ${\mathbb Q}$-vector space $V\subset{\mathbb R}$; therefore a certain subset of $S$ constitutes a basis of $V$. Now apply the theorem for sets $S\subset{\mathbb Z}$ to the representations of the $r_i\in S$ with respect to this basis. $\endgroup$ Nov 3, 2014 at 11:06

You must log in to answer this question.

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