A proposed problem of IMO

Discussion on International Mathematical Olympiad (IMO)
User avatar
SANZEED
Posts: 550
Joined: Wed Dec 28, 2011 6:45 pm
Location: Mymensingh, Bangladesh

A proposed problem of IMO

Unread post by SANZEED » Thu Jan 26, 2012 7:51 am

If $c_{1},c_{2},....,c_{n}$ are real numbers ($n>=2$) such that
$(n-1)(c_{1}^{2}+c_{2}^{2}+.....+c_{n}^{2})=(c_{1}+c_{2}+.....+c_{n})^{2}$
Show that either all of them are non-negative,or all of them are non positive.[Proposed by czechoslovakia in 1977, was unused]
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: A proposed problem of IMO

Unread post by Phlembac Adib Hasan » Thu Jan 26, 2012 12:36 pm

A nice place to use induction.
My Proof :
Surely it's true for $n=2,3$.Now let it is true for $n=k$.Means \[(k-1) \sum_{p=1}^k c_p^2=(\sum_{p=1}^k c_p)^2 \]
We have to prove it for $n=k+1$.
Let a new number be $c_{k+1} $ so that it follows $k \sum_{p=1}^{k+1} c_p^2=(\sum_{p=1}^{k+1} c_p)^2$.As all $c_p$s(without $c_{k+1}$) are either non-negative or non-positive, .So if $c_{k+1}$ is of opposite sign, the inequality follows: \[ k\sum_{p=1}^{k+1}c_p^2\geq \left ( k-1 \right )\sum_{p=1}^{k}c_p^2=\left ( \sum_{p=1}^{k}c_p \right )^2\geq \left ( \sum_{p=1}^{k+1}c_p \right )^2\] with equality iff $c_{k+1}=0$.So our proof is complete.
Last edited by Phlembac Adib Hasan on Fri Jan 27, 2012 9:55 am, edited 1 time in total.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

Re: A proposed problem of IMO

Unread post by sourav das » Thu Jan 26, 2012 1:55 pm

Adib, try to find bug in your solution (if it has any) and reply why you are right or wrong...

Solution:
For the sake of contradiction let $c_{i}c_j<0$. So it follows that $\sqrt{c_{i}^2+c_{j}^2}>|c_{i}+c_{j}|$


Now using Cauchy-Schwartz's inequality for $n-1$ terms:

$(n-1)(\sum^{n-2}c_{k}^2 + c_{i}^2+c_{j}^2)\geq (\pm(\sum^{n-2}c_{k}) + \sqrt{c_{i}^2+c_{j}^2})^2 $
notice that either, $(\sum^{n-2}c_{k})+|c_{i}+c_{j}|\geq |\sum c_i|$ or $-(\sum^{n-2}c_{k})+|c_{i}+c_{j}|\geq |\sum c_i|$
As, $\sqrt{c_{i}^2+c_{j}^2}>|c_{i}+c_{j}|$
$(n-1)(\sum^{n-2}c_{k}^2 + c_{i}^2+c_{j}^2)>( \sum c_i)^2$

So our assumption was wrong.
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: A proposed problem of IMO

Unread post by Phlembac Adib Hasan » Fri Jan 27, 2012 9:53 am

Yes.There is.But it is not a bug of my proof.I'll say it "typing mistake"-I wrote $(n-1)$ instead of $k$ and $(k-1)$ unmindfully.Now it is edited.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

Re: A proposed problem of IMO

Unread post by sourav das » Fri Jan 27, 2012 10:28 am

Phlembac Adib Hasan wrote:A nice place to use induction.
My Proof :
Surely it's true for $n=2,3$.Now let it is true for $n=k$.Means \[(k-1) \sum_{p=1}^k c_p^2=(\sum_{p=1}^k c_p)^2 \]
We have to prove it for $n=k+1$.
Let a new number be $c_{k+1} $ so that it follows $k \sum_{p=1}^{k+1} c_p^2=(\sum_{p=1}^{k+1} c_p)^2$.As all $c_p$s(without $c_{k+1}$) are either non-negative or non-positive, .So if $c_{k+1}$ is of opposite sign, the inequality follows: \[ k\sum_{p=1}^{k+1}c_p^2\geq \left ( k-1 \right )\sum_{p=1}^{k}c_p^2=\left ( \sum_{p=1}^{k}c_p \right )^2\geq \left ( \sum_{p=1}^{k+1}c_p \right )^2\] with equality iff $c_{k+1}=0$.So our proof is complete.
Ok, then explain me, in your induction step you assume that IF\[(k-1) \sum_{p=1}^k c_p^2=(\sum_{p=1}^k c_p)^2 \].....(i) holds ONLY THEN All $C_i$ satisfy the condition. But in second step
\[k \sum_{p=1}^{k+1} c_p^2=(\sum_{p=1}^{k+1} c_p)^2\]....... (ii) doesn't need to satisfy (i). So you can't say "As all $c_p$s(without $c_{k+1}$) are either non-negative or non-positive".
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: A proposed problem of IMO

Unread post by Phlembac Adib Hasan » Tue Jan 31, 2012 9:45 am

No.No.You may misunderstand (ii).I used same $c_p$s in (ii), as in (i).I only added such a number $c_{k+1}$ in $c_p$s so that they fulfills (ii).I defined (i) before.So I can say all $c_p$s (without $c_{p+1}$) are of same sign.I only showed if the statement is true for $k$ variables, it will also be true for $k+1$ variables.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

Re: A proposed problem of IMO

Unread post by sourav das » Tue Jan 31, 2012 10:46 am

Phlembac Adib Hasan wrote:No.No.You may misunderstand (ii).I used same $c_p$s in (ii), as in (i).I only added such a number $c_{k+1}$ in $c_p$s so that they fulfills (ii).I defined (i) before.So I can say all $c_p$s (without $c_{p+1}$) are of same sign.I only showed if the statement is true for $k$ variables, it will also be true for $k+1$ variables.
Actually, I still don't understand. (I'm very dull in understanding) . Just answer the following questions:
(i)In your induction you assume that for any $k$ variables that satisfies the given condition must be all same in sign. Next you take a set of {$c_1,c_2.....c_k$} that satisfy the given condition(***). Next you work with adding a $c_{k+1}$ (So that {$c_1,c_2.....c_k,c_{k+1}$ also satisfy the condition})and showing $c_{k+1}$ also same sign as others,that's why you demand that for any $k+1$ element it'll be true. Am i right?

(ii)If you agree with (i) then tell me one thing. It may possible that we can find a set A={$c_1,c_2....c_{k+1}$}
such that it satisfy the given condition but any $k$ element subset of A doesn't satisfy the given condition. So your induction clearly doesn't work for those type $k+1$ element sets.

Actually i think you are choosing the value of variables.
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: A proposed problem of IMO

Unread post by Phlembac Adib Hasan » Wed Feb 01, 2012 7:54 pm

No, you may missed something.Just look at my definition of $c_{k+1}$.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Corei13
Posts: 153
Joined: Tue Dec 07, 2010 9:10 pm
Location: Chittagong

Re: A proposed problem of IMO

Unread post by Corei13 » Wed Feb 01, 2012 9:31 pm

@Adib:
Your Induction hypothesis is not enough to prove the problem, it just proves a case of the given problem.

Note that, the problem asked you to prove for all $c_i$ with only one condition $(n-1)\sum_{i\le n}{c_i^2} = \left ( \sum_{i\le n}{c_i} \right )^2$. That is, you can't add a extra constraint $(n-2)\sum_{i<n}{c_i^2} = \left ( \sum_{i < n}{c_i} \right )^2$ unless you prove that, $(n-1)\sum_{i\le n}{c_i^2} = \left ( \sum_{i\le n}{c_i} \right )^2 \Longrightarrow (n-2)\sum_{i<n}{c_i^2} = \left ( \sum_{i < n}{c_i} \right )^2$(which is actually not true). But you added this extra constraint with your hypothesis. So, you just proved a case.
ধনঞ্জয় বিশ্বাস

User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: A proposed problem of IMO

Unread post by Phlembac Adib Hasan » Sat Feb 04, 2012 8:48 am

Ok,I want to end all argument.That proof has been withdrawn.Here I'm giving another proof.
Let $a_1,a_2,...,a_m,-a_{m+1},-a_{m+2},...,-a_n\; \; \; \; \; $ be a permutation of $c_1,c_2,...,c_n$ with all non-negative $a_i$s (and all of them are not equal to $0$).Now I'll show they can cot follow the given condition.(A proof using contradiction).Let they follow given condition: \[(n-1) \left ( \sum_{p=1}^{n} a_p^2\right )=\left ( \sum_{p=1}^n a_p \right )^2\]
\[\Rightarrow (n-1) \left ( \sum_{p=1}^{m} a_p^2\right )+(n-1) \left ( \sum_{p=m+1}^{n} a_p^2\right )=\left ( \sum_{p=1}^m a_p- \sum_{p=m+1}^n a_p\right )^2\]
\[\Rightarrow (n-1) \left ( \sum_{p=1}^{m} a_p^2\right )+(n-1) \left ( \sum_{p=m+1}^{n} a_p^2\right )=\left ( \sum_{p=1}^m a_p\right )^2 \] \[ -2\left ( \sum_{p=1}^m a_p\right ) \left (\sum_{p=m+1}^n a_p\right )+\left (\sum_{p=m+1}^n a_p\right )^2\]
\[\Rightarrow (n-1) \left ( \sum_{p=1}^{m} a_p^2\right )+(n-1) \left ( \sum_{p=m+1}^{n} a_p^2\right )+ 2\left ( \sum_{p=1}^m a_p\right ) \left (\sum_{p=m+1}^n a_p\right ) \] \[-\left (\sum_{p=m+1}^n a_p\right )^2=\left ( \sum_{p=1}^m a_p\right )^2 \]
As\[(n-1) \left ( \sum_{p=m+1}^{n} a_p^2\right )-\left (\sum_{p=m+1}^{n} a_p\right )^2\] \[\geq (n-m) \left ( \sum_{p=m+1}^{n} a_p^2\right )-\left (\sum_{p=m+1}^{n} a_p\right )^2\geq 0\; \; \; [Cauchy-Schwartz].....(1)\]
Again from cauchy,\[(n-1) \left ( \sum_{p=1}^{m} a_p^2\right )\geq m \left ( \sum_{p=1}^{m} a_p^2\right )\geq \left (\sum_{p=1}^{m} a_p\right )^2....(2)\]
From $(1)$ and $(2)$ we can say \[\Rightarrow (n-1) \left ( \sum_{p=1}^{m} a_p^2\right )+(n-1) \left ( \sum_{p=m+1}^{n} a_p^2\right ) \ge \left ( \sum_{p=1}^m a_p- \sum_{p=m+1}^n a_p\right )^2\]
With equality iff \[\frac {a_1}{1}=\frac{a_2}{1}=...=\frac{a_n}{1}=0\]A contradiction comes which completes the proof.
Last edited by Phlembac Adib Hasan on Sat Feb 04, 2012 7:06 pm, edited 1 time in total.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Post Reply