If $a_{1}$, $a_{2}$, $\ldots$, $a_{n}\geq 0$ are such that \[a_{1}^{2}+\cdots+a_{n}^{2}=1,\] then find the maximum value of the product $(1-a_{1})\cdots (1-a_{n})$.
Problem
Source: Romanian I TST 2007
Tags: inequalities, induction, logarithms, calculus, derivative, inequalities proposed
13.04.2007 16:36
If $n=1$ then it is $0$. Now if $n>1$. I assume that we solved following: If $a_{1},a_{2}\geq 0$ and $a_{1}^{2}+a_{2}^{2}\leq 1$. Find maximum of $(1-a_{1})(1-a_{2})$. I think it is easy and I called value that is $M$. By induction on $n$ we can prove : If $n>1$ and $a_{1},...,a_{n}\geq 0$ such that $a_{1}^{2}+...+a_{n}^{2}\leq 1$ then $(1-a_{1})...(1-a_{n})\leq M$. Answer : $M$ if $n>1$, $0$ if $n=1$. Am I true?
13.04.2007 17:04
Alternatively we can play around with Karamata's and $f(x)=\ln (1-\sqrt{x})$ which is concave on $[0,\frac{1}{4}]$ and convex on $[\frac{1}{4},1)$.
13.04.2007 20:04
i think jensen works better.
14.04.2007 02:54
N.T.TUAN wrote: If $n=1$ then it is $0$. Now if $n>1$. I assume that we solved following: If $a_{1},a_{2}\geq 0$ and $a_{1}^{2}+a_{2}^{2}\leq 1$. Find maximum of $(1-a_{1})(1-a_{2})$. I think it is easy and I called value that is $M$. By induction on $n$ we can prove : If $n>1$ and $a_{1},...,a_{n}\geq 0$ such that $a_{1}^{2}+...+a_{n}^{2}\leq 1$ then $(1-a_{1})...(1-a_{n})\leq M$. Answer : $M$ if $n>1$, $0$ if $n=1$. Am I true? I think you're wrong because the value of $M$ you will get is 1 that holds when you take every $a_{i}=0$. So the sum of the squares satisfy your condition, but clearly $M<1$ so that's not the solution.
15.04.2007 05:27
Megus wrote: Alternatively we can play around with Karamata's and $f(x)=\ln (1-\sqrt{x})$ which is concave on $[0,\frac{1}{4}]$ and convex on $[\frac{1}{4},1)$. Can you show in detail?
15.04.2007 13:01
the final and correct answer is that the maximum realizes for x3=x4=...=xn=0 and x1=x1=sqrt2 /2
15.04.2007 18:30
Just want to ask who is the author of this very nice problem? Is he in this forum?
15.04.2007 18:41
Could someone post a solution?
15.04.2007 18:48
I have one, but it's very, very ugly. It took me six pages in the contest. I think that a solution with Karamata may be more acceptable Lemma. Let $x,y \in [0,1]$ such that $x^{2}+y^{2}= c \in [0,1]$. If $c \in \left[ 0, \frac12 \right]$, then the maximum of $(1-x)(1-y)$ is reached when one of the variables is $0$. Else, the maximum is reached either when $x=y$ or when $xy = 0$. Proof. It's straightforward using Lagrange Multipliers, but I don't think that anyone is too eager to see such a proof. Now, can you complete it, silouan? The method I used in the last part is quite common on Mathlinks.
15.04.2007 19:21
silouan wrote: Could someone post a solution? I will show it for you, silouan. First, we realize that this problem is totally equivalent to the following one (by contradiction method) If $x_{1},x_{2},...,x_{n}\in [0,1]$ such that $x_{1}x_{2}...x_{n}=(1-\frac{1}{\sqrt{2}})^{2}$ then \[f(x_{1},x_{2},...,x_{n}) = (1-x_{1})^{2}+(1-x_{2})^{2}+...+(1-x_{n})^{2}\le 1 (1) \] I choose this renewed form because it it easier to reason. Now, let's start with (1). Denote $k=1-\frac{1}{\sqrt{2}}$. Remark. If $x,y\in [0,1]$ such that $x+y+xy \ge 1$ then \[(1-x)^{2}+(1-y)^{2}\le (1-xy)^{2}. \] Indeed, just notice that \[(1-x)^{2}+(1-y)^{2}-(1-xy)^{2}=(x+y-1)^{2}-x^{2}y^{2}\] \[=(x-1)(y-1)(x+y+xy-1) \le 0. \] Returning to the initial inequality. Just notice that if $x_{1}\le x_{2}\le ...\le x_{n}$ then $x_{1}x_{2}x_{3}\ge k^{2}$ so $x_{2}x_{3}\ge k^{4/3}$, so \[x_{2}+x_{3}+x_{2}+x_{3}\ge 2k^{2/3}+k^{4/3}= 1.07 \ge 1 \] (oh... it is so approximating, greatly luck). According to the remake, we refer \[f(x_{1},x_{2},...,x_{n}) \le f(x_{1},x_{2}x_{3},1,x_{4},...,x_{n}) \le f(x_{1},x_{2}x_{3}x_{4},1,1,x_{5},...,x_{n}) \le ... \le f(x_{1},x_{2}x_{3}...x_{n},1,1,...,1), \] By this step, the problem returns to initial case $n=2$ (just for $2$ numbers). We have done. Remark. It is such a very nice inequality, I must add it to my book, thank its author
15.04.2007 20:08
hungkhtn wrote: silouan wrote: Could someone post a solution? I will show it for you, silouan. First, we realize that this problem is totally equivalent to the following one (by contradiction method) If $x_{1},x_{2},...,x_{n}\in [0,1]$ such that $x_{1}x_{2}...x_{n}=(1-\frac{1}{\sqrt{2}})^{2}$ then \[f(x_{1},x_{2},...,x_{n}) = (1-x_{1})^{2}+(1-x_{2})^{2}+...+(1-x_{n})^{2}\le 1 (1) \] I choose this renewed form because it it easier to reason. Now, let's start with (1). Denote $k=1-\frac{1}{\sqrt{2}}$. Remark. If $x,y\in [0,1]$ such that $x+y+xy \ge 1$ then \[(1-x)^{2}+(1-y)^{2}\le (1-xy)^{2}. \] Indeed, just notice that \[(1-x)^{2}+(1-y)^{2}-(1-xy)^{2}=(x+y-1)^{2}-x^{2}y^{2}\] \[=(x-1)(y-1)(x+y+xy-1) \le 0. \] Returning to the initial inequality. Just notice that if $x_{1}\le x_{2}\le ...\le x_{n}$ then $x_{1}x_{2}x_{3}\ge k^{2}$ so $x_{2}x_{3}\ge k^{4/3}$, so \[x_{2}+x_{3}+x_{2}+x_{3}\ge 2k^{2/3}+k^{4/3}= 1.07 \ge 1 \] (oh... it is so approximating, greatly luck). According to the remake, we refer \[f(x_{1},x_{2},...,x_{n}) \le f(x_{1},x_{2}x_{3},1,x_{4},...,x_{n}) \le f(x_{1},x_{2}x_{3}x_{4},1,1,x_{5},...,x_{n}) \le ... \le f(x_{1},x_{2}x_{3}...x_{n},1,1,...,1), \] By this step, the problem returns to initial case $n=2$ (just for $2$ numbers). We have done. Remark. It is such a very nice inequality, I must add it to my book, thank its author Very nice ! And very special , too ! My solution : $n=2$ we need to find the maximum of : $g(x,y)=(1-\frac{x}{\sqrt{x^{2}+y^{2}}})(1-\frac{y}{\sqrt{x^{2}+y^{2}}})$ $\forall x,y \in [0,+\infty)$ Put $y=1$ we have $g'(x,1)=\frac{(x-1)(x^{2}+1)^{2}-(x-1)(x+1)(x^{2}+1)^{\frac{3}{2}}}{(x^{2}+1)^{\frac{7}{2}}}$ Easy to show that $max g(x,1)=(1-\frac{1}{\sqrt{2}})^{2}$ with the equality if $x=1$ or $max g(x,y)=(1-\frac{1}{\sqrt{2}})^{2}$ with the equality if $x=y$ If $n\geq\3$ put $f(x_{1},x_{2},.....,x_{n})=(1-x_{1})(1-x_{2})..(1-x_{n})$ Notice that $x_{i}\geq\ 0 \leftrightarrow 1-x_{i}\leq\ 1$ we have : $f(x_{1},x_{2},.....,x_{n}) \leq\ f(x_{1},x_{2},.....,0) \leq\ .... \leq\ f(x_{1},x_{2},0,0,.......,0)$ We return to $n=2$ which is easy !
15.04.2007 20:30
Thank you, Your way is short, too, Tan. I never believe that you are only at 11th grade.
15.04.2007 23:24
tanpham90 wrote: Notice that $x_{i}\geq\ 0 \leftrightarrow 1-x_{i}\leq\ 1$ we have : $f(x_{1},x_{2},.....,x_{n}) \leq\ f(x_{1},x_{2},.....,0) \leq\ .... \leq\ f(x_{1},x_{2},0,0,.......,0)$ We return to $n=2$ which is easy ! I think you are wrong because $x_{1}^{2}+x_{2}^{2}\le 1$ and the inequality $f(x_{1},x_{2},0,0,.......,0) \le (1-\frac 1{\sqrt{2}})^{2}$ doesn't hold (see $x_{1}=x_{2}=0$). We can prove easier the inequality by contradiction. Assume that $F=(1-\sqrt{x_{1}})(1-\sqrt{x_{2}})...(1-\sqrt{x_{n}})$ attainds its maximum at $(x_{1},x_{2},...,x_{n})$ with $x_{1}\ge x_{2}\ge x_{3}\ge ... \ge x_{n}$ and $x_{3}>0$. Then, we show that $F(x_{1},x_{2},x_{3},x_{4},...,x_{n}) < F(x_{1},0,x_{2}+x_{3},x_{4},...,x_{n})$, which is a contradiction. Thus, it follows that $F$ is maximal for $x_{3}=...=x_{n}=0$. The inequality above $F(x_{1},x_{2},x_{3},x_{4},...,x_{n}) < F(x_{1},0,x_{2}+x_{3},x_{4},...,x_{n})$ is true because $x_{2}+x_{3}\le \frac{2}{3}$.
16.04.2007 06:17
It is not elememtary, VASC (why you affirm that the maximum exists at $(x_{1},x_{2},...,x_{n})$). However, it is very natural and short.
16.04.2007 06:42
Vasc wrote: I think you are wrong because $x_{1}^{2}+x_{2}^{2}\le 1$ and the inequality $f(x_{1},x_{2},0,0,.......,0) \le (1-\frac 1{\sqrt{2}})^{2}$ doesn't hold (see $x_{1}=x_{2}=0$). You are right , Vasc ! But in my solution , I think $f(x_{1},x_{2},0,0,0,.....,0)$ with $x_{i}$ satisfy $\sum x_{i}^{2}=1$ mean $x_{3}=x_{4}=.....=x_{n}=0$ ( so that we have $x_{1}^{2}+x_{2}^{2}=1$ ) and we can reutrn to case $n=2$ ! Am I wrong ?
16.04.2007 09:38
tanpham90 wrote: I think $f(x_{1},x_{2},0,0,0,.....,0)$ with $x_{i}$ satisfy $\sum x_{i}^{2}=1$ mean $x_{3}=x_{4}=.....=x_{n}=0$ ( so that we have $x_{1}^{2}+x_{2}^{2}=1$ ) and we can reutrn to case $n=2$ ! Am I wrong ? Yes. You are wrong, because in $f(x_{1},x_{2},.....,x_{n}) \leq\ f(x_{1},x_{2},.....,0) \leq\ .... \leq\ f(x_{1},x_{2},0,0,.......,0)$ you don't mean $x_{3}=x_{4}=.....=x_{n}=0$.
16.04.2007 18:37
hungkhtn wrote: Remark. If $x,y\in [0,1]$ such that $x+y+xy \ge 1$ then \[(1-x)^{2}+(1-y)^{2}\le (1-xy)^{2}. \] Indeed, just notice that \[(1-x)^{2}+(1-y)^{2}-(1-xy)^{2}=(x+y-1)^{2}-x^{2}y^{2}\] $=(x-1)(y-1)(x+y+xy-1) \le 0.$ Shouldn't the last sign be $\geq$?
16.04.2007 18:53
maggot wrote: hungkhtn wrote: Remark. If $x,y\in [0,1]$ such that $x+y+xy \ge 1$ then \[(1-x)^{2}+(1-y)^{2}\le (1-xy)^{2}. \] Indeed, just notice that \[(1-x)^{2}+(1-y)^{2}-(1-xy)^{2}=(x+y-1)^{2}-x^{2}y^{2}\] $=(x-1)(y-1)(x+y+xy-1) \le 0.$ Shouldn't the last sign be $\geq$? I am sorry. It is a typo only. It should be \[(1-x)^{2}+(1-y)^{2}-(1-xy)^{2}=(x+y-1)^{2}-x^{2}y^{2}\] $=-(x-1)(y-1)(x+y+xy-1) \le 0.$
17.04.2007 06:27
hungkhtn wrote: \] Just notice that if $x_{1}\le x_{2}\le ...\le x_{n}$ then $x_{1}x_{2}x_{3}\ge k^{2}$ so $x_{2}x_{3}\ge k^{4/3}$, so \[ Why is this?
17.04.2007 06:57
Because $x_{1}\le x_{2}\le...\le x_{n}\le 1$, so \[x_{1}x_{2}x_{3}\ge k^{2}.\] Because $x_{1}\le x_{2}\le x_{3}$ so \[x_{2}x_{3}\ge k^{4/3}\] Is this clear now?
17.04.2007 09:54
All right. I see. But it is not very convenient to prove in the exam that $2k^{2/3}+k^{4/3}\geq 1$!
17.04.2007 10:04
I understand. But it is not hard to check. Let see other solutions when you must count the derivative, so complicated! The fact that $2k^{2/3}+k^{4/3}~1.07~1$ also shows that this problem is very nice and sharp.
17.04.2007 16:13
Hmm... actually how can it be proved?
17.04.2007 16:24
radio wrote: Hmm... actually how can it be proved? .. I think this is not a hard and interesting question. Calculating in inequalities is indispensable, and by a calculator, you can check it easily (I am not sure if Romania Exam allows calculator). However, if you still ask for this question, I will answer \[2k^{2/3}+k^{4/3}\ge 1 \Leftrightarrow k^{2/3}\ge \sqrt{2}-1\] \[\Leftrightarrow (\sqrt{2}-1)^{2}\ge \sqrt{2}(\sqrt{2}-1)^{3}\Leftrightarrow 1 \ge \sqrt{2}(\sqrt{2}-1) \Leftrightarrow \sqrt{2}\ge 1\] It is obvious. But it is boring,
18.04.2007 04:04
hungkhtn wrote: It is not elememtary, VASC (why you affirm that the maximum exists at $(x_{1},x_{2},...,x_{n})$). However, it is very natural and short. By induction, we can make elementary the solution above. Let $F_{k}(x_{1},x_{2},...,x_{k})=(1-\sqrt{x_{1}})(1-\sqrt{x_{2}})...(1-\sqrt{x_{k}})$ with $x_{1}+x_{2}+...+x_{k}=1$. For $k=2$, we have $F_{2}(x_{1},x_{2}) \le (1-\frac 1{\sqrt 2})^{2}$. For $k=n$, $n \ge 3$, assume that $x_{1}\ge x_{2}\ge ... \ge x_{n}$. We have $F_{n}(x_{1},x_{2},...,x_{n-1},x_{n}) \le F_{n}(x_{1},x_{2},...,x_{n-1}+x_{n},0)$ since $x_{n-1}+x_{n}\le \frac 2{n}(x_{1}+x_{2}+...+x_{n})=\frac 2{n}\le \frac 2{3}$. But $F_{n}(x_{1},x_{2},...,x_{n-1}+x_{n},0)=F_{n-1}(x_{1},x_{2},...,x_{n-2},x_{n-1}+x_{n})\le (1-\frac 1{\sqrt 2})^{2}$ by induction hypothesis.
29.05.2007 00:01
hungkhtn wrote: silouan wrote: Could someone post a solution? I will show it for you, silouan. First, we realize that this problem is totally equivalent to the following one (by contradiction method) If $x_{1},x_{2},...,x_{n}\in [0,1]$ such that $x_{1}x_{2}...x_{n}=(1-\frac{1}{\sqrt{2}})^{2}$ then \[f(x_{1},x_{2},...,x_{n}) = (1-x_{1})^{2}+(1-x_{2})^{2}+...+(1-x_{n})^{2}\le 1 (1) \] I choose this renewed form because it it easier to reason. Now, let's start with (1). Denote $k=1-\frac{1}{\sqrt{2}}$. Remark. If $x,y\in [0,1]$ such that $x+y+xy \ge 1$ then \[(1-x)^{2}+(1-y)^{2}\le (1-xy)^{2}. \] Indeed, just notice that \[(1-x)^{2}+(1-y)^{2}-(1-xy)^{2}=(x+y-1)^{2}-x^{2}y^{2}\] \[=(x-1)(y-1)(x+y+xy-1) \le 0. \] Returning to the initial inequality. Just notice that if $x_{1}\le x_{2}\le ...\le x_{n}$ then $x_{1}x_{2}x_{3}\ge k^{2}$ so $x_{2}x_{3}\ge k^{4/3}$, so \[x_{2}+x_{3}+x_{2}+x_{3}\ge 2k^{2/3}+k^{4/3}= 1.07 \ge 1 \] (oh... it is so approximating, greatly luck). According to the remake, we refer \[f(x_{1},x_{2},...,x_{n}) \le f(x_{1},x_{2}x_{3},1,x_{4},...,x_{n}) \le f(x_{1},x_{2}x_{3}x_{4},1,1,x_{5},...,x_{n}) \le ... \le f(x_{1},x_{2}x_{3}...x_{n},1,1,...,1), \] By this step, the problem returns to initial case $n=2$ (just for $2$ numbers). We have done. Remark. It is such a very nice inequality, I must add it to my book, thank its author can someone clarify why is this an equivalent problem, please?
20.06.2007 15:02
We have: a[1]^2+a[2]^2+a[3]^2+...a[n]^2 = 1, so all a <= 1 for all i <= n. Let f(a[1],a[2],a[3],...,a[n])=(1-a[1])*(1-a[2])*(1-a[3])*...*(1-a[n])+p*(a[1]^2+a[2]^2+a[3]^2+...a[n]^2 - 1), where p - real. 1) diff(f(a[1],a[2],...,a[n]), a[1]) = -(1-a[2])(1-a[3])...(1-a[n])+2*p*a[1] = 0 2) diff(f(a[1],a[2],...,a[n]), a[2]) = -(1-a[1])(1-a[3])...(1-a[n])+2*p*a[2] = 0 ... ... n) diff(f(a[1],a[2],...,a[n]), a[n]) = -(1-a[2])(1-a[3])...(1-a[n-1])+2*p*a[n] = 0 sub 2) and 1) : 2*p*(a[2] - a[1]) + (-1 + a[1] + 1 - a[2])*(1-a[3])*...*(1-a[n]) = 0 or (a[2] - a[1])*(2*p - (1-a[3])*...*(1-a[n])) = 0; we have a[1] = a[2] or 2*p = (1-a[3])*...*(1-a[n]) **)if(a[1] == a[2]) then continue for all ecuations : 3)-2) -> we have a[2] = a[3] or 2*p = (1-a[1])*(1-a[4])*....*(1-a[n]) ..... so we have all a[1] == a[2] == a[3] == ... ==a[n] or a[k] = 1 and all a =0 {i != k} if a[1]=a[2]=....a[n] so a = 1 / sqrt(n) and f = (1 - 1 / sqrt(n))^n in other case (a[k] = 1) we have f = 0; Answer: f{max} = (1 - 1 / sqrt(n))^n
21.06.2007 14:15
Yuriy Solovyov wrote: We have: a[1]^2+a[2]^2+a[3]^2+...a[n]^2 = 1, so all a <= 1 for all i <= n. Let f(a[1],a[2],a[3],...,a[n])=(1-a[1])*(1-a[2])*(1-a[3])*...*(1-a[n])+p*(a[1]^2+a[2]^2+a[3]^2+...a[n]^2 - 1), where p - real. 1) diff(f(a[1],a[2],...,a[n]), a[1]) = -(1-a[2])(1-a[3])...(1-a[n])+2*p*a[1] = 0 2) diff(f(a[1],a[2],...,a[n]), a[2]) = -(1-a[1])(1-a[3])...(1-a[n])+2*p*a[2] = 0 ... ... n) diff(f(a[1],a[2],...,a[n]), a[n]) = -(1-a[2])(1-a[3])...(1-a[n-1])+2*p*a[n] = 0 sub 2) and 1) : 2*p*(a[2] - a[1]) + (-1 + a[1] + 1 - a[2])*(1-a[3])*...*(1-a[n]) = 0 or (a[2] - a[1])*(2*p - (1-a[3])*...*(1-a[n])) = 0; we have a[1] = a[2] or 2*p = (1-a[3])*...*(1-a[n]) **)if(a[1] == a[2]) then continue for all ecuations : 3)-2) -> we have a[2] = a[3] or 2*p = (1-a[1])*(1-a[4])*....*(1-a[n]) ..... so we have all a[1] == a[2] == a[3] == ... ==a[n] or a[k] = 1 and all a =0 {i != k} if a[1]=a[2]=....a[n] so a = 1 / sqrt(n) and f = (1 - 1 / sqrt(n))^n in other case (a[k] = 1) we have f = 0; Answer: f{max} = (1 - 1 / sqrt(n))^n Is it me or did you just contradict all of the above solutions plus the official answer? (My interptretation of the problem was something using $R^{n}$ which if I remember got me $1$ big point)
30.12.2007 08:59
It is because he applied lagrange multipliers incorrectly. Since $ x_i\ge 0$, we have to check the border of that inequality, or when $ x_i=0$, etc. This gives the correct answer. I also believe that he solved the system incorrectly. I got that the max occurs when M variables are a, N variables are (1-a) and P variables are 0 where M+N+P=n