CaptainBlack's Problem of the Week #1

[CaptainBlack]

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]

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]

\[\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

 

[Sudharaka]

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. :p

 

[CaptainBlack]

Hint: CaptainBlack's Problem of the Week #1

Hint:

[sp]
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) \)

[/sp]

CB

 

[Sudharaka]

\[\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]

\[\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]

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]

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

 

[caffeinemachine]

\[\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]

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! (Wave)

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]

Hi! (Wave)

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]

I don't think that's right. $-0.7>-1, -0.8>-1$ but $-(0.7+0.8) \not > -1$

Ahhh...(Headbang) 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]

Ahhh...(Headbang) 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.