Putnam/Olympiad problem of the day

[Anonymous No.5863492]

Daily problems at: http://math.harvard.edu/putnam/
To find threads: >>>/sci/putnam

Let <span class="math">a_{1}, a_{2}, \dots, a_{n}[/spoiler] (<span class="math">n > 3[/spoiler]) be real numbers such that
<div class="math">
a_{1} + a_{2} + \cdots + a_{n} \geq n
\qquad {\rm and} \qquad
a_{1}^{2} + a_{2}^{2} +
\cdots + a_{n}^{2} \geq n^{2}.
</div>Prove that <span class="math">\max(a_{1}, a_{2}, \dots, a_{n}) \geq 2[/spoiler].

[Anonymous No.5863650]

first if n>3 then we have <span class="math">n^2 \geq 4n[/spoiler].

Now suppose that <span class="math">\text{max}(a_1,\ldots,a_n)<2[/spoiler] then there exist an <span class="math">\varepsilon > 0[/spoiler] such that <span class="math">a_1^2+\ldots+a_n^2 \leq 4n-\varepsilon [/spoiler] and so <span class="math">a_1^2+\ldots+a_n^2 < 4n \leq n^2[/spoiler].

that was way too easy, what am i doing wrong ?

[Anonymous No.5863656]

>>5863650
erf ... "\text{}" is a unknown sequence ? ._.

" now suppose that max<span class="math">(a_1,\ldots,a_n) <2[/spoiler] "

[Anonymous No.5863662]

>>5863650
I think you're assuming the numbers are positive, which isnt given. If you have all a's equal to -3, then their max is <2, but <span class="math"> a_1^2+\ldots+a_n^2 = 9n^2 [/spoiler]

[Anonymous No.5863665]

>>5863662
I just realised this is a dumb example, since it doesnt satisfy <span class="math"> a_1 + a_2 + \ldots + a_n \geq n [/spoiler], but I hope you get the idea

[Anonymous No.5863668]

>>5863662
yup, i was assuming that, thanks anon !

[Anonymous No.5863746]

>>5863492
Second inequality defines the outside of the sphere of radius n, hence <span class="math">\max(|a_i|)\geq [/spoiler]. Now suppose that <span class="math">\max(a_i)<2[/spoiler], this means that there is k such that <span class="math">a_k\leq-n[/spoiler] (using n>3). Rewrite the 1st inequality
<div class="math"> z_1 + ... + z_n \geq 0</div>
where <span class="math">z_j = a_j - 1[/spoiler]. We know that all j <span class="math">z_j < 1[/spoiler] and that <span class="math">z_k\leq-n-1[/spoiler]. Now,
<div class="math">\sum_{j\neq k}z_j < (n-1)</div>.
Adding <span class="math"> z_k[/spoiler] we get <span class="math">z_1 + ... + z_n < 0[/spoiler] which is a contradiction.

How wrong am I?

[Anonymous No.5863752]

>>5863746
<span class="math">\max(|a_i|) \geq n[/spoiler]

[Anonymous No.5863767]

>>5863746
>>5863752
disregard that, I'm moron

[Anonymous No.5863772]

Whats this kind of math called? Why are there dots? Do I have to make a T chart?

[prep !!bRma1Ao62vX No.5863795]

let <span class="math">x \in \mathbb{R}^n[/spoiler], <span class="math">x=(a_1,...,a_n)^T[/spoiler].

In <span class="math">mathbb{R}^n[/spoiler], all norms are equivalent, and in particular:
<span class="math">||x||_{\infty} \leq ||x||_2 \leq \sqrt{n} ||x||_{\infty}[/spoiler].
Here, <span class="math">(||x||_2)^2 = \sum_{k=1}^{n} (a_k)^2 \geq n^2 [/spoiler], so <span class="math">max(|a_1|,...,|a_n|)=||x||_{\infty} \geq \sqrt{n} \geq 2 [/spoiler].

Now I assume we can remove the absolute values by using <span class="math">||x||_1[/spoiler] somehow?

[Anonymous No.5864308]

bump

[Anonymous No.5864311]

>>5863772
>algebra
>ellipses
>no

[Anonymous No.5864322]

>>5863492
it's driving me crazy, that should be pretty simple but my brain doesn't want to work tonight and i get nothing ...

[Anonymous No.5864334]

>>5863492
mfw I don't even know how to read this...Fuck

[Anonymous No.5864366]

>>5864334
To be fair, it is super condensed notation wise. I took me a minute to realize what they were asking. Just don't over think it.

[Anonymous No.5864390]

Pretty obvious. The first equation requires the max to be positive, and restricting all the a's to positive values will determine the smallest maximum satisfying that. Then from the second one for <span class="math">n>3, n^{2}>=4n=2^{2}+2^{2}+...+2^{2} (n-times)[/spoiler].. so basically the first post in this thread

[Anonymous No.5864393]

The first equation requires the max to be positive. Then restricting all of the a's to positive numbers will determine the smallest maximum satisfying that. From the second equation, for <span class="math">n>3, n^{2}>=4n=2^{2}n[/spoiler]. So the minimum max is +2

[Anonymous No.5864395]

>>5864390

Whoops thought that got deleted

[Anonymous No.5864432]

>>5864393
>Then restricting all of the a's to positive numbers will determine the smallest maximum satisfying that.
You would need to explicitly show that for every list of a's satisfying the inequalities, there is a list of positive a's satisfying the inequalities with a lesser or equal maximum.

[Anonymous No.5864440]

>>5864393
And if you just mean
>restricting all of the a's to positive numbers will determine the smallest maximum satisfying <span class="math">a_{1} + a_{2} + \cdots + a_{n} \geq n[/spoiler]
then that is true, but the smallest maximum satisfying that is 1. And that doesn't help you. You haven't ruled out solutions with some of the a's negative where the maximum is greater than 1 but less than 2.

[Anonymous No.5864468]

>>5863492
I understood the idea but I have no idea have to solve it.

if max = 2 then all the numbers in the series have to be 2 for n=4, the lowest case.

then

2^n = n^2

if max is lower than 2 then

series(n=4) < n^2

and the whole thing breaks.

for n>=5 max SHOULD be bigger than 2 so thats why I didn't even mention it.

I can't into maths please comment on my pleb reasoning.

[Anonymous No.5864487]

>>5863492
Let a1, a2, ..., an be in descending order. I will call s the sum of all a and S the sum of all a^2. We can keep s constant and increase S by increasing an ak (1<=k<n) by some amount h and decrease an by the same amount (without changing the order of the a), since (b+h)^2+(c-h)^2=b^2+c^2+2(b-c)h+h^2>b^2+c^2 whenever b>c.
Let us start with s=n and keep all a below 2. As we repeat the above a shift to keep s at n, ak (1<=k<n) approach 2 from below, while an approaches -n+2. As all absolute values of the a increase, S approaches its supremum 2^2*(n-1)+(-n+2)^2=4n-4+n^2-4n+4=n^2, but never reaches it. S cannot reach another optimum by other means, since if there was one we could apply the above a shift to get a better one. Since for all a being smaller than 2 and s equaling n (for larger s, S would only shrink), S cannot reach n^2, s>=n and S>=n^2 implies an a being at least 2, qed.

[Anonymous No.5864500]

>>5864487
PS: A larger s would increase S iff -n+2 has a smaller absolute value than 2 (Increase s enough for an to approach 2), which is equivalent to n being no bigger than 3.

[Anonymous No.5864511]

>>5864440
Ah. I see. So I suppose that the maximum we're looking for is somewhere in the interval (1,2]. If I let <span class="math">|a_i|\in(1,2][/spoiler] then for that second equation I get the condition that <span class="math">\sum |a_i|^2 = (1+a)^2+(1+b)^2+... = n+(a^2+b^2+...)+2(a+b+...) \ge n^2 \ge 4n \Rightarrow a^2+b^2+...+2(a+b+...) \ge 3n[/spoiler]. I dont know if this is really helping me, but it seems like the n positive constants a,b,... should be at least one to satisfy the inequality, making the smallest maximum <span class="math">|a_i|=2[/spoiler] but that might just add confusion.

[Anonymous No.5864560]

>>5864487
This works. If you were submitting the answer in a competition you'd need to spell out explicitly why starting with s > n decreases S, but that part's easy to fill in.

The proof can be made a bit cleaner by eliminating the talk of limits and supremums. Assume the existence of a solution with all <span class="math">a_i < 2[/spoiler] and apply your procedure n-1 times to reach (2, 2, ..., s-2(n-1)). This strictly increases S, but the final S is still no larger than 2. That implies the starting S was less than 2, which contradicts it being a solution.