# CaptainBlack's Problem of the Week #1

#### CaptainBlack

##### Well-known member
Let $$x_1, ..., x_n$$ be real numbers such that:

$$\sum_{i=1}^n x_i=0$$ and $$\sum_{i=1}^n x_i^2=1$$

Prove that for some $$k,l$$ both in $$\{1, .. , n\}$$ that $$x_k x_l\le -1/n$$

CB

#### Sudharaka

##### Well-known member
MHB Math Helper
Let $$x_1, ..., x_n$$ be real numbers such that:

$$\sum_{i=1}^n x_i=0$$ and $$\sum_{i=1}^n x_i^2=1$$

Prove that for some $$k,l$$ both in $$\{1, .. , n\}$$ that $$x_k x_l\le -1/n$$

CB
$\left(\sum_{i=1}^{n}x_{i}\right)^2=\sum_{i=1}^{n}x_{i}^{2}+\sum_{k\neq l}x_{k}x_{l}\mbox{ where }k,l\in\{1,\cdots,n\}$

$\Rightarrow 0=1+\sum_{k\neq l}x_{k}x_{l}$

$\Rightarrow\sum_{k\neq l}x_{k}x_{l}=-1~-------(1)$

Let $$A=\{x_{k}x_{l}:k\neq l\mbox{ and }k,l\in\{1,\cdots,n\}\}$$. Notice that, $$|A|=n(n-1)$$. Take $$m=\mbox{min}(A)$$. Then,

$m\leq x_{k}x_{l}\forall~k,l\in\{1,\cdots,n\}\mbox{ where }k\neq l$

Since $$|A|=n(n-1)$$

$mn(n-1)\leq\sum_{k\neq l}x_{k}x_{l}~-------(2)$

By (1) and (2);

$mn(n-1)\leq -1$

$m\leq\frac{-1}{n(n-1)}~------(3)$

Suppose that, $$x_{k}x_{l}>-\frac{1}{n}~\forall~k,l\in\{1,\cdots,n\}$$. Then,

$m>-\frac{1}{n}~------(4)$

By (3) and (4);

$-\frac{1}{n}<m\leq\frac{-1}{n(n-1)}$

$\Rightarrow n>2$

Therefore in order for our assumption to be true $$n$$ should be greater than 2. Consider the set, $$\left\{\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right\}$$. This set has two elements but, $$\displaystyle\sum_{i=1}^{2}x_{i}=0\mbox{ and }\sum_{i=1}^{n}x_{i}^{2}=1$$. Therefore our assumption is wrong.

$x_{k}x_{l}\leq -\frac{1}{n}\mbox{ for some }k,l\in\{1,\cdots,n\}$

#### CaptainBlack

##### Well-known member
$\left(\sum_{i=1}^{n}x_{i}\right)^2=\sum_{i=1}^{n}x_{i}^{2}+\sum_{k\neq l}x_{k}x_{l}\mbox{ where }k,l\in\{1,\cdots,n\}$

$\Rightarrow 0=1+\sum_{k\neq l}x_{k}x_{l}$

$\Rightarrow\sum_{k\neq l}x_{k}x_{l}=-1~-------(1)$

Let $$A=\{x_{k}x_{l}:k\neq l\mbox{ and }k,l\in\{1,\cdots,n\}\}$$. Notice that, $$|A|=n(n-1)$$. Take $$m=\mbox{min}(A)$$. Then,

$m\leq x_{k}x_{l}\forall~k,l\in\{1,\cdots,n\}\mbox{ where }k\neq l$

Since $$|A|=n(n-1)$$

$mn(n-1)\leq\sum_{k\neq l}x_{k}x_{l}~-------(2)$

By (1) and (2);

$mn(n-1)\leq -1$

$m\leq\frac{-1}{n(n-1)}~------(3)$

Suppose that, $$x_{k}x_{l}>-\frac{1}{n}~\forall~k,l\in\{1,\cdots,n\}$$. Then,

$m>-\frac{1}{n}~------(4)$

By (3) and (4);

$-\frac{1}{n}<m\leq\frac{-1}{n(n-1)}$

$\Rightarrow n>2$

Therefore in order for our assumption to be true $$n$$ should be greater than 2. Consider the set, $$\left\{\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right\}$$. This set has two elements but, $$\displaystyle\sum_{i=1}^{2}x_{i}=0\mbox{ and }\sum_{i=1}^{n}x_{i}^{2}=1$$. Therefore our assumption is wrong.

$x_{k}x_{l}\leq -\frac{1}{n}\mbox{ for some }k,l\in\{1,\cdots,n\}$
In your example for $$n=2$$ (which is essentially the only $$n=2$$ possibility satisfying the given conditions):

$$i=1, j=2$$, then $$x_ix_j=-\frac{1}{2}=-\frac{1}{n}\le -\frac{1}{n}$$

Which disposes of the case where $$n=2$$

CB

Last edited:

#### Sudharaka

##### Well-known member
MHB Math Helper
In your example for $$n=2$$ (which is essentially the only $$n=2$$ possibility satisfying the given conditions):

$$i=1, j=2$$, then $$x_ix_j=-\frac{1}{2}=-\frac{1}{n}\le -\frac{1}{n}$$

Which disposes of the case where $$n=2$$

CB
I see that my answer is incorrect. Thank you for pointing that out. Back to square one.

#### CaptainBlack

##### Well-known member
Hint: CaptainBlack's Problem of the Week #1

Hint:

Let $$a=\max(x_i, i=1, .. , n)$$ and $$b=\min(x_i, i=1, .. , n)$$ and then consider $$f(x)=(x-a)(x-b)$$

CB

Last edited by a moderator:

#### Sudharaka

##### Well-known member
MHB Math Helper
$\left(\sum_{i=1}^{n}x_{i}\right)^2=\sum_{i=1}^{n}x_{i}^{2}+\sum_{k\neq l}x_{k}x_{l}\mbox{ where }k,l\in\{1,\cdots,n\}$

Since $$\displaystyle\sum_{i=1}^{n}x_{i}=0$$,

$\sum_{i=1}^{n}x_{i}^{2}=-\sum_{k\neq l}x_{k}x_{l}~~~~~~~~~(1)$

Suppose that, $$x_{k}x_{l}>-\frac{1}{n}~\forall~k,l\in\{1,\cdots,n\}$$. Then,

$\sum_{k\neq l}x_{k}x_{l}>-\frac{1}{n}$

$\Rightarrow -\sum_{k\neq l}x_{k}x_{l}<\frac{1}{n}~~~~~~~~~(2)$

By (1) and (2);

$\sum_{i=1}^{n}x_{i}^{2}<\frac{1}{n}<1$

This is a contradiction. Hence,

$x_{k}x_{l}\leq -\frac{1}{n}\mbox{ for some }k,l\in\{1,\cdots,n\}$

#### CaptainBlack

##### Well-known member
$\left(\sum_{i=1}^{n}x_{i}\right)^2=\sum_{i=1}^{n}x_{i}^{2}+\sum_{k\neq l}x_{k}x_{l}\mbox{ where }k,l\in\{1,\cdots,n\}$

Since $$\displaystyle\sum_{i=1}^{n}x_{i}=0$$,

$\sum_{i=1}^{n}x_{i}^{2}=-\sum_{k\neq l}x_{k}x_{l}~~~~~~~~~(1)$

Suppose that, $$x_{k}x_{l}>-\frac{1}{n}~\forall~k,l\in\{1,\cdots,n\}$$. Then,

$\sum_{k\neq l}x_{k}x_{l}>-\frac{1}{n}$

$\Rightarrow -\sum_{k\neq l}x_{k}x_{l}<\frac{1}{n}~~~~~~~~~(2)$

By (1) and (2);

$\sum_{i=1}^{n}x_{i}^{2}<\frac{1}{n}<1$

This is a contradiction. Hence,

$x_{k}x_{l}\leq -\frac{1}{n}\mbox{ for some }k,l\in\{1,\cdots,n\}$
There is a constructive proof which produces a pair $$x_k, x_l$$ that will result in satisfaction of the inequality.

CB

#### Sudharaka

##### Well-known member
MHB Math Helper
Re: Hint: CaptainBlack's Problem of the Week #1

Hint:

Let $$a=\max(x_i, i=1, .. , n)$$ and $$b=\min(x_i, i=1, .. , n)$$ and then consider $$f(x)=(x-a)(x-b)$$

CB
$f(x_{i})=(x_{i}-a)(x_{i}-b)=x_{i}^{2}-x_{i}(a+b)+ab$

$\Rightarrow\sum_{i=1}^{n}f(x_{i})=\sum_{i=1}^{n}x_{i}^{2}-(a+b)\sum_{i=1}^{n}x_{i}+ab\sum_{i=1}^{n}1$

$\Rightarrow\sum_{i=1}^{n}f(x_{i})=1+abn~~~~~~~(1)$

Also note that since $$a=\max(x_i, i=1,\cdots, n)$$ and $$b=\min(x_i, i=1,\cdots, n)$$,

$x_{i}-a\leq 0\mbox{ and }x_{i}-b\geq 0~\forall~i=1,\cdots,n$

$\therefore\sum_{i=1}^{n}f(x_{i})=\sum_{i=1}^{n}(x_{i}-a)(x_{i}-b)\leq 0~~~~~~~(2)$

By (1) and (2);

$1+abn\leq 0$

$\Rightarrow ab\leq -\frac{1}{n}$

So we have found a $$x_{k}\mbox{ and a }x_{l}$$ (equal to $$a$$ and $$b$$) so that $$x_{k}x_{l}\leq -\frac{1}{n}$$

I am pretty sure that this is the answer that you have in mind. Isn't?

#### CaptainBlack

##### Well-known member
Re: Hint: CaptainBlack's Problem of the Week #1

$f(x_{i})=(x_{i}-a)(x_{i}-b)=x_{i}^{2}-x_{i}(a+b)+ab$

$\Rightarrow\sum_{i=1}^{n}f(x_{i})=\sum_{i=1}^{n}x_{i}^{2}-(a+b)\sum_{i=1}^{n}x_{i}+ab\sum_{i=1}^{n}1$

$\Rightarrow\sum_{i=1}^{n}f(x_{i})=1+abn~~~~~~~(1)$

Also note that since $$a=\max(x_i, i=1,\cdots, n)$$ and $$b=\min(x_i, i=1,\cdots, n)$$,

$x_{i}-a\leq 0\mbox{ and }x_{i}-b\geq 0~\forall~i=1,\cdots,n$

$\therefore\sum_{i=1}^{n}f(x_{i})=\sum_{i=1}^{n}(x_{i}-a)(x_{i}-b)\leq 0~~~~~~~(2)$

By (1) and (2);

$1+abn\leq 0$

$\Rightarrow ab\leq -\frac{1}{n}$

So we have found a $$x_{k}\mbox{ and a }x_{l}$$ (equal to $$a$$ and $$b$$) so that $$x_{k}x_{l}\leq -\frac{1}{n}$$

I am pretty sure that this is the answer that you have in mind. Isn't?
Yes

==========================================================

Let $$x_1, ..., x_n$$ be real numbers such that:

$$\sum_{i=1}^n x_i=0$$ and $$\sum_{i=1}^n x_i^2=1$$

Prove that for some $$k,l$$ both in $$\{1, .. , n\}$$ that $$x_k x_l\le -1/n$$

CB

===========================================================

Solution

Let $$a=\max(x_1, ... , x_n)$$ and $$b=\min(x_1, ... , x_n)$$, and put:

$f(x)=(x-a)(x-b)=x^2-(a+b)\; x+ab$

Then by construction $$f(x_i)\le 0,\;i=1, ... , n$$ . Now consider:

$\sum_{i=1}^n f(x_i)=\sum_{i=1}^n x^2 -(a+b) \sum_{i=1}^n x_i +n\;ab = 1+n\;ab \le 0$

hence:

$ab \le -\frac{1}{n}$

QED

Last edited:

#### caffeinemachine

##### Well-known member
MHB Math Scholar
$\left(\sum_{i=1}^{n}x_{i}\right)^2=\sum_{i=1}^{n}x_{i}^{2}+\sum_{k\neq l}x_{k}x_{l}\mbox{ where }k,l\in\{1,\cdots,n\}$

Since $$\displaystyle\sum_{i=1}^{n}x_{i}=0$$,

$\sum_{i=1}^{n}x_{i}^{2}=-\sum_{k\neq l}x_{k}x_{l}~~~~~~~~~(1)$

Suppose that, $$x_{k}x_{l}>-\frac{1}{n}~\forall~k,l\in\{1,\cdots,n\}$$. Then,

$\sum_{k\neq l}x_{k}x_{l}>-\frac{1}{n}$

$\Rightarrow -\sum_{k\neq l}x_{k}x_{l}<\frac{1}{n}~~~~~~~~~(2)$

By (1) and (2);

$\sum_{i=1}^{n}x_{i}^{2}<\frac{1}{n}<1$

This is a contradiction. Hence,

$x_{k}x_{l}\leq -\frac{1}{n}\mbox{ for some }k,l\in\{1,\cdots,n\}$
Hi Sudharaka.

I couldn't get the "then" part in the following:

Suppose that $x_k x_l > - \frac{1}{n} \forall k,l \in \{ 1, \ldots, n \}$. THEN $\displaystyle\sum_{k \neq l}x_k x_l > - \frac{1}{n}$

#### Sudharaka

##### Well-known member
MHB Math Helper
Hi Sudharaka.

I couldn't get the "then" part in the following:

Suppose that $x_k x_l > - \frac{1}{n} \forall k,l \in \{ 1, \ldots, n \}$. THEN $\displaystyle\sum_{k \neq l}x_k x_l > - \frac{1}{n}$
Hi!

Since $x_{k}x_{l}>- \frac{1}{n}~\forall~k,l \in \{ 1, \ldots, n \}$, the addition of any finite number of terms in the set $\{x_k x_l:k,l\in\{1,\ldots,n\}\}$ is also greater than $-\frac{1}{n}$. This stems from the result; if $a>b\mbox{ and }c>b\Rightarrow a+c>b\mbox{ where }a,b,c\in\Re$.

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Hi!

Since $x_{k}x_{l}>- \frac{1}{n}~\forall~k,l \in \{ 1, \ldots, n \}$, the addition of any finite number of terms in the set $\{x_k x_l:k,l\in\{1,\ldots,n\}\}$ is also greater than $-\frac{1}{n}$. This stems from the result; if $a>b\mbox{ and }c>b\Rightarrow a+c>b\mbox{ where }a,b,c\in\Re$.
I don't think that's right. $-0.7>-1, -0.8>-1$ but $-(0.7+0.8) \not > -1$

#### Sudharaka

##### Well-known member
MHB Math Helper
I don't think that's right. $-0.7>-1, -0.8>-1$ but $-(0.7+0.8) \not > -1$
Ahhh..... Indeed it is incorrect. It should be $a>b\mbox{ and }c>b\Rightarrow a+c>2b\mbox{ where }a,b,c\in\Re$ I don't how I made such a terrible mistake but thanks for pointing that out. That being said the solution is incorrect with reference to this mistake. I think CB's constructive proof is the only method to tackle this problem.

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Ahhh..... Indeed it is incorrect. It should be $a>b\mbox{ and }c>b\Rightarrow a+c>2b\mbox{ where }a,b,c\in\Re$ I don't how I made such a terrible mistake but thanks for pointing that out. That being said the solution is incorrect with reference to this mistake. I think CB's constructive proof is the only method to tackle this problem.
CB's solution is correct.. but very "unnatural" to me. I don't have another solution. I had observed a crucial (and simple) thing. If there exist $k,l \in \{ 1, \ldots, n\}$ such that $x_k x_l < -\frac{1}{n}$ then certainly $ab< - \frac{1}{n}$ where $a=\min \{x_1, \ldots, x_n \}, b= \max \{x_1, \ldots, x_n \}$. So one should aim to show that $ab < - \frac{1}{n}$.
To define a quadratic polynomial with $a,b$ as its roots in order to solve this is way too clever for me. I strongly believe there is a "simple minded" solution too.