limit
real analysis
integration
probability
function
probability and stats

Let $ (X_n: n\in\mathbb{N})$ sequence of independent equally distributed random variables such that $ \mathbb{E}[X_1]\equal{}0$. Prove that $ \lim_{n\rightarrow \infty}\frac{1}{n}\mathbb{E}[|X_1\plus{}\dots\plus{}X_n|]\equal{}0$.

This would be easy if each $ X_i$ had finite variance $ \sigma^2.$ If that were the case,

$ \mathbb{E}\left(\sum X_i\right)^2=n\sigma^2,$ and by Cauchy-Schwarz,

$ \mathbb{E}\left(\left|\sum X_i\right|\right)\le \left(\mathbb{E}\left(\sum X_i\right)^2\right)^{\frac12}=\sqrt{n}\,\sigma.$

But you didn't say anything about finite variance, so we'll have to find another proof.

what you are trying to prove is the "modified" law of large number where the almost sure convergence is replaced by the $ L^1$ convergence.
For $ \epsilon > 0$, take $ a$ large enough such that:
$ |E[ X 1_{|X|<a} ]| \leq \epsilon$ and such that $ |E[ X1_{|X| \geq a} ]| \leq \epsilon$
Then you can apply the strong law of the large number to $ X^{(a)}=X 1_{|X|<a}$ to get that $ \frac{1}{n} \sum_1^n X^{a}_n$ converges almost surely towards $ -\epsilon \leq \mu_a = E[ X 1_{|X|<a} ] \leq \epsilon$. But this convergence is also in $ L^1$ since all the random variables $ \frac{1}{n} \sum_1^n X^{a}_n$ are bounded by $ a$. The difference between $ E[ \frac{1}{n} \sum_1^n X^{a}_n ]$ and $ E[ \frac{1}{n} \sum_1^n X_n ]$ is bounded by $ |E[ X 1_{|X| \geq a} ]| \leq \epsilon$, which gives the conclusion.

Well, this is just the $ L_1$-law of large numbers, which can be deduced from the SLLN by using truncation. Another approach is to use the fact that
\[ \frac {S_n}{n} \equal{} E(X_1|X_1,\dots,X_n),
\]
so it's uniformly integrable.

[quote="Yustas"]\[ \frac {S_n}{n} \equal{} E(X_1|X_1,\dots,X_n),
\][/quote]

Can you please prove this?

Can you tell me the following argument is correct?

By definition $ \int_AE(X|X\plus{}Y) dP\equal{}\int_AX dP$ for all $ A\in \sigma(X\plus{}Y)$ and
                     $ \int_AE(Y|X\plus{}Y) dP\equal{}\int_AY dP$ for all $ A\in \sigma(X\plus{}Y)$
 Since $ \sigma(X\plus{}Y)\subseteq \sigma(X,Y)$ and since $ X$ and $ Y$ are iid, $ \int_AX dP\equal{}\int_AY dP$ for all $ A\in \sigma(X\plus{}Y)$
 and hence $ \int_AE(X|X\plus{}Y) dP\equal{}\int_AE(Y|X\plus{}Y) dP$ for all $ A\in \sigma(X\plus{}Y)$

Hence $ E(X|X\plus{}Y)\equal{}E(Y|X\plus{}Y)\equal{}\frac{X\plus{}Y}{2}$

[quote="siiz"][quote="Yustas"]
\[ \frac {S_n}{n} \equal{} E(X_1|X_1,\dots,X_n),
\]
[/quote]

I think the correct statement is
\[ \frac {S_n}{n} \equal{} E(X_1|X_1 \plus{} \dots \plus{} X_n),
\]
to limsup: You had better practice your skill of calculating conditional expectation by proving above result with $ n \equal{} 2$ and so on.[/quote]
 yes, because  $ E(X_1|X_1,\dots,X_n) \equal{} X_1$  :D
and also:
$ E(X_1|X_1 \plus{} \dots \plus{} X_n)\equal{}E(X_2|X_1 \plus{} \dots \plus{} X_n)\equal{} \ldots\equal{}E(X_n|X_1 \plus{} \dots \plus{} X_n)$
so
$ E(X_1|X_1 \plus{} \dots \plus{} X_n)\equal{}\frac{E(X_1|X_1 \plus{} \dots \plus{} X_n)\plus{} \ldots\plus{}E(X_n|X_1 \plus{} \dots \plus{} X_n)}{n}$
and of course:
$ \frac{E(X_1 \plus{} \dots \plus{} X_n|X_1 \plus{} \dots \plus{} X_n)}{n} \equal{} \frac{S_n}{n}$

[quote="alekk"]
and also:
$ E(X_1|X_1 \plus{} \dots \plus{} X_n) \equal{} E(X_2|X_1 \plus{} \dots \plus{} X_n) \equal{} \ldots \equal{} E(X_n|X_1 \plus{} \dots \plus{} X_n)$
[/quote]
This is exactly what limsup wants to prove.
to alekk, please let him have time to do it by himself.

[quote="siiz"][quote="limsup"]... $ \int_AE(X|X \plus{} Y) dP \equal{} \int_AE(Y|X \plus{} Y) dP$ for all $ A\in \sigma(X \plus{} Y)$

Hence $ E(X|X \plus{} Y) \equal{} E(Y|X \plus{} Y) \equal{} \frac {X \plus{} Y}{2}$[/quote]
I am afraid that you are wrong. Let's try harder.[/quote]

I don't know what's wrong in this.
$ E(X|X \plus{} Y)$ and $ E(Y|X \plus{} Y)$ are both $ \sigma(X \plus{} Y)$ measurable and $ \int_AE(X|X \plus{} Y) dP \equal{} \int_AE(Y|X \plus{} Y) dP$ for all $ A\in \sigma(X \plus{} Y)$.
Therefore  $ E(X|X \plus{} Y) \equal{} E(Y|X \plus{} Y)$
Hence $ 2E(X|X \plus{} Y) \equal{}E(X\plus{}Y|X \plus{} Y) \equal{}X \plus{} Y$
Thus $ E(X|X \plus{} Y) \equal{} E(Y|X \plus{} Y)\equal{}\frac {X \plus{} Y}{2}$

Ok, I will explain. Let $ X$ and $ Y$ be two integrable random variables defined on the probability space $ (\Omega, \mathcal{F},P)$. Then $ \int_A X dP \equal{} \int_A Y dP$ for all $ A \in \mathcal{F}$  iff $ X$ and $ Y$ have the same distribution. Actuary, I have seen that you had used this argument at the first part of your proof.

Hint: do you know something like $ E(X|Y\equal{}y)$, and the following formula
\[ EX \equal{} \int_R E(X|Y\equal{}y)dF_Y(y).\]

[quote="siiz"]Let $ X$ and $ Y$ be two integrable random variables defined on the probability space $ (\Omega, \mathcal{F},P)$. Then $ \int_A X dP \equal{} \int_A Y dP$ for all $ A \in \mathcal{F}$  iff $ X$ and $ Y$ have the same distribution. [/quote]

I don't think that this is true.
See the following example.

Experiment: Tossing a coin.
Define $ X\equal{}1$, if head appears, $ 0$ if tail appears each with prob. $ 1/2$.
Define $ Y\equal{}0$, if head appears, $ 1$ if tail appears each with prob $ 1/2$.
Then $ X$ and $ Y$ have the same distribution.
But if $ A\equal{}${head} then $ E(X.1_A)\neq E(Y.1_A)$
Sorry if I am mistaken!

yep, you are right. Nice counterexample.
 :blush:

I think that siiz meant: If for all $ A \in \mathcal F$, the following is true:
\[ P[X \in A] \equal{} P[ Y \in A]\]
then $ X,Y$ have the same distribution. (this is alsmost the definition of equality in distribution isn't it  :lol: )or equivalently, and often more practical:
Take $ X: \Omega_X \to \mathbb{R}^n$, $ Y: \Omega_Y \to \mathbb{R}^n$ and suppose that for any test function $ f$ (compactly supported, smooth) the following holds:
\[ E[f(X)]\equal{}E[f(Y)]\]
then $ X,Y$ have the same distribution.

Or even more: Take $ X: \Omega_X \to \mathbb{R}^n$, $ Y: \Omega_Y \to \mathbb{R}^n$ and suppose that for any $ \xi \in \mathbb{R}^n$ the following holds:
\[ E[\exp(i \xi.X)]\equal{}E[\exp(i \xi.Y)]\]
then $ X,Y$ have the same distribution. (see: Fourier Transform)

Can someone please prove this: When $ X$ and $ Y$ are iid, $ E(X|X \plus{} Y) \equal{} E(Y|X \plus{} Y)$?  Its breaking my head...please...

ok, alekk. you are such a generous man :roll:
Here is my proof: Let denote by $ F(x)$ the distribution function of $ X$ (and of $ Y$ as well). For each $ a \in R$, we have
\[ E(X, X\plus{}Y < a) \equal{} \int_R E(X, X\plus{}Y <a|X\equal{}x)dF(x)\equal{}\int_R xF(a\minus{}x)dF(x)\]
hence \[ E(X, X\plus{}Y < a)\equal{}E(Y,X\plus{}Y<a)\equal{}0.5E(X\plus{}Y,X\plus{}Y<a) \quad \forall a \in R.\]
It maybe good if someone could kindly show us more elementary proof.


A polynomial of degree n has all coefficients equal to  :pm:1. If all its roots are real, prove n<=3.

Very surprising result

[hide]Since we can change P to -P let's suppose

P(x) = xn - s1 xn-1 + s2 xn-1 + ...... + (-1)n sn

With

s1 =  :Sigma: ai

s2 =  :Sigma: ai aj

sn = prod ai

if ai are the roots.

Then :Sigma: ai = s1 - 2s2 = 1 - 2s2

All the roots are real so :Sigma: ai >= 0 and so s2 = -1  and :Sigma: ai = 3 !

Let bi = ai

We have :Sigma: bi = 3, prod bi = 1.

AM-GM : :Sigma: bi / n >= prod bi or n <= 3  :mrgreen:

x-1, x-x-1, x3+x-x-1 are examples of such polynoms for n <= 3.[/hide]

Thats exactly the same solution I had!

I kept wanting to use AM-GM but couldn't because of negatives.. then I thought of using the squares, and then that was it.. quite nice.


Okay, Here's my query, and it is -- It's late at night, you're walking in a street (There are very few people on the street), it's raining pretty heavily (a heavy downpour), you can hear loud thunderstorms and see intermittent glimpses of lighting. Now, In the prevailing circumstances, what's the probability of you getting struck by lightning (or a lightning bolt)?

Assume you forgot to carry an umbrella with you -- The downpour was not expected at all -- sort of impromptu.

Consider another case (case no 2) in which you're walking on a road on the outskirts of the city (which is almost completely devoid of people,trees, buildings,etc). Does the probability of you getting hit by lightning increase here when compared with first case?

Now, it does appear obvious intuitively (in general) that the probability of getting struck by lightning is very low. (In the presence of buildings, people, trees, etc), but, I would also like to know whether the probability of getting hit by lightning increase in the absence of the aforementioned things (trees,etc)?

But I'm slightly more interested in seeking a scientific, or a coherent/logical explanation rather than an intuitive one. (Both are welcomed)

Thank you!

The National Safety Council estimates that 70 to 120 people per year are killed by lightning strikes.  Say 100, just to be even.  The US population is 308 million, maybe a little more.  So the probability of being killed by a lightning strike is roughly $ 3.25\times 10^{\minus{}7}$, pretty small.

Now not everyone who is struck by lightning dies of course, so your numerator rises by a little.  But it certainly won't alter the order of magnitude by more than 1.

A month or two ago, a woman was killed by lightning in Southern California - I think it was in San Bernardino. It was extensively covered in the local news, in part because the storm was quite unusual, especially for the time of year. She was in a residential neighborhood with plenty of trees and houses around. Apparently, the lightning bolt hit a tree and then jumped sideways from the tree to hit her.

[quote="worthawholebean"]If I remember correctly, lightning tends to strike higher objects more often, so if you're in a street the lightning will hit a house more often.[/quote]

Yes, you're right.

Assume the following scenario:You're walking in a completely deserted land -- there are no buildings, trees, etc. Now, if there are no "higher" objects -- The probability of the lightning directly striking you will increase-- but does lightning "directly" strike people? (It shouldn't strike people as in the "news article" that [b]Kent Merryfield [/b] had cited)

I'm just asking the probability of getting struck by lightning as in case (1) -- When you're in a busy street, and in case (2) -- When you're in a completely deserted area as aforementioned. Certainly, the probability of getting struck by lightning in the second case will be more as and when compared with the first case.

[quote="Kent Merryfield"]Fontana, rather than San Bernardino (close enough), and it appears she was standing under the tree. Here are two news stories:

[url=http://lethalapp.com/news/2009/06/rare-california-lightning-death/]Link.[/url]
[url=http://www.pe.com/localnews/sbcounty/stories/PE_News_Local_S_wea04.4b9641e.html]Link.[/url][/quote]

Yes, I felt sad :( after reading the article. Maybe it drives home the point:"Death could sometimes occur in the weirdest possible manner."

doesn't lightning go upward, correct me if im wrong
something about massive static electricity


[quote="leviethai"]Let $ a,b,c > 0$

$ \sqrt {\dfrac{{2a}}{{a \plus{} b}}} \plus{} \sqrt {\dfrac{{2b}}{{b \plus{} c}}} \plus{} \sqrt {\dfrac{{2c}}{{c \plus{} a}}} \ge \dfrac{{\left( {a \plus{} b \plus{} c} \right)\left( {ab \plus{} bc \plus{} ca} \right)}}{{\sqrt {\left( {{a^2} \plus{} {b^2} \plus{} {c^2}} \right)\left( {{a^2}{b^2} \plus{} {b^2}{c^2} \plus{} {c^2}{a^2}} \right)} }}$[/quote]

Using Holder's Inequality

$ (\sum \sqrt {\frac {2a}{a \plus{} b}})^2(\sum {4a^2(a \plus{} b)})\geq (2a \plus{} 2b \plus{} 2c)^3$

we have

$ (\sum \sqrt {\frac {2a}{a \plus{} b}})^2\geq \frac {(2a \plus{} 2b \plus{} 2c)^3}{\sum {4a^2(a \plus{} b)}}$

we only prove

$ \frac {(2a \plus{} 2b \plus{} 2 c)^3}{\sum {4a^2(a \plus{} b)}}\geq \frac {(a \plus{} b \plus{} c)^2(ab \plus{} bc \plus{} ca)^2}{(a^2 \plus{} b^2 \plus{} c^2)(a^2b^2 \plus{} b^2 c^2 \plus{} c^2a^2)}$

or

$ \frac {2(a \plus{} b \plus{} c)}{a^2(a \plus{} b) \plus{} b^2(b \plus{} c) \plus{} c^2(c \plus{} a)}\geq \frac {(ab \plus{} bc \plus{} ca)^2}{(a^2 \plus{} b^2 \plus{} c^2)(a^2b^2 \plus{} b^2 c^2 \plus{} c^2a^2)}$

The inequality holds,but i can not prove. :lol:

[quote="leviethai"]Let $ a,b,c > 0$

$ \sqrt {\dfrac{{2a}}{{a \plus{} b}}} \plus{} \sqrt {\dfrac{{2b}}{{b \plus{} c}}} \plus{} \sqrt {\dfrac{{2c}}{{c \plus{} a}}} \ge \dfrac{{\left( {a \plus{} b \plus{} c} \right)\left( {ab \plus{} bc \plus{} ca} \right)}}{{\sqrt {\left( {{a^2} \plus{} {b^2} \plus{} {c^2}} \right)\left( {{a^2}{b^2} \plus{} {b^2}{c^2} \plus{} {c^2}{a^2}} \right)} }}$[/quote]

by Holder, we have

\[ \left( {\sum {\sqrt {\frac {{2a}}{{a \plus{} b}}} } } \right)^2 \sum {a\left( {a \plus{} b} \right)} \sum {a^2 } \ge 2\left( {a \plus{} b \plus{} c} \right)^4 ,\]
we get

\[ \left( {\sum {\sqrt {\frac {{2a}}{{a \plus{} b}}} } } \right)^2 \ge \frac {{2\left( {a \plus{} b \plus{} c} \right)^4 }}{{\sum {a\left( {a \plus{} b} \right)} \sum {a^2 } }},\]
so we just need to prove that

\[ \frac {{2\left( {a \plus{} b \plus{} c} \right)^4 }}{{\sum {a\left( {a \plus{} b} \right)} \sum {a^2 } }} \ge \frac {{\left( {a \plus{} b \plus{} c} \right)^2 \left( {ab \plus{} bc \plus{} ca} \right)^2 }}{{\left( {a^2 \plus{} b^2 \plus{} c^2 } \right)\left( {a^2 b^2 \plus{} b^2 c^2 \plus{} c^2 a^2 } \right)}},\]
or

\[ 2\left( {a \plus{} b \plus{} c} \right)^2 \left( {a^2 b^2 \plus{} b^2 c^2 \plus{} c^2 a^2 } \right) \ge \left( {ab \plus{} bc \plus{} ca} \right)^2 \left( {a^2 \plus{} b^2 \plus{} c^2 \plus{} ab \plus{} bc \plus{} ca} \right),\]
that's easy to prove by Muirhead.

 :D

[quote="hedeng123"][quote="leviethai"]@hedeng123:  I hope you will prove it soon :)
@kuing: I don't like Murihead so much, so can you give me another solution? Thank you  :)
I have 1 proof, using only AM-GM and CAuchy - Schwartz

P/S: my english is not good......[/quote]

$ 2(a \plus{} b \plus{} c)^2(a^2b^2 \plus{} b^2c^2 \plus{} c^2a^2) \minus{} (ab \plus{} ca \plus{} bc)^2(a^2 \plus{} bc \plus{} b^2 \plus{} ca \plus{} c^2 \plus{} ab)\geq 0$

 $ \Longleftrightarrow \sum_{sym} (2a^4b^2 \minus{} 2a^4bc \plus{} 3a^3b^3 \minus{} 2a^3b^2c \minus{} a^2b^2c^2)\geq 0$

or

$ \Longleftrightarrow (a \minus{} b)^2(b \minus{} c)^2(c \minus{} a)^2 \plus{} 5\sum b^2c^2(a \minus{} b)(a \minus{} c) \plus{} 2abc\sum(b \plus{} c)(a \minus{} b)(a \minus{} c)\geq 0$[/quote]
Great, I think this is computer's power  :)
So we have another Inequality. Thank you.
I try to prove this inequality more elementary.

[quote="kuing"][quote="leviethai"]@hedeng123:  I hope you will prove it soon :)
@kuing: I don't like Murihead so much, so can you give me another solution? Thank you  :)
I have 1 proof, using only AM-GM and CAuchy - Schwartz

P/S: my english is not good......[/quote]

then.......how about the $ uvw$ method? use it to prove that ineq is so easy.

do you like it?[/quote]

You can.........

I don't like it because I can't use it  :blush: , I want everything can be solved in elementary solutions  :) .

P/S: I'm Grade 10 Student

My solution  :) ( This is a reason why I said this inequality wasn't hard)

From AM-GM inequality, we have

$ \sqrt {\dfrac{{2a}}{{a \plus{} b}}} \equal{} \dfrac{{2a}}{{\sqrt {2a} .\sqrt {a \plus{} b} }} \ge \dfrac{{4a}}{{3a \plus{} b}}$

$ \sqrt {\dfrac{{2b}}{{b \plus{} c}}} \ge \dfrac{{4b}}{{3b \plus{} c}},\sqrt {\dfrac{{2c}}{{c \plus{} a}}} \ge \dfrac{{4c}}{{3c \plus{} a}}$

So that,

$ \sqrt {\dfrac{{2a}}{{a \plus{} b}}} \plus{} \sqrt {\dfrac{{2b}}{{b \plus{} c}}} \plus{} \sqrt {\dfrac{{2c}}{{c \plus{} a}}} \ge 4\left( {\dfrac{a}{{3a \plus{} b}} \plus{} \dfrac{b}{{3b \plus{} c}} \plus{} \dfrac{c}{{3c \plus{} a}}} \right)$

From Schwartz inequality and the following well-known inequality $ {{a^2} \plus{} {b^2} \plus{} {c^2}} \ge {ab \plus{} bc \plus{} ca}$

$ \dfrac{a}{{3a \plus{} b}} \plus{} \dfrac{b}{{3b \plus{} c}} \plus{} \dfrac{c}{{3c \plus{} a}} \equal{} \dfrac{{{a^2}}}{{3{a^2} \plus{} ab}} \plus{} \dfrac{{{b^2}}}{{3{b^2} \plus{} bc}} \plus{} \dfrac{{{c^2}}}{{3{c^2} \plus{} ca}}$

$ \ge \dfrac{{{{\left( {a \plus{} b \plus{} c} \right)}^2}}}{{3\left( {{a^2} \plus{} {b^2} \plus{} {c^2}} \right) \plus{} ab \plus{} bc \plus{} ca}} \ge \dfrac{{{{\left( {a \plus{} b \plus{} c} \right)}^2}}}{{4\left( {{a^2} \plus{} {b^2} \plus{} {c^2}} \right)}}$

Therefore,

$ \sqrt {\dfrac{{2a}}{{a \plus{} b}}} \plus{} \sqrt {\dfrac{{2b}}{{b \plus{} c}}} \plus{} \sqrt {\dfrac{{2c}}{{c \plus{} a}}} \ge \dfrac{{{{\left( {a \plus{} b \plus{} c} \right)}^2}}}{{{a^2} \plus{} {b^2} \plus{} {c^2}}}$

We also have, (just prove analogously)

$ \sqrt {\dfrac{{2a}}{{a \plus{} b}}} \plus{} \sqrt {\dfrac{{2b}}{{b \plus{} c}}} \plus{} \sqrt {\dfrac{{2c}}{{c \plus{} a}}} \equal{} \sqrt {\dfrac{{2ac}}{{ac \plus{} bc}}} \plus{} \sqrt {\dfrac{{2ba}}{{ba \plus{} ca}}} \plus{} \sqrt {\dfrac{{2cb}}{{cb \plus{} ab}}}$

$ \ge \dfrac{{{{\left( {ab \plus{} bc \plus{} ca} \right)}^2}}}{{{a^2}{b^2} \plus{} {b^2}{c^2} \plus{} {c^2}{a^2}}}$

So that,

$ \sqrt {\dfrac{{2a}}{{a \plus{} b}}} \plus{} \sqrt {\dfrac{{2b}}{{b \plus{} c}}} \plus{} \sqrt {\dfrac{{2c}}{{c \plus{} a}}} \ge \dfrac{1}{2}\left( {\dfrac{{{{\left( {a \plus{} b \plus{} c} \right)}^2}}}{{{a^2} \plus{} {b^2} \plus{} {c^2}}} \plus{} \dfrac{{{{\left( {ab \plus{} bc \plus{} ca} \right)}^2}}}{{{a^2}{b^2} \plus{} {b^2}{c^2} \plus{} {c^2}{a^2}}}} \right)$

$ \ge \dfrac{{\left( {a \plus{} b \plus{} c} \right)\left( {ab \plus{} bc \plus{} ca} \right)}}{{\sqrt {\left( {{a^2} \plus{} {b^2} \plus{} {c^2}} \right)\left( {{a^2}{b^2} \plus{} {b^2}{c^2} \plus{} {c^2}{a^2}} \right)} }}$ (from AM-GM inequality)

The proof is completed. Equality holds if and only if $ a \equal{} b \equal{} c$.

[quote="kuing"][quote="nguoivn"][quote="kuing"]
or
\[ 2\left( {a \plus{} b \plus{} c} \right)^2 \left( {a^2 b^2 \plus{} b^2 c^2 \plus{} c^2 a^2 } \right) \ge \left( {ab \plus{} bc \plus{} ca} \right)^2 \left( {a^2 \plus{} b^2 \plus{} c^2 \plus{} ab \plus{} bc \plus{} ca} \right),\]
that's easy to prove by Muirhead.

 :D[/quote]
AM-GM solved it easily, my friend  :)[/quote]

 :blush:

how to solved... :what?:[/quote]
My proof is also similar to you, Kuing. But with this last ineq, we can prove it more simpler:
The first, rewrite it to:
$ \frac {2(a^2b^2 \plus{} b^2c^2 \plus{} c^2a^2)}{(ab \plus{} bc \plus{} ca)^2} \ge \frac {a^2 \plus{} b^2 \plus{} c^2 \plus{} ab \plus{} bc \plus{} ca}{(a \plus{} b \plus{} c)^2}$
Or $ \sum (\frac {4a^2}{(ab \plus{} bc \plus{} ca)^2} \minus{} \frac {1}{(a \plus{} b \plus{} c)^2})(b \minus{} c)^2 \ge 0$
Assume that $ a \ge b \ge c$, then easily to see that $ Sa, Sb \ge 0$
In other hand, by AM-GM, we also have:
$ Sb \plus{} Sc \equal{} \frac {2(b^2 \plus{} c^2)}{(ab \plus{} bc \plus{} ca)^2} \minus{} \frac {1}{(a \plus{} b \plus{} c)^2} \ge \frac {(b \plus{} c)^2}{(ab \plus{} bc \plus{} ca)^2} \minus{} \frac {1}{(a \plus{} b \plus{} c)^2}$
So, we can prove $ Sb \plus{} Sc \ge 0$ if show that: $ (b \plus{} c)(a \plus{} b \plus{} c) \ge ab \plus{} bc \plus{} ca$ (obviously trues).
The proof completed  :)
PS: Nice proof, leviethai  :)

[quote="nguoivn"]
My proof is also similar to you, Kuing. But with this last ineq, we can prove it more simpler:
The first, rewrite it to:
$ \frac {2(a^2b^2 \plus{} b^2c^2 \plus{} c^2a^2)}{(ab \plus{} bc \plus{} ca)^2} \ge \frac {a^2 \plus{} b^2 \plus{} c^2 \plus{} ab \plus{} bc \plus{} ca}{(a \plus{} b \plus{} c)^2}$
Or $ \sum (\frac {4a^2}{(ab \plus{} bc \plus{} ca)^2} \minus{} \frac {1}{(a \plus{} b \plus{} c)^2})(b \minus{} c)^2 \ge 0$
Assume that $ a \ge b \ge c$, then easily to see that $ Sa, Sb \ge 0$
In other hand, by AM-GM, we also have:
$ Sb \plus{} Sc \equal{} \frac {2(b^2 \plus{} c^2)}{(ab \plus{} bc \plus{} ca)^2} \minus{} \frac {1}{(a \plus{} b \plus{} c)^2} \ge \frac {(b \plus{} c)^2}{(ab \plus{} bc \plus{} ca)^2} \minus{} \frac {1}{(a \plus{} b \plus{} c)^2}$
So, we can prove $ Sb \plus{} Sc \ge 0$ if show that: $ (b \plus{} c)(a \plus{} b \plus{} c) \ge ab \plus{} bc \plus{} ca$ (obviously trues).
The proof completed  :)
PS: Nice proof, leviethai  :)[/quote]

oh...S.O.S method...
thank you  :)


IMO 2003
inequalities
IMO
arithmetic sequence
IMO Shortlist

Let $n$ be a positive integer and let $x_1\le x_2\le\cdots\le x_n$ be real numbers.
Prove that

             \[
          \left(\sum_{i,j=1}^{n}|x_i-x_j|\right)^2\le\frac{2(n^2-1)}{3}\sum_{i,j=1}^{n}(x_i-x_j)^2.
             \]
Show that the equality holds if and only if $x_1, \ldots, x_n$ is an arithmetic sequence.

We can rewrite the given expression as
\( \sum_i (2i-n-1)x_i \)^2
\leq (n^2 - 1)/3 \( n\sum x_i^2 - (\sum x_i )^2\).
As the expression is translation invariant (obvious from the original form), we can assume that \sum x_i =0. The rest follows by Cauchy-Schwartz.

The crucial idea is that we may assume that Sum x_k = 0. I had tried to solve this problem, but I did not succeed. I came up with the first identity in Jayanta's message, but I was not smart enough to make his clever assumption. Let me complete the proof

(a) Since sum_{i,j} |x_j  x_i|= 2 sum_{i<j} (x_j  x_i) and sum_{i,j} (x_j  x_i)^2 = 2 sum{i<j} (x_j  x_i)^2 , it suffices to show that

( sum_{i<j} (x_j  x_i) )^2 <= [(n^2-1)/3] sum{i<j} (x_j  x_i)^2.

Since
sum_{i<j} (x_j  x_i)^2 = n sum x_i^2  (sum x_i )2 ,

and assuming that  sum x_i =0, it suffices to show that

( sum_{i<j} (x_j  x_i) )^2 <= [n(n^2-1)/3] sum x_i^2

We observe that

(*) 	sum_{i<j} (x_j  x_i)= (n-1) x_n +(n-3) x_{n-1} +-(n-3)x_2-(n-1) x_1=sum a_k x_k,

where a_{n-k} = n-1-2k, for k=1,,,n. Note that if n=2m, then

sum a_k^2 = 2(1^2+3^2++(2m-1)^2 ) = 2m(2m-1)(2m+1)/3 = n(n^2-1)/3,

and if n=2m-1, then a_{n-k} = 2(m-k), for k=1,,n (note that a_m=0), so

sum a_k^2 =8[(1^2+2^2++(m-1)^2] = 8(m-1)m(2m-1)/6 = n(n^2-1)/3,

since m(m-1)=(n^2-1)/4. Thus, by Cauchy's inequality we have,

( sum_{i<j| (x_j  x_i) )2  <= (sum a_k^2 ) (sum x_k^2 ) ={ n(n^2-1)/3}(sum x_k^2 ),

as desired.

Comment: To see (*), consider the following triangle

x_n-x_1 	x_{n-1}-x_1     x_3-x_1  x_2-x_1
x_n-x_2 	x_{n-1}-x_2      x_3-x_2

	x_{n-1}-x_{n-2}
x_n-x_{n-2}
x_n-x_{n-1}

(b) We have quality of if and only if x_k= 0 for all k, or a_k= t*x_k for all k and some nonzero real number t. In the first case clearly we have an arithmetic progression. In the second case, since 2 = a_k-a_{k-1} = t(x_k-x_{k-1}), we have x_k = x_{k-1} + 2/t, and the result follows.

well, I meant

"Since
sum_{i<j} (x_j  x_i)^2 = n sum x_i^2  (sum x_i )^2 ,

and assuming that sum x_i =0, .....e.t.c"

this one was  a rather cute problem.but two people have beaten me agen b4 i cud post my solution.and my proof is same as achilleas proof(u guys are fast)
which wud u ppl rate as the best question at this year's imo(i luvd no2)

Question: Is the following inequality true?

Let n>2 and x_1 <=x_2<=...<=x_n and y_1<=y_2<=...<=y_n. Then

(sum_{i,j} |x_i-x_j|) * (sum_{i,j} |y_i-y_j|) <= 2(n^2-1)/3 sum_{i,j} |x_i-x_j)(y_i-y_j)| .

This would be a generalization of the IMO problem.

We could assume that sum x_k=sum y_k=0 and use the identity

n*(sum x_k * y_k) = (sum x_k)*(sum y_k) + sum_{i<j} (x_i-x_j)(y_i-y_j).

Then it would suffice to show that

(sum_{i<j} (x_j-x_j)) * (sum_{i<j} (y_j-y_i) ) <= [2n(n^2-1)/3] sum x_k * y_k

Since sum_{i<j} (x_j-x_i)) = sum a_k * x_k and sum_{i<j} (y_j-y_i)) = sum a_k * y_k, where a_k are as above for k=1,2,..,n-1 (I had written up to n inadvertently in my previous message).
Also sum (a_k)^2=2n(n^2-1)/3 (proof in my previous message) and

sum_{i<j} (x_j-x_j)) * (sum_{i<j} (y_j-y_i) ) =(sum a_k * x_k) * (sum a_k * y_k)

but I cannot see how this would prove it; it seems like a deadend. Any other approach? (Of course, the inequality could be false)

Elinor, I hope this is the way you did it..

The number of terms is

(n-1)*1^2+(n-2)*2^2+...+1*(n-1)^2 = sum (n-k)*k^2 for k=1,2,...,n-1 = n^2(n^2-1)/12.

So the rhs of the reduced inequality (i.e. the sum for i<j) times the numer of terms n^2(n^2-1)/12 is larger than or equal to the square of the sum

S=(a_1+...+a_{n-1} +2*(a_1+a_2) + 2*(a_2+a_3)+...+2*(a_{n-2}+a_{n-1})+..+(n-1)*(a_1+....+a_{n-1}))

(This also follows from Cauchy-Scwartz). In order to finish the proof we need to show that

S>= (n/2)*S' , where S' is the sum=(a_1+...+a_{n-1} +
(a_1+a_2) + (a_2+a_3)+...+(a_{n-2}+a_{n-1})+..+(a_1+....+a_{n-1}))

In order to do this we observe that after making the operations in the two sums we see that for k=1,2,..,n-1, the coefficient of a_k in S is nk(n-k)/2 and in S' is k(n-k). (of course, this needs proof!!) Thus we actually have equality

S= (n/2)*S' ,

and the result follows.

[quote="Achilleas Sinefakopoulos"]Question: Is the following inequality true?

Let n>2 and x_1 <=x_2<=...<=x_n and y_1<=y_2<=...<=y_n. Then

(sum_{i,j} |x_i-x_j|) * (sum_{i,j} |y_i-y_j|) <= 2(n^2-1)/3 sum_{i,j} |x_i-x_j)(y_i-y_j)| .

...(Of course, the inequality could be false)[/quote]

It is false in general, (as will be shown later).  This can also be easily seen by trying n=3.  However under certain restrictions for the x_i, y_i the attack given by Elinor and Achilles can work by replacing the Cauchy-Schwartz (or AM-RMS) inequality with Chebyshev's inequality.  However this gives the very awkward restriction that if f(i, j) = |x_i-x_j|/|i-j| and g(i,j) = |y_i-y_j|/|i-j|, f(i, j)<f(k,l) iff g(i, j)<g(k,l).  I can't think of any interesting pairs of sequences that satisfy this condition, other than y_i = x_i + ki for k in R.

Also, there is a corresponding inequality using the other form of Chebyshev if f(i, j)<f(k,l) iff g(i, j)>g(k,l), showing that the originally proposed inequality is in general false.

[b]Lemma:[/b] $\sum_{i,j=1}^n |x_i - x_j| |i - j| = \frac{n \sum_{i,j=1} |x_i - x_j|}{2}$.
[i]Proof:[/i] Let $a_1 = x_1$, and let $a_{i} = x_i - x_{i-1}$ for all $i$ with $2 \leq i \leq n$. The lemma we wish to prove can easily be seen to be equivalent to
$\sum_{1 \leq i < j \leq n} (i - j)(a_{i+1} + a_{i+2} + \cdots + a_j) = \frac{n}{2} \sum_{1 \leq i < j \leq n} (a_{i+1} + a_{i+2} + \cdots + a_j).$

When expanded, both sides are a linear combination of $a_1, a_2, \cdots, a_n$. We will determine the coefficients of each variable on both sides of the equation.

On the left-hand side, $a_k$ appears if and only if $i+1 \leq k \leq j$, in which case it comes with a factor if $(j-i)$. Hence, the coefficient of $a_k$ on the left-hand side is $\sum_{i=1}^{k-1} \sum_{j=k}^n (j-i) = \frac{n(k-1)(n-k+1)}{2}$. On the right-hand side, $a_k$ appears iff $i+1 \leq k \leq j$, in which case it comes with a factor if $\frac{n}{2}$. Hence, the coefficient of $a_k$ on the right-hand side is $\frac{n(k-1)(n-k+1)}{2}$, which is equal to the coefficient on the left. $\blacksquare$

It can easily be seen that $\sum_{i=1}^n \sum_{j=1}^n |i - j|^2 = \frac{2(n^2-1)}{3} \cdot \frac{n^2}{4}$. By the Cauchy-Schwarz inequality,
\begin{align*}
\frac{2(n^2 - 1)}{3} \left( \sum_{i,j=1}^n |x_i - x_j|^2 \right)
&= \frac{\left( \sum_{i,j=1}^n |x_i - x_j|^2 \right) \left( \sum_{j=1}^n |i-j|^2 \right)}{\frac{n^2}{4}} \\
&\geq \left (\frac{ \sum_{i,j=1}^n |x_i - x_j| \, |i - j| }{ \frac{n}{2} } \right)^2 \\
&= \left( \sum_{i,j=1}^n |x_i - x_j| \right)^2,
\end{align*}
as desired.

The cases of equality easily follow from the above application of Cauchy-Schwarz.

I have known that this problem can be solved using Cauchy-Schwarz inequality, but even with this information I haven't known how to solve it. It can be solved by using derivatives in a very simple way. Just compute derivatives on each variable and it can be easily seen that $x_2-x_1=x_3-x_2$ and so on.

We first make use of symmetry to rewrite the inequality as
\[\left(\sum_{1\le i<j\le n}|x_i-x_j|\right)^2\le\frac{n^2-1}3\left(\sum_{1\le i<j\le n}|x_i-x_j|^2\right)\].
WLOG that $x_1\le x_2\le\dots\le x_n$ and let $x_{i-1}-x_i=a_i$. The inequality is equivalent to
\[\left(\sum_{1\le i<j\le n}\left(a_i+\dots+a_{j-1}\right) \right)^2\le\frac{n^2-1}3\left(\sum_{1\le i<j\le n}\left(a_i+\dots+a_{j-1}\right)^2\right)\] for all $a_1,\dots,a_{n-1}$.
But this can be rewritten as
\[\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right) \right)^2\le\frac{n^2-1}3\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\]
By Cauchy-Schwarz:
\begin{align*}
\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\left(\sum_{l=1}^{n-1}\sum_{j-i=l}l^2\right)&\ge\left(\sum_{l=1}^{n-1}\sum_{j-i=l}l\left(a_i+\dots+a_j\right)\right)^2\\
&=\left(\sum_{l=1}^{n-1}l\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2
\end{align*}

We claim that
\[\sum_{j-i=l}(a_i+\dots+a_j)=\sum_{j-i=(n-l)}(a_i+\dots+a_j)\]. Indeed, we may consider the $l\times(n-l)$ matrix:
\[ \left( \begin{array}{cccc}
a_1 & a_2 & \dots & a_l \\
a_2 & a_3 & \dots & a_{l+1} \\
\vdots & \vdots & \ddots & \vdots\\
a_{n-l} & a_{n-l+1} & \dots & a_n \end{array} \right)\]
The first sum corresponds to summing the matrix row by row, and the second corresponds to summing it column by column. Thus the two sums are equal, as claimed.

Hence:
\begin{align*}
\left(\sum_{l=1}^{n-1}l\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2&=\left(\sum_{l=1}^{n-1}\frac n2\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2\\
&=\frac{n^2}4\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2
\end{align*}

We may also check that
\[\sum_{l=1}^{n-1}\sum_{j-i=l}l^2=\sum_{l=1}^{n-1}(n-l)l^2=\frac{n^4-n^2}{12}\]. Thus we have proven that
\[\frac{n^4-n^2}{12}\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\ge\frac{n^2}4\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2\]
Dividing $\frac{n^2}4$ yields
\[\frac{n^2-1}{3}\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\ge\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2\] as desired.

Furthermore, from Cauchy's equality condition, equality holds if and only if $a_1=a_2=\dots=a_{n-1}$ - that is, when the $x_i$ form an arithmetic sequence.

This is a very old inequality and there are a number of elegant solutions but I would like to contribute with a very straightforward approach using induction and derivatives.
For $n=3$, the inequality is obviously true. Now let's assume that the inequality is true for $n$ and we will prove it for $n+1$.
Let's define  $y_{i}$ such that $y_{i}=x_{i}-\frac{\sum_{j=1}^{n}x_{j}}{n}$ and we have $\sum_{i=1}^{n} y_{i}=0$
We need to prove that for $y_{n+1} \geq y_{n}$ we have: $P(y_{n+1}) \geq 0$ where:
\[P(y_{n+1}) = \frac{2}{3}((n+1)^2-1)(\sum_{i,j=1}^{n+1} (y_{i}-y_{j})^2) - (\sum_{i,j=1}^{n+1} |y_{i}-y_{j}|)^2 \geq 0\]
Let $A_{n} = \sum_{i,j=1}^{n} (y_{i}-y_{j})^2$ and $B_{n} = \sum_{i,j=1}^{n} |y_{i}-y_{j}|$ and we have from induction's hypothesis $\frac{2}{3}(n^2-1)A_{n} \geq B_{n}^2 $.
After Simplification, we get:
\[P(y_{n+1}) = \frac{2}{3}((n+1)^2-1)(2ny_{n+1}^2+\frac{n+1}{n}A_{n})-(2ny_{n+1}+B_{n})^2\]
$P$ reaches a minimal value for $y_{n+1}$ such that $P'(y_{n+1})=0$ and after simplification, we get:
\[P'(y_{n+1})=0 \Leftrightarrow	 y_{n+1}=\frac{3B_{n}}{2n(n-1)}\]
Then we have:
\[P(y_{n+1}) \geq P(\frac{3B_{n}}{2n(n-1)})=\frac{n+2}{n-1}(\frac{2}{3}(n^2-1)A_{n}-B_{n}^2) \geq 0\]
Equality case: we have $\frac{2}{3}(n^2-1)A_{n}-B_{n}^2 = 0$ which is true only if there exists a real number $r$ such that $x_{i}=ir$ for all $i\leq n$, and
\[x_{n+1}=y_{n+1}+\frac{\sum_{i=1}^{n} x_{i}}{n}=\frac{3\sum_{i,j=1}^{n}|i-j|r}{2n(n-1)}+\frac{\sum_{i=1}^{n} ir}{n}=\frac{(n+1)r}{2}+\frac{(n+1)r}{2}=(n+1)r\]
Which completes the proof by induction.

basically the same as first cauchy sol

WLOG let $x_1\le x_2\le \cdots \le x_n$, then we work on the LHS,
\begin{align*}
\sum_{i=1}^n \sum_{j=1}^n |x_i-x_j|
&=\sum_{i=1}^n \left(\sum_{j=1}^{i-1}(x_i-x_j)+\sum_{j=i+1}^{n}(x_j-x_i)\right)\\
&=\sum_{i=1}^n(2i-n-1)x_i+\sum_{i=1}^n \left(\sum_{j=i+1}^{n}x_j-\sum_{j=1}^{i-1}x_j\right)\\
&=2\sum_{i=1}^n(2i-n-1)x_i.
\end{align*}
Now we work on the RHS,
\begin{align*}
\sum_{i=1}^n \sum_{j=1}^n |x_i-x_j|^2
&=\sum_{i=1}^n\sum_{j=1}^n (x_i^2+x_j^2)-2\sum_{i=1}^n\sum_{j=1}^n x_ix_j\\
&=2n\sum_{i=1}^n x_i^2-2\left(\sum_{i=1}^n x_i\right)^2.\\
\end{align*}

The key idea is that the original inequality does not depend on $\sum_{i=1}^n x_i$, so we may set it equal to zero. Then the desired inequality becomes
\[\left(\sum_{i=1}^n(2i-n-1)x_i\right)^2\le\frac{n(n^2-1)}{3}\sum_{i=1}^n x_i^2.\]

Applying C-S on the LHS, we have
\[\left(\sum_{i=1}^n(2i-n-1)x_i\right)^2\le\left(\sum_{i=1}^n (2i-n-1)^2\right)\left(\sum_{i=1}^n x_i^2\right),\]
so it suffices to show that
\[\sum_{i=1}^n (2i-n-1)^2=\frac{n(n^2-1)}{3}.\]

If $n=2m$, we have
\begin{align*}
\sum_{i=1}^n (2i-n-1)^2 &= 2(1^2+3^2+\cdots+(2m-1)^2)\\
&=2\sum_{i=1}^{m}\left(\binom{2i-1}{2}+\binom{2i}{2}\right)\\
&=2\binom{2m+1}{3}\\
&=\frac{n(n^2-1)}{3},
\end{align*}
as desired.

If $n=2m+1$, we have
\begin{align*}
\sum_{i=1}^n (2i-n-1)^2 &= 2(2^2+\cdots+(2m)^2)\\
&=2\sum_{i=1}^{m}\left(\binom{2i}{2}+\binom{2i+1}{2}\right)\\
&=2\binom{2m+2}{3}\\
&=\frac{n(n^2-1)}{3},
\end{align*}
as desired.

The equality case occurs at
\[x_1:x_2:\cdots:x_n=1-n:3-n:\cdots:n-1,\]
so they are in arithmetic progression, as desired.

This would have been a really nice inequality problem if the question hadn't stated the inequality case.
Anyway, posting this for storage, basically the same CS solution as others.
We'll first rewrite the sum condition as
\[ \left( \sum_{1 \le i < j \le n} (x_j - x_i) \right)^2 \le \frac{n^2 - 1}{3} \sum_{1 \le i < j \le n} (x_j - x_i)^2 \]
Now, we'll prove that
\[ \sum_{1 \le i < j \le n} \frac{(j - i)^2}{n^2} = \frac{n^2}{12} \]
This can be proved by noticing that
\begin{align*}
 \sum_{1 \le i < j \le n} \frac{(j - i)^2}{n^2} &= \frac{1}{n^2} \sum_{1 \le i <j \le n} (j - i)^2 \\
&= \frac{1}{n^2} \sum_{k = 1}^{n-1} k^2 (n - k) \\
&= \frac{1}{n} \sum_{k = 1}^{n-1} k^2 - \frac{1}{n^2} \sum_{k = 1}^{n-1} k^3 \\
&= \frac{1}{n} \left( \frac{1}{6} (n-1)(n)(2n-1) \right) - \frac{1}{n^2} \left( \frac{(n-1)n}{2} \right)^2 \\
&= \frac{(n-1)(2n-1)}{6} - \frac{(n-1)^2}{4} \\
&= \frac{2(2n^2 - 3n + 1) - 3(n^2 - 2n + 1)}{12} \\
&= \frac{n^2 - 1}{12}
\end{align*}
which is what we wanted.
Therefore, we could rewrite the condition as
\[ \left( \sum_{1 \le i < j \le n} (x_j - x_i) \right)^2 \le 4 \left( \sum_{1 \le i < j \le n} \frac{(j - i)^2}{n^2} \right) \left( \sum_{1 \le i < j \le n} (x_j - x_i)^2 \right) \]
Now, apply CS at the RHS, we have
\[ 4 \left( \sum_{1 \le i < j \le n} \frac{(j - i)^2}{n^2} \right) \left( \sum_{1 \le i < j \le n} (x_j - x_i)^2 \right) \ge \left( 2 \sum_{1 \le i < j \le n} \frac{j - i}{n} (x_j - x_i) \right)^2 \]
It suffices to prove that
\[ 2 \sum_{1 \le i < j \le n} \frac{j - i}{n} (x_j - x_i) =  \sum_{1 \le i < j \le n} (x_j - x_i) \]
But this is true by considering each coefficient of $x_i$.
Notice that in the RHS, the coefficient of $x_j$ is $( j - 1) - (n - j) = 2j - n - 1$ and in the LHS, we have the coefficient of $x_j$ is
\[ \frac{2 ( (1 + 2 + \dots + j - 1) - (1 + \dots + (n - j)) )}{n} = \frac{(j - 1)j - (n -j)(n-j+1)}{n} = \frac{2nj - n^2 - n}{n} = 2j - n - 1\]

Let $L$ and $R$ equal the LHS and RHS of the inequality respectively. We have $R = \frac{4(n^2-1)}{3}\sum_{i>j\ge1}^{n}(x_i-x_j)^2$ since $(x_i-x_j)^2 = (x_j-x_i)^2$. Next, let $J = \sum_{i>j\ge1}^{n}(x_i-x_j)^2$ and $K = \sum_{i = 1}^n\sum_{i \ge j \ge 1}^nx_j^2$. Also, let $c_n = \binom{n}{2}, c_{n-1} = \binom{n}{2}-n, \ldots c_1 = \binom{n}{2}-(n-1)n = -\binom{n}{2}$. By Cauchy-Schwarz, $$JK = \left((x_2-x_1)^2+(x_3-x_1)^2+(x_3-x_2)^2+\ldots+(x_n^2-x_{n-1}^2)\right)\left((1^2)+(2^2+1^2)+(3^2+\ldots+2^2+1^2)\right)$$ $$\ge \left(1(x_2-x_1)+2(x_3-x_1)+1(x_3-x_2)+\ldots+2(x_n-x_{n-2})+1(x_n-x_{n-1})\right)^2$$ $$= \left(c_nx_n+c_{n-1}x_{n-1}+c_{n-2}x_{n-2}+\ldots+c_1x_1\right)^2 = I^2$$ where the last step can be proven by considering specific values of $x_i$.

Next, I will find the specific value of $K$. We have the following lemmas: $\sum_{i = 1}^ni^3 = \frac{n^2(n+1)^2}{4}, \sum_{i = 1}^ni^2 = \frac{n(n+1)(2n+1)}{6}, \sum_{i = 1}^ni = \frac{n(n+1)}{2}.$ Therefore, $$K = \sum_{i = 1}^{n-1} \frac{i(i+1)(2i+1)}{6} = \sum_{i = 1}^n \frac{2i^3+3i^2+i}{6} = \frac{\frac{(n-1)^2n^2}{2}+\frac{(n-1)n(2n-1)}{2}+\frac{(n-1)n}{2}}{6} = \frac{(n-1)n^2(n+1)}{12}.$$ Therefore, we have $$R = \frac{4(n^2-1)}{3K}JK \ge \frac{4(n-1)(n+1)}{\frac{3(n-1)n^2(n+1)}{12}}I^2 = \frac{16}{n^2}I^2.$$

Finally, it suffices to prove $L = \frac{16}{n^2}I^2$. Note that $L = 4\left(\sum_{i \ge 1 \ge 1}|x_i-x_j|\right)^2$. Also, let $d_i = 2i-(n+1)$. For specific $x_p$, notice that if $i > p$, then $|x_i-x_p|$ will result in a negative $x_p$ term. If $i < p$, then $|x_p-x_i|$ will result in a positive $x_p$ term, and otherwise nothing. We now see that the coefficient of $x_p$ will be $$\left((p-1)-1+1\right)-\left(n-(p+1)+1)\right) = 2p-n-1$$ as desired. However, $\frac{nd_i}{2} = pn-\frac{n^2}{2}-\frac{n}{2} = \binom{n}{2}-n(n-p) = xc_i$. This means $L = 4\left(\frac{2}{n}\right)^2I^2 = \frac{16}{n^2}I^2$, which proves the inequality. Finally, we see that equality holds when $\frac{|x_i-x_j|}{|i-j|}$ is a constant which gives equality in the Cauchy-Schwarz. Since $i < j \implies x_i < x_j$, this means $x_1, x_2, \ldots x_n$ must be an arithmetic sequence. $\blacksquare$

[b][color=#f00]Remarks: [/color][/b] If this problem did not tell you the equality condition, it would be quite harder because you have to guess it, which makes the Cauchy-Schwarz part much more contrived. I actually enjoyed bashing this problem unlike some other problems I did.

Shift so that \(\sum_{i=1}^nx_i=0\). By Cauchy-Schwarz, \[ \left[\sum_{i=1}^n\left(i-\frac{n+1}2\right)x_i\right]^2 \le\frac{n(n+1)(n-1)}{12}\cdot\sum_{i=1}^nx_i^2;\] that is, \[\left[4\sum_{i=1}^n\left(i-\frac{n+1}2\right)x_i\right]^2 \le\frac{2(n^2-1)}3\left[2n\sum_{i=1}^nx_i^2-2\left(\sum_{i=1}^nx_i\right)^2\right],\] which is equivalent to the desired inequality. Equality holds iff \(x_1\), \ldots, \(x_n\) is an arithmetic sequence.

Since shifting the sequence $(x_1,x_2,\dots, x_n)$ does not affect the problem, we can assume that the sum is $0$. We have
\begin{align*}\left(\sum_{i,j=1}^{n}|x_i-x_j|\right)^2 &=\left(2\sum_{1\le i\le j\le n}(x_j-x_i)\right)^2 \\
&= \left((2n-2)x_n+(2n-6)x_{n-1}+\dots +(2-2n)x_1\right)^2 \\
&\le ((2n-2)^2+(2n-6)^2+(2n-10)^2+\dots + (2-2n)^2)(x_1^2+x_2^2+\dots + x_n^2) \\
&= \frac{4(n-1)(n)(n+1)}{3}(x_1^2+x_2^2+\dots + x_n^2) \\
&= \frac{2(n^2-1)}{3}\cdot 2(nx_1^2 + nx_2^2 + \dots + nx_n^2) \\
&= \frac{2(n^2-1)}{3}\cdot 2\left((n-1)\left(\sum_{i=1}^{n}{x_i^2}\right) + \left(\sum_{i=1}^{n}{x_i}\right)^2 - 2\sum_{1\le i<j\le n}x_ix_j\right) \\
&= \frac{2(n^2-1)}{3}\cdot 2\left(\sum_{1\le i<j\le n}(x_i-x_j)^2\right) \\
&= \frac{2(n^2-1)}{3}\sum_{i,j=1}^{n}(x_i-x_j)^2
\end{align*}
Clearly, the equality condition of Cauchy will force the equality case of this inequality to also be an arithmetic sequence. In the case that one of the coefficients in the second line of our work is zero, we can add $\varepsilon$ to each of the coefficients to get the same inequality but avoid division by zero.

Induction led me to a solution that is way too long, but I’d recommend you to try it if you couldn’t find the Cauchy-Schwarz way (like me)

We will do induction on $n$. The base case $n = 1$ simplifies to $0 \le 0$, which is clear. For the inductive step, we will assume that the problem is true for $n = k$, and prove that it is also true for $n = k + 1$. Noticing that the problem statement does not change if we shift all variables $x_i$ by a constant, assume that their sum $\sum_{i = 1}^k x_i = 0$ to simplify calculations. Let \[\rho_1 = \sum_{i, j=1}^k |x_i - x_j| \text{ and } \rho_2 = \sum_{i,j = 1}^k (x_i - x_j)^2.\]
    By the inductive hypothesis, we may assume that \[\frac{2(k^2 - 1)}{3} \cdot \rho_2 \ge \rho_1^2.\]
    Let $P(x_{k + 1})$ be \[P(x_{k + 1}) = \frac{2[(k + 1)^2 - 1]}{3} \cdot \sum_{i,j = 1}^{k + 1} (x_i - x_j)^2 - \left(\sum_{i,j = 1}^{k + 1}|x_i - x_j|\right)^2.\]
    We wish to show that $P(x_{k + 1}) \ge 0$ for $x_{k + 1} \ge x_k$. Using the fact that $\sum_{i = 1}^k x_i = 0$, we can calculate \[\sum_{i,j = 1}^{k + 1} |x_i - x_j| = p_1 + 2 \sum_{i = 1}^{k} (x_{k + 1} - x_i) = p_1 + 2kx_{k + 1}.\]
    We can also calculate \[\sum_{i,j = 1}^{k + 1}(x_i - x_j)^2 = \rho_2 + 2\sum_{i = 1}^k (x_i - x_{k + 1})^2 = p_2 + 2\sum_{i = 1}^k x_i^2 + 2k x_{k + 1}^2.\]
    In addition, I claim that \[2\sum_{i = 1}^k x_i^2 = \frac{\rho_2}{k}.\]
    This is because \begin{align*}
        \rho_2 &= \sum_{i,j = 1}^k (x_i - x_j)^2 \\
        &= 2k \sum_{i = 1}^k x_i^2 - 2\sum_{i,j = 1}^k x_i x_j \\
        &= 2k \sum_{i = 1}^k x_i^2 - 2 \left(\sum_{i = 1}^k x_i\right)\left(\sum_{j = 1}^k x_j\right) \\
        &= 2k \sum_{i = 1}^k x_i^2.
    \end{align*}
    So, we can further simplify our formula to get \[\sum_{i,j = 1}^{k + 1} (x_i - x_j)^2 = \frac{k + 1}{k} \cdot \rho_2 + 2kx_{k + 1}^2.\]
    Thus, \[P(x_{k + 1}) = \frac{2k^2 + 4k}{3} \cdot \left(\frac{k + 1}{k} \cdot \rho_2 + 2kx_{k + 1}^2\right) - (\rho_1 + 2k x_{k + 1})^2.\]
    Treating this as a quadratic polynomial in terms of $x_{k + 1}$ holding all other terms are constant, $P(x_{k + 1})$ is minimized at \[x_{k + 1} = \frac{-(-4k\rho_1)}{2\left(\frac{4k^3 + 8k^2}{3} - 4k^2\right)} = \frac{4k\rho_1}{2\left(\frac{4k^3 - 4k^2}{3}\right)} = \frac{3\rho_1}{2k(k - 1)}.\]
    Plugging this in, \[P\left(\frac{3\rho_1}{2k(k - 1)}\right) = \frac{2k^2 + 4k}{3} \cdot \left(\frac{k + 1}{k} \cdot \rho_2 + \frac{9\rho_1^2}{2k(k - 1)^2}\right) - \left(\rho_1 + \frac{3\rho_1}{k - 1}\right)^2.\]
    This simplifies to \begin{align*}
        P(x_{k + 1}) &= \frac{2(k + 2)(k + 1)}{3} \cdot \rho_2 + \left(\frac{3(k + 2)}{(k - 1)^2} - \frac{(k + 2)^2}{(k - 1)^2}\right)\rho_1^2 \\
        &= \frac{k + 2}{k - 1}\left(\frac{2(k^2 - 1)}{3}\rho_2 - \rho_1^2\right).
    \end{align*}
    By the inductive hypothesis, $\frac{2(k^2 - 1)}{3}\rho_2 \ge \rho_1^2$, so we get that $P(x_{k + 1}) \ge 0$ which completes the inductive step. Equality holds if and only if for all $0 \le k \le n - 1$, \[x_{k + 1} = \frac{3\sum_{i,j = 1}^k |x_i - x_j|}{2k(k - 1)}.\]
    We will prove that this is equivalent to $x_1, x_2, \ldots, x_n$ being an arithmetic sequence using induction. For $n = 2$, the problem statement becomes $4(x_2 - x_1)^2 \le 4(x_2 - x_1)^2$, which is true for all $x_1$ and $x_2$. Since any two numbers are in an arithmetic sequence, the base case is clear. For the inductive step, assume that $d = x_2 - x_1 = x_3 - x_2 = \cdots = x_k - x_{k - 1}$, and we will prove that $x_{k + 1} - x_k = d$ as well. This is equivalent to the numbers being in an arithmetic sequence. Since we previously assumed that $x_1 + x_2 + \cdots + x_k = 0$, this means that $x_k = \frac{(k - 1)d}{2}$. We can simplify \begin{align*}
        x_{k + 1} &= \frac{3 \sum_{i,j = 1}^k |x_i - x_j|}{2k(k - 1)} \\
        &= \frac{3 \sum_{1 \le i < j \le k} d(j - i)}{k(k - 1)}.
        \end{align*}
    In the sum in the numerator, a difference of $d$ occurs $n - 1$ times, a difference of $2d$ occurs $n - 2$ times, and so-on. Thus, \begin{align*}
        x_{k + 1} &= \frac{3d}{(k - 1)k}((k - 1) \cdot 1 + (k - 2) \cdot 2 + \cdots + 1 \cdot (k - 1)) \\
        &= \frac{3d}{(k - 1)k} \sum_{i = 1}^{k - 1} i(k - i) \\
        &= \frac{3d}{(k - 1)k} \left(k\sum_{i = 1}^{k - 1} i - \sum_{i = 1}^{k - 1} i^2 \right) \\
        &= \frac{3d}{(k - 1)k} \left(k \cdot \frac{(k - 1)k}{2} - \frac{(k - 1)k(2k - 1}{6}\right) \\
        &= 3d \left(\frac{k}{2} - \frac{2k - 1}{6}\right) \\
        &= d\left(\frac{k + 1}{2}\right).
    \end{align*}
    Thus, $x_{k + 1} - x_k = d$, completing the inductive step. Thus, we have proven the inequality and have shown that equality holds if and only if the variables are in an arithmetic sequence.


algebra
polynomial
algorithm
Gauss
number theory unsolved
number theory

This is supposed to be fairly easy, but I can't seem to do it for some reason  :(

Given $ \phi_n(x) \equal{} \prod_{d|n}(x^d \minus{} 1)^{\mu(n/d)}$, show the coefficients of $ \phi_n(x)$ are integers.

You prove it by induction.  For n=1 it is true. Than you assume it holds for all  cyclotomic polynomials less than n.  You write
x^n-1= f(x) \phi_n(x)  where f(x) is a polynomial with integer coefficients (being a product of cyclotomic polynomials less than n).   Since x^n-1=f(x) q(x)+r(x)  all with integer coefficients. By uniqueness of the division algorithm \phi_n(x) = q(x) which has integer coefficients.

Using some algebra:
a) It's a monic divisor of $ x^n\minus{}1$, so the claim follows from Gauss' lemma.

b) It's monic, has rational coefficients and has only algebraic integers as roots. As $ \mathbb Z$ is integrally closed, it has integer coefficients.


Hi!
I am thinking of a Computer Science major at STanford or Caltech. But at the same time, I am hugely interested in the upcoming field of nanotechnology. But no place offers any major in nanotechnology right now as its still a 'research' field. Still, even at undergrad, I want to experience Nanotech so that I might be well prepared for research in this later in life .  I once read that at Princeton, where there is no biotech, students and faculty had prepared a list of courses one could do to expereince biotech , even though that s no major..... do you know of such courses and gropus at Stanford and Caltech? Which departments would best cover this? Are there any specifc courses for this? Also, this might be 'kiddish', but which are the best places right now in Nanotech research and education , esp among the two above?i.e. which places are making the best strides in Nanotech research and if you know, have the most relevant courses for the same.

 Thanks a lot!

Rushil

That's weird, cuz I'm choosing between the same schools, and I'm also interested in nanotechnology.

That's great! So which place are you leaning towards?
Would you (or someone else) have more specific info on my question pertaining to nanotech?
Thanks!

I guess you could try to find out which departments are doing nanotechnology-related research at each school.  Personally, I think I'm leaning towards Stanford.

Thats great, I too am toward Stanford! But since you are also into nanotech, have you found out more about whuch place offers a better thing for Nanotech --- I though STanford offered a better deal since it has more courses and a devoted centre etc... which other places besides these two are making great strides in nanotech and offer great courses as well!

I can't help you with the schools you mentioned, but I do know that Waterloo has a pretty selective [url=http://www.nanotech.uwaterloo.ca/]Nanotechnology Engineering[/url] program.

I sent my matriculation thingy to Stanford.

I guess I can't help you much, but I do know that Rice has some good nanotech stuff.. with the whole bucky balls and whatnot


Is there a polynomial with 0-1 coefficients that is reducible and such that no other divisor except 1 and himself has all coefficients equal to 0,1 or -1?

Gm. There exist a cyclotomic polynomial (which is the divisor of $1+x+x^2+\dots+x^{n-1}$) with some coefficient, equal to a given integer $m$. I guess that the quotient also have not coefficients equal to 0 and $\pm 1$, at least some times. Here is an example: take $n=210$. Check it with maple.

[quote="Fedor Petrov"] Here is an example: take $n=210$. Check it with maple.[/quote]
Hmm... What exactly is the example?  :?  Surely not $1+x+\dots+x^{209}$: this one is divisible by $1+x$. Seems I'm missing something here  :?

Ops, I misunderstood the question. I thought about just two divisors, which product equals the initial polynomial.

Well, I hope that the product of cyclotomics of orders 165 and 525 is an example.

Sorry again. Coefficients of a product are 0,1-1.

Harazi, do you know a solution? Or the answer at least?

No, Fedor, unfortunately I do not have a solution. I don't even know the answer, tough I strongly believe it is negative. I tried a computer research, but I haven't found any negative example.

Does your friend (from a source) know an answer, or it was just a question?

No,it was just a question.He asked it  after solving the nice Ens problem with the irreducible polynomial that has 0 and 1 as coefficients.Anyway it is a nice question.


let x,y,z are non-gative numbers such as:  3xyz(x+y+z)$ \ge$ 0

and let a,b,c, are base of triagle ABC ,S is the area of ABC

PROVE THAT:  x$ {a}^{2}$ +y$ {b}^{2}$ +z$ {c}^{2}$ $ \ge$ 4S$ \sqrt{xy\plus{}yz\plus{}zx}$

b) if x,y,z are any real numbers such as: 3xyz(x+y+z)$ \ge$ 0  the inqualities true or false?

[quote="trannguyenquyND_VN"]let x,y,z are non-gative numbers such as:  3xyz(x+y+z)$ \ge$ 0

and let a,b,c, are base of triagle ABC ,S is the area of ABC

PROVE THAT:  x$ {a}^{2}$ +y$ {b}^{2}$ +z$ {c}^{2}$ $ \ge$ 4S$ \sqrt {xy \plus{} yz \plus{} zx}$

b) if x,y,z are any real numbers such as: 3xyz(x+y+z)$ \ge$ 0  the inqualities true or false?[/quote]
this inequaliti true with x+y≥0, y+z≥0, z+x≥0; xy+yz+zx≥0.  x,y,z can<0.
ex.  10a^2+15b^2≥40S+2c^2;
       12a^2+24b^2≥72S+c^2;
..............................................

(to trannguyenquy: vao email or phone 0984678582) tren dien dan) :lol:  :lol:

What is with this picture?  :huh:
Please don't post such insignificant pictures.....
However the solution that quykhtn-qa1 gave seems to be correct.

Thanks.

are a, b, c, x, y, z similarly sorted?

if so, the inequality will be a simple consequence of Chebyshev's and Weitzenbock's inequalities.  :)


hello, we have by the addition formuals
$ \displaystyle{4\sin(\frac{x}{2})^2\minus{}\sqrt{3}\cos(2x)\minus{}1\minus{}2\cos(x\minus{}\frac{3}{4}\pi)^2\equal{}\minus{}2(\cos(x)\plus{}\cos(2x\plus{}\frac{\pi}{6}))\equal{}\minus{}4\cos(\frac{3x}{2}\plus{}\frac{\pi}{12})\cdot\cos(\frac{x}{2}\plus{}\frac{\pi}{12})\equal{}0}$ and this is easy to solve.
Sonnhard.

[quote="Dr Sonnhard Graubner"]hello, we have by the addition formuals
$ \displaystyle{4\sin(\frac {x}{2})^2 - \sqrt {3}\cos(2x) - 1 - 2\cos(x - \frac {3}{4}\pi)^2 = - 2(\cos(x) + \cos(2x + \frac {\pi}{6})) = - 4\cos(\frac {3x}{2} + \frac {\pi}{12})\cdot\cos(\frac {x}{2} + \frac {\pi}{12}) = 0}$ and this is easy to solve.
Sonnhard.[/quote]

[size=150][color=darkblue]Yes easy we get: [/color][/size] $ [ \begin{array}{l} x = \frac {{5\pi }}{{18}} + k\frac {{2\pi }}{3} \\
 \\
x = \frac {{5\pi }}{6} + l2\pi \\
\end{array}$ , $ k,l \in Z$


inequalities
integration
calculus
real analysis
real analysis unsolved

[color=blue]
Let $f: [0,1]\to\mathbb{R}$ be a $C^{1}[a,b]$ function. Prove that the following inequality holds:

            \[ \int_{0}^{1} (f'(x))^{2}dx\geq 5(3\int_{0}^{1} f(x)dx-8\int_{0}^{1} xf(x)dx+f(1))^{2}.  \]

[/color]

Indeed, very interesting. Unfortunately, just as usual: 2 integrations par parts and Cauchy-Schwarz. When are you going to change the ideas, Cezar?  :P


Give the name  of the following surfaces.

(a) (y − 1)^2 = x
(b) 2x^2 + y^2 = 1
(c) y = x^2 + z^2
(d) 5x^2 + z^2 = y^2 − 1

I know, I know! The name is [url=http://en.wikipedia.org/wiki/Quadric]quadric surfaces[/url].


function
calculus
integration
real analysis
calculus computations

is it possible to integrate a function like
f(x)=x for rational x and 0 for irrational x?

Not with the Riemann integral.
But its [url=http://en.wikipedia.org/wiki/Lebesgue_integration]Lebesgue integral[/url] exists (and is equal to zero).

A function which is Riemann-integrable must be continuous at a dense set of points; actually, the set of discontinuities must have Lebesgue measure zero. For a reasonably elementary proof, see [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?&t=37648]here[/url].


symmetry
number theory solved
number theory

Determine positive integers $m,n$ such that $m^2+mn+n^2$ is square.

Firstly we notice that if the pair $(m,n)$ satisfies the condition that $m^2 + mn + n^2$ is a perfect square, then so does the pair $(am, an) \ \forall a \in \mathbb{Z}^+$, keeping in mind that we are looking for positive integer solutions. Thus we can assume that $\gcd (m,n) = 1$.

Now, obviously ${(m+n)}^2 = m^2 + 2mn + n^2 > m^2 + mn + n^2 \ \forall m,n >0$, thus we can let $m^2 + mn + n^2 = {(m+n-k)}^2$ for some $k \in \mathbb{Z}^+$. Expanding out, we get the equality $mn - 2km - 2kn + k^2 = 0$, which is equivalent to $(m-2k)(n-2k) = 3k^2$.

From our original assumption that $\gcd (m, n) = 1$, we have $\gcd (m-2k, n-2k) = 1$, thus $\exists \ q_1 \in \mathbb{Z}^+ , q_1 \mid k$, such that letting $q_2 = \frac{k}{q_1}$, we have $\gcd(q_1, q_2) = 1$, satisfying the condition that either $3{q_1}^2 \mid m-2k, {q_2}^2 \mid n-2k$ or ${q_1}^2 \mid m-2k, 3{q_2}^2 \mid n-2k$. By symmetry of $m, n$, we can assume WLOG that $3{q_1}^2 \mid m-2k, {q_2}^2 \mid n-2k$.

Note that we can say even further more, that $\mid m-2k \mid = 3{q_1}^2$, and $\mid n-2k \mid = {q_2}^2$, thus we have either $m = 2k + 3{q_1}^2, n = 2k + {q_2}^2$ or $m = 2k - 3{q_1}^2, n = 2k - {q_2}^2$. This is equivalent to $m = q_1 (2q_2 \pm 3q_1), n = q_2 (2q_1 \pm q_2)$.

Finally, dropping the condition that $m, n$ must be coprime, we thus have the final solution of the form $m = d q_1 (2q_2 \pm 3q_1), n = d q_2 (2q_1 \pm q_2)$, where $d, q_1, q_2 \in \mathbb{Z}^+, \gcd (q_1, q_2) = 1$, with the additional checking to be done that $m, n$ are positive in the case of $m = d q_1 (2q_2 - 3q_1), n = d q_2 (2q_1 - q_2)$. Indeed, checking back into the expression $m^2 + mn + n^2$, we have $m^2 + mn + n^2 = {d^2 (3q_1^2 \pm 3q_1q_2 + q_2^2)}^2$, which is a perfect square. Computing, some of the first few solutions are $(3, 5), (5, 16), (7, 8), (7, 33), (11, 24), \ldots$

[quote]From our original assumption that \gcd (m, n) = 1, we have \gcd (m-2k, n-2k) = 1[/quote]

it's not true, take n=5, m=8, k=1.
can you make it right?


Couldn't understand the solution for AIME II, 2003, #12 and #13.  I'd really really appreciate a step by step and carefully written solution.

12. The members of a distinguished committee were choosing a president, and each member gave one vote to one of the 27 candidates.  For each candidate, the exact precentage of votes the candidate got was smaller by at least 1 than the number of votes for that candidate.  What is the smallest possible number of members in the committee?

13. A bug starts at a vertex of an equilateral triangle.  On each move, it randomly selects one of the two vertices where it is not currently located, and crawls along a side of the triangle to that vertex.  Given that the probability that the bug moves to its starting vertex on its tenth move is m/n, where m and n are relatively positive integers, find m+n.

I have some headway on #12, it seems, but #13 is completely mindboggling.
Thanks a lot.

[hide="3"]
Place the bug and the triangle on the complex plane with the vertices as the third roots of unity and $ 1$, i.e. $ 1$, $ \omega$, and $ \omega^{2}$ where $ w^{3}=1$ is not purely real.

Then, the probability will be the coefficient on $ 1$, when powers are reduced as far as possible, in the expansion of:
\[ \left( \omega+\frac{1}{\omega}\right)^{10}\]
divided by $ 2^{10}$, as each time we multiply a complex number by $ \omega$ it is rotated around the complex plane $ 120^\circ$ in the counterclockwise direction (by DeMoivre's Theorem), and similarly dividing by $ \omega$ rotates in the clockwise direction. (Why?)

 This is equal to:
\[ \frac{ \binom{10}{2}+\binom{10}{5}+\binom{10}{8}}{2^{10}}= \frac{171}{512}\implies m+n= \boxed{683}\]
[/hide]


assume that $G=(V,E)$ is a connected graph with minimum degree $\delta$ prove that if $|V|>2\delta$ then $G$ contains a path with length at least $2\delta$ :?:

take the longest path, if it's shorter than $2d$ then this path is a cycle, since it is a cycle any vertex cannot be adjacent to any vertex which is not in that cycle, so this graph cannot be connected

yeah correct your solution is the same as mine...
any other solutions?? :?:


geometry
inradius
incenter
circumcircle
geometric transformation
reflection
Euler

Given a triangle $ ABC$ with an interior point $ P$ in it, suppose the distances from $ P$ to $ BC,CA, AB$ are $ p,q,r$ respectively.
Also, suppose that $ pqr\ge R^3$ where $ R$ is the inradius of triangle $ ABC$.
Prove that the point $ P$ lies inside or on the circle with centre $ S$ and radius $ SI$ where $ I$ is the incenter and $ S$ circumcenter of triangle $ ABC$.

This problem was posted on Mathematical reflections with the solution. As soon as I get the link I post it. The clue to solve this problem is using the Euler pedal theorem plus some AM-GM inequalities


I've studied Diophantine Equations in two variables, but I have not found any resources for those in three or more variables.  Consider, for example, the equation $ ax\plus{}by\plus{}cz\equal{}n$, where $ a$, $ b$, $ c$, and $ n$ are positive integers and $ x$, $ y$, and $ z$ are the variables, also constrained to be positive integers.

Perhaps what I am most interested in is a way to count the number of nonnegative solutions to an equation like this.  For an equation like the above where $ a$, $ b$, and $ c$ are $ 1$, we can use balls and urns, but I don't know what to do otherwise.  A method for counting solutions would come in handy on coin problems; for example, counting the number of ways to make change for a dollar using pennies, nickels, and dimes would be equivalent to counting the solutions to $ x\plus{}5y\plus{}10z$ for integers $ x$, $ y$, and $ z$.  Any suggestions?

$ ax\plus{}by\plus{}cz\equal{}n$ defines a plane in 3-space with normal vector $ <a,b,c>$. The number of solutions is, of course, the number of lattice points in quadrant 1 on the plane.

A quick Googling found [url=http://adsabs.harvard.edu/abs/2008arXiv0805.1702Z]this[/url].

If you're familiar with the generating functions approach to the balls-and-urns problem, the corresponding generating function for pennies, nickels, and dimes is
$ \frac {1}{(1 \minus{} x)(1 \minus{} x^5)(1 \minus{} x^{10})} \equal{} s_0 \plus{} s_1 x \plus{} ...$

where $ s_n$ is the number of ways to make change for $ n$ cents.  In theory, it is possible to solve this problem by finding the partial fraction decomposition of the LHS, and the answer is some sum of exponentials with polynomial coefficients involving the fifth and tenth roots of unity.

Note that this is very different from asking the same question about integers alone; compare the [url=http://en.wikipedia.org/wiki/Coin_problem]coin problem[/url] with [url=http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity]Bezout's identity[/url].  Without the positive restriction, the three-variable problem reduces to the two-variable problem.  The difficulty of this problem is not in the number of variables, but in the positivity restriction.


geometry
rotation
integration
calculus
calculus computations

I know this problem is very easy for all of you but I would like to know the answer:

The line segment connecting the point (1,2) to (5,5) is rotated around the line x= -3.
Find the surface area of the resulting solid.

anyone?

I just want the answer... it doesnt matter if you dont want to post the solution

that does not have a finite surface area, you need to have more restrictions because the line continues on forever, making it infinite surface area, but if you do give other restrictions, one thing that will help would be moving everything up 3 units, so you would rotate about the y-axis

No, it has finite area. qweretyq's problem did say the line segment, not the line.

Let's find an equation for that line segment: $-3x+4y=5,$ or $x=\frac{4y-5}3$ for $2\le y\le 5.$

Take an infinitesimal piece of this segment. Its length is $ds=\sqrt{dx^2+dy^2}=\sqrt{1+\left(\frac{dx}{dy}\right)^2}\,dy= \sqrt{1+\left(\frac43\right)^2}=\frac53\,dy.$ When you rotate it around the line $x=-3,$ it forms a slanted ribbon whose length is the circumference of a circle, $2\pi(x+3),$ and whose width is $ds.$

Area = $\int2\pi(x+3)ds=\int_2^52\pi\left(\frac53\right)\left(\frac{4y-5}3+3\right)dy =\frac{700\pi}9.$

The rotated object is a portion of a cone. The cone's vertex lies on the $(x,y)$ plane at the point $(-3,-1).$


calculus
integration
calculus computations

Let $a<b$ amd $f: [a,b]\rightarrow R$ be a bounded function. Suppose that for all $\epsilon > 0$ there is a $\delta >0$such that if $P$ and $Q$ are partitions of $[a,b]$ with $\| P \|<\delta$ and $\| Q \| <\delta$ then $| R(f,P)- R(f,Q) | <\epsilon$ for any Riemann sums $R(f,P)$ and $R(f,Q)$ of $f$ with respect to the partitions $P$ and $Q$. ( the two Riemann sums do not ncecssarily involve the same sample points)

Show that $f$ is integrable

Note that most of this is the same as the definition of integrability. Mimic the proof that a Cauchy sequence of real numbers is convergent (or use the fact to produce a candidate integral $I$).

Could you explain in detail? Please help. Thx alot.


modular arithmetic
number theory
least common multiple

If $ n$ is any whole number, $ n^2(n^2 \minus{} 1)$ is always divisible by

$ \textbf{(A)}\ 12 \qquad\textbf{(B)}\ 24 \qquad\textbf{(C)}\ \text{any multiple of }12 \qquad\textbf{(D)}\ 12 \minus{} n \qquad\textbf{(E)}\ 12\text{ and }24$

Is $ 0$ divisible by $ 12$?
What happens if $ n\equal{}1$?
What is AHSME, and why do these problems look so easy?

[hide="Solution"]

[b](A)[/b].

Consider the case where $ n \equal{} 2$.

$ 2^2(2^2 \minus{} 1) \equal{} 12$, which clearly eliminates choices [b]B-E[/b].
[/hide]

Here's more information on the [url=http://www.artofproblemsolving.com/Wiki/index.php/AHSME]AHSME[/url].

I understood that the hidden solution would be the official solution, and I might have checked that answer if I was taking the test and had something to gain by doing so.
However, I do not like any of the choices because when $ n\equal{}\minus{}1$, or $ n\equal{}0$, or $ n\equal{}1$,  $ n^2(n^2 \minus{} 1)\equal{}0$, and I have never called $ 0$ a multiple of anything.
If $ 0$ can be called a multiple of any natural number, I would have to agree with the official solution.
If $ 0$ cannot be called a multiple of any natural number, the expression may sometimes be divisible by that one answer, but is not always divisible by any of the choices. So it all hinges on what the meaning of the word "is" is (or rather on what the meaning of the word "divisible" is).

By definition, $ n|0$ for all $ n\in\mathbb{R}$.
We can claim this because $ 0\equiv 0\pmod{n}$ for any $ n$. By definition, $ n|k\iff k\equiv 0\pmod n$.

[hide="My Solution"]
We have $ n^2(n^2 \minus{} 1) \equal{} n\cdot (n \minus{} 1)n(n \plus{} 1)$. Clearly, this quantity is divisible by $ 3$ and $ 2$ because there are 3 consecutive integers. Also, if $ n$ is even, then the whole quantity is divisible by $ 4$. If $ n$ is odd, then the whole quantity will still be divisible by $ 4$. We have covered all the cases so $ n^2(n^2 \minus{} 1)$ is therefore divisible by $ \mathrm{lcm}{(2,3,4)} \equal{} \boxed{12 \text{(A)}}$.
[/hide]

factor n(n)(n+1)(n-1). if n is odd then due to n+1 and n-1 it is automatically divisble by 8. when n is even then it is divisile by 4. So we already have it being divisible by 4. but since there is n(n+1)(n-1) 3 consecutive numbers then it is divisible by 3. So hence it is divisible by A)12

This is a reply to a months-old discussion, but the formal definition of divisibility is "$ a \mid b$ if and only if there exists a $ c$ such that $ ac \equal{} b$." (not mods, that's reversed; mods are defined by divisibility) Here if $ b \equal{} 0$, then $ c \equal{} 0$ for any $ a$ works, so we say everything divides $ 0$. The definition of divisibility is not something in dispute, by the way.


Hi everybody, I'm an 8th grade, I'm doing in my math class good so far. I got for my first marking period A+ and for second one, its comming probably A+ too. I'm little bit worried about my high school math, I looked in those problems  under high school math they look scary. Maybe most of you guys been like that?Is it easy to learn high level math? Took you more time and research to figure out problems? and how you did in 8th grade, and high school math?Thanks

Sorry for my bad English, I'm new in country so....

I've moved this thread to this forum, where it will hopefully get more replies.

Needless to say, nice job on your math results so far!

My two cents:

(1) Pretty much everything looks scary until you learn how to do it.  For a baby, standing on two feet and walking is pretty scary, and babies bump their heads a lot, but eventually they learn to walk.  The first time I drove a car, it was terrifying.  Then, after a few times, it became the coolest thing ever.  (Now I live in Southern California, so it's terrifying again, for a different reason.)

(2) Most things worth doing aren't easy.  That's why they're worth doing.

I suspect that if you're getting A+'s in 8th grade math at your school, that you will continue to do excellent in your school classes.  For very good students (like yourself), the type of math taught in most schools is pretty easy.  It's the type of math -- and problem solving! -- that we do on this site that's hard.  See (2) above.

[quote="might"]I'm little bit worried about my high school math, I looked in those problems  under high school math they look scary. Maybe most of you guys been like that?Is it easy to learn high level math? Took you more time and research to figure out problems? and how you did in 8th grade, and high school math?Thanks[/quote]

While DPatrick's points still stand, please note that the problems in the high school section of AoPS are *nothing* like what you'll be doing in a normal high school. AoPS is for interested, bright students. High school is not. So relax, if you enjoy math, it'll all come together for you :)

well, I'm kind of thinking I wanna become a computer engineer, so I would need take I think calculus or trignomerty or something like that for it.

You will do trigonometry, eventually. You will do calculus, eventually. There's no need to be worrying about them in 8th grade.

Calculus is normally done in the last year of high school or the first year of college, for a student interested in math/science/engineering.

If you are interested in learning mathematics, in really learning it than I would recommend taking the hardest math classes your school has to offer.  But, also get involved in extracurricular activies related to different types of math, Summer programs are probably your best bet.

Don't fall into the trap of thinking that high school math is all you will need (as I did and am now regretting).


[quote="chien than"]Let $ a;b;c;d$ be positive real numbers.Prove that :

$ (\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{d})(\frac{1}{1+a}+\frac{1}{1+b}+\frac{1}{1+c}+\frac{1}{d}) \geq \frac{16}{1+abcd}$[/quote]
Maybe $ \left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{d}\right)\left(\frac{1}{1+a}+\frac{1}{1+b}+\frac{1}{1+c}+\frac{1}{1+d}\right) \geq \frac{16}{1+abcd}$ $ ?$
If so, try $ a=b=c=d=0.8.$ :wink:


Amy wants to design a rectangular prism with a volume of 32 cubic units such that one edge is twice as long as another and each dimension is an integer. How many unique prisms could she make?

We have sides x, 2x, and y. So then 2*x^2*y=32.
x^2*y =16
Then we have ordered pairs (1,16),(2,4), and (4,1) for a total of 3 prisms.


What is the digit in the thousandths place of the decimal
equivalent of $ \frac{3}{16}$?

What is there to say? Dividing reveals the thousands digit as $ \boxed{7}$.


What is the sum of the solutions to $ (y \plus{} 2)^2 \equal{} 25$?

If $ (y \plus{} 2)^2 \equal{} 25$, then y+2=5 or -5. These possibilities give 3 and -7 for y, so the answer is 3+(-7)=-4.


abstract algebra
group theory
invariant
superior algebra
superior algebra unsolved

Let $ G$ be a finite abelian group and $ x$ is an element of maximal order.Let $ H$ be a maximal subgroup of $ G$ such that $ H \cap  \langle x\rangle\equal{}\{0\}$(which means if $ K$,such that $ H<K<G$ and $ K \cap  \langle x\rangle\equal{}\{0\}$,then $ K\equal{}H$),Prove $ G\equal{}\langle x\rangle \oplus  H$.

Neat problem.

You need to show two things: that $ G \equal{} \langle x\rangle\plus{} H$, and that the sum is direct.  The latter is immediate from the definition once we've proved the first.

Taking the quotient by $ H$, we may assume without loss of generality that $ H\equal{}0$. ($ x$'s order does not decrease, so the conditions of the problem are maintained)

The problem becomes: If $ x$ has maximal order and every nontrivial subgroup intersects $ \langle x\rangle$ nontrivially, then $ G\equal{}\langle x\rangle$.

This is almost immediate from the [url=http://en.wikipedia.org/wiki/Finitely_generated_abelian_group#Invariant_factor_decomposition]invariant factor decomposition[/url] of $ G$.  There is probably a more elementary way to see it, but it is eluding me at the moment.

Nice indeed.
[quote="LydianRain"]If $ x$ has maximal order and every nontrivial subgroup intersects $ \langle x\rangle$ nontrivially, then $ G \equal{} \langle x\rangle$.[/quote]
By splitting $ G$ and $ \langle x\rangle$ into the direct products of its Sylow subgroups, we can assume $ G$ is a $ p$-group for some prime $ p$.
For $ y\in G\setminus \langle x\rangle$ of minimal order we have $ y^p\in \langle x\rangle$, i.e. $ y^p\equal{}x^n$ for some $ n\in\mathbb{Z}$.
Then for $ p\nmid n$ we get $ \langle x\rangle\equal{}\langle x^n\rangle\equal{}\langle y^p\rangle\lneq \langle y\rangle$, which contradicts $ x\in G$ of maximal order.
So $ p\mid n$ and $ z: \equal{}yx^{\minus{}n/p}\in G\setminus \langle x\rangle$ satisfies $ z^p\equal{}1$ and $ \langle x\rangle\cap \langle z\rangle\equal{}1$.
Contradiction!

Thank you,but I think it is better to use olorin's way to prove the lemma,because we can use this theorem to prove the decomposition theorem of finite abelian groups.

No, my proof uses LydianRain's idea to factor out $ H$.
I was struggling too, so this is joined work.


For each $ n \in \omega$, let $ X_n$ be the set $ \{0, 1\}$, and let $ \tau_n$ be the discrete topology on $ X_n$. For each of the following subsets of $ \prod_{n \in \omega} X_n$, say whether it is open or closed (or neither or both) in the product topology.

(a) $ \{f \in \prod_{n \in \omega} X_n | f(10)\equal{}0 \}$
(b) $ \{f \in \prod_{n \in \omega} X_n | \text{  }\exists n \in \omega \text{  }f(n)\equal{}0 \}$
(c) $ \{f \in \prod_{n \in \omega} X_n | \text{  }\forall n \in \omega \text{  }f(n)\equal{}0 \Rightarrow f(n\plus{}1)\equal{}1 \}$
(d) $ \{f \in \prod_{n \in \omega} X_n | \text{  }|\{ n \in \omega | f(n)\equal{}0 \}|\equal{}5 \}$
(e)$ \{f \in \prod_{n \in \omega} X_n | \text{  }|\{ n \in \omega | f(n)\equal{}0 \}|\leq5 \}$

So remember that open sets in the infinite product topology is really just having all but finitely many the whole space and the rest are open. Since the individual factors are discrete, you only need to check that all but finitely many are the whole space.

e.g. in (a) the 10th coordinate has a specific value, but all other coordinates can be whatever, so this is certain open.

Thanks for your help, I am starting to understand this problem more.  Do you have any ideas on the other parts?  I am still struggling with this problem.

Recall that $ \omega\equal{}\mathbb{N} \cup \{ 0 \}$

[b]Progress:[/b]

Take set (b). Let $ B \equal{} \{f \in \prod_{n \in \omega} X_n | \;\exists n \in \omega \; f(n) \equal{} 0 \}$. If $ f\in B$ then there exists m such that f(m)=0. Then the set $ \{g \in \prod_{n \in \omega} X_n |\; g(m) \equal{} 0\}$ is an open neighbourhood of f contained in B. [b]Therefore B is open.
[/b]
It's usually more difficult to check when a set is closed. You have to look at its complement and decide whether that is open. Sometimes this is straightforward. For example, the complement of set (a) is the set of all f such that f(10)=1. [b]That is open, so set (a) is closed as well as open.[/b]

For a slightly less easy example, look at set (c). Let $ C \equal{} \{f \in \prod_{n \in \omega} X_n | \text{ }\forall n \in \omega \text{ }f(n) \equal{} 0 \Rightarrow f(n \plus{} 1) \equal{} 1 \}$. If $ f\notin C$ then there exists m such that f(m)=f(m+1)=0. Then $ \{g \in \prod_{n \in \omega} X_n |\; g(m) \equal{} g(m \plus{} 1) \equal{} 0\}$ is an open neighbourhood of f containing no points of C. [b]Therefore the complement of C is open and so C is closed.[/b]
[b]
[color=red]I still do not know how to do parts (d.) and (e.)[/b][/color]


A group of 20 students, including 3 particular girls and 4 particular boys are to be lined up in two rows with 10 students each. In how many ways can this be done if the 3 particular girls must be in the front row while the 4 particular boys be in the back?


search
inequalities unsolved
inequalities

Let $ ABC$ is a triangle. Prove that: $ \boxed{p\le2R \plus{} (3\sqrt {3} \minus{} 4)r}$

See also here:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=207461


function
number theory open
number theory

[quote="bboypa"]Fixed a positive integer $ t > 0$, define $ a_0$ and $ a_1$ two positive integers each of the form $ 2p$, where $ p$ is a arbitrary prime much and much greater of $ t$.

Now consider the recurrence $ a_{n \plus{} 2} \equal{} \frac {a_{n \plus{} 1} \plus{} a_n}{2} \plus{} 2t$ forall $ n \in \mathbb{N}$.

There exist a index $ i$ (explicit or in function of t) such that $ a_j$ is not a integer of the form $ 2p$, for some $ 2 \le j \le i$?

[size=75](Ask me if the question is not clear)[/size][/quote]
We have $ a_{n\plus{}2}\minus{}a_{n\plus{}1}\equal{}2t\minus{}\frac{a_{n\plus{}1}\minus{}a_n}{2}$

And so $ a_{n\plus{}2}\minus{}a_{n\plus{}1}\equal{}t\plus{}\frac{a_{n}\minus{}a_{n\minus{}1}}{4}$

And so $ a_{2k\plus{}1}\minus{}a_{2k}\equal{}t\plus{}\frac{t}{4}\plus{}\frac{t}{4^2}\plus{}$...$ \plus{}\frac{t}{4^{k\minus{}1}}\plus{}\frac{a_1\minus{}a_0}{4^{k}}$

$ a_{2k\plus{}1}\minus{}a_{2k}\equal{}\frac{4t}{3}(1\minus{}\frac{1}{4^k})\plus{}\frac{a_1\minus{}a_0}{4^k}$

And obviously, there exist an index $ k$ such that RHS is not an integer.


linear algebra
matrix
algebra
polynomial
linear algebra unsolved

Solve the equation

$X^{2006}=\left(\begin{array}{cc} 9&3\\\ 15&5\end{array}\right)$

 :)

[quote="alekk"]it is the caracteristic polynomial. But if you don't know caracteristic polynomial theory, you can check this out : this is just calculations ..[/quote]

Oh,yeah.
I finally unterstood this. It was an easy one..... :D

Actually, Socrates one can easily solve the following general equation:

                            \[ X^{2}=A, \]
 where $X\in M_{2}(\mathbb{C})$ and $det A=0$. :)  ;)


Compute the determinant:

$ \triangle_n\equal{} \left| \begin{array}{ccccc}
1 & a_1 & a_2 & \dots & a_{n\minus{}1} \\
1 & \minus{} \frac{1}{a_1} & 0 & \dots & 0\\
1 & 0 & \minus{}\frac{1}{a_2} & \dots & 0 \\
\dots & \dots & \dots & \dots & \dots \\
1 & 0 & 0 & \dots & \minus{} \frac{1}{a_{n\minus{}1}} \end{array}  \right|$ , where $ a_1,a_2, \dots a_{n\minus{}1} \in \mathbb{C}^*$.


geometry
trigonometry
area of a triangle

Find the largest possible area of a triangle that has two sides of lengths 30 and 40.

The triangle with the major area is the right and he area is 600

Hey, uh...could you elaborate on why the right triangle always has the most area?

The area of a triangle can be determined by two sides and their included angle, and is equal to $ \frac{1}{2} ab \sin \theta$. Since we know $ a$ and $ b$, we would like to maximize $ \sin \theta$, which is done by letting $ \theta \equal{} \frac{\pi}{2}$.


analytic geometry
USAMTS
search
inequalities
geometry
Gauss

How hard did you think round 1 was in comparison to round 1 of Year 19.

I personally think that this year's was harder than last year's but not by much. first of all, last year, in 8th grade, i got a 19, and now, since i have gotten better, and i am able to solve one of the problems that i got a 1 on last year, i could probly get a 23 or 24 maybe 25. on this year's test, #1 was very tricky and required alot of precise casework, which is not good for a #1. So this year, i see myself struggling to get a 21 or 22....

I found them sort of the same dificulty...

However, I think that this round was easier to make a stupid mistake on.

I thought this year was easier, I could solve all of them, but perhaps I just put in more time this year.

I've never done this contest before, but I looked at a few past rounds before (not first rounds in particular), and this round was easier than I expected.  Just now I looked at the round 1 / year 19 problems, and the last one seems kind of hard.  Then again, it would probably be possible to brute-force it with coordinates.

Hmm... solutions.tex > Properties > Modified: Tuesday, August 05, 2008. I'm weird.

I suppose the questions were a bit trickier, though I didn't find them as difficult as before (or there's the unlikely possibility that I might have improved..).

I find these problems are getting too bashable: 1 (CASEWORK) 4 (COORDINATES) 2 and 3 were pretty easy (unless I messed up... ugh) In my opinion, 5 was the only nice problem. Although it did get a little bit bashy with the algebra, I actually like the problem.

Anyway, I also think that the non-bashable problems are getting harder...

Maybe it's just me, but I thought the problems were a bit too easy. Like last year, I couldn't solve a single problem, but this year, I looked at the problems and was like...yeah, too simple.  Then again, I was reeeeeeeeeeeeaaaaaaaaaaaaaaaaaalllllllllllllllly stupid last year, but then again, I might still be this year.

its proabbly because you're smarter this year....

i looked at both years probs and their all hard :D

I think I partially screwed up #1, kinda did good on #2, totally messed up #3 and #4, and did well on #5.
Meh. Epoch Phail... :(

If this year is easy, I don't know how I'm gonna survive next year...  :P

I think this year's USAMTS was hard. Pretty hard, compared to older ones.
So i guess they'd just be getting harder and harder as the years go by...

I think this round was harder, but it could just have been me being stupid (especially on 2 and 5).  #2... I tried to use $ lcm(x,y,z)|x \plus{} y \plus{} z \minus{} 1$ and got stuck from there.  After a while of getting nowhere, I tried to write a program to search for solutions based on this, and this gave me nothing because I messed up the order of operations in the program...

#5, I started with the same idea as the official, but I tried to flat out expand for the $ r$ odd case, rearrange into two square roots, and show the numbers we were square-rooting had a difference of 1.  After pages of work, I just got stuck.  epic failure, hoping for a 3.

[i]Don't discuss the current round!! -- Admin[/i]

Hey, I did the exact same epic failure for that number five too! I had the same idea of splitting into odd and even, and epically failed the odd case by expanding!

 :ninja:

I think this year's first round was harder but the problems were not as well developed. If you know what I mean..

the problems in general were easier, but #1 on this year's test was like WHAT? i missed it i was off by 1, so that kinda stinx. oh well. so yeah, they should kinda cut down on the bashing problems.

I think this year was much easier.
Last year, I looked at the problems, stared at them for like another hour, and all I was thinking was Say Whaaat?
And then chickened out after a couple days.
But this year I solved 1,2,4,and 5. 3 turned into an inequality bash for me that didn't get anywhere.

last year #1 < this year #1
last year #2 > this year #2
last year #3 < this year #3
last year #4 < this year #4 ( i like 2-d geometry more than 3-d geometry)
last year #5 < this year #5

so yeah..... this is my opinion.....

really?

I found that

this year #1 < last year #1.

Actually, it is pretty hard to mess up #1 with Burnside's Lemma actually.

I made several mistakes but whenever I made a mistake, my answer was not an integer. So I knew I had made a mistake.

how exactly do you use burnside's lemma anyway?  I don't quite get what your are supposed to count...

So I missed number 1 (got 23) by stupidly overcounting.  :-<

As for #2, last year's was easier.  by far.  The angles you could find from the diagram easily, and the rest was playing with the angles.

#1 this year... idk.  I think its not quite comparable to #1 round 1 last year, but some of the other rounds had similar problems.  But I'd rate it a bit harder than most geometric counting problems, but it can still be done by casework.

#2 - so i tried to use $ lcm(x,y,z)|x\plus{}y\plus{}z\minus{}1$.  found a few useless facts, overall got nowhere, and then tried writing a program to find the answers.  But i Phailed that too... just figured out I messed up stinking order of operations there.  I just thought there were no solutions.

overall :\

[quote="facis"]how exactly

So I missed number 1 (got 23) by stupidly overcounting.  :-<

[/quote]

i'm with you.... :(

I don't think #1 is hard as long as you count your casework carefully and avoid stupid mistakes.

wow we're still talking about round 1?

gauss are you done with round 2??

EDIT: hey 1181 posts

yes, it's not like we can talk about any other rounds...*cough*


integration
limit
logarithms
calculus
real analysis
real analysis unsolved

a question i asked in class yesterday...   :D  took nearly 30 mins to get it done completely... students got both confused and excited at the same time...

we already know from riemann,
$ \int_a^b\;f(x)\;dx\;\equal{}\;\lim_{n\to\infty}\left\{\left(\dfrac{b\minus{}a}{n}\right)\sum_{m\equal{}1}^n\;f\left(a\plus{}\dfrac{m(b\minus{}a)}{n}\right)\right\}$

now show
$ \int_a^b\;f(x)\;dx\;\equal{}\;\sum_{n\equal{}1}^\infty\;\sum_{m\equal{}1}^{2^n\minus{}1}\;\left\{(\minus{}1)^{m\plus{}1}\cdot\left(\dfrac{b\minus{}a}{2^n}\right)\cdot\,f\left(a\plus{}\dfrac{m(b\minus{}a)}{2^n}\right)\right\}$

and hence show for $ 0\leq p<\infty$,

$ \sum_{n\equal{}1}^\infty\;\sum_{m\equal{}1}^{2^n\minus{}1}\;\dfrac{(\minus{}1)^{m\plus{}1}}{2^n}\;\left(\ln\,\left(\dfrac{2^n}{m}\right)\right)^p\;\equal{}\;\int_0^1\;\left(\ln\,\left(\frac{1}{x}\right)\right)^p\;dx\;\equal{}\;\boxed{p!}$

apparently, this double series summing to $ p!$ was known to archimedes using this method ! what a genius !! :o

[quote="Field"][quote="misan"]
we already know from riemann,
$ \int_a^b\;f(x)\;dx\; \equal{} \;\lim_{n\to\infty}\left\{\left(\dfrac{b \minus{} a}{n}\right)\sum_{m \equal{} 1}^n\;f\left(a \plus{} \dfrac{m(b \minus{} a)}{n}\right)\right\}$[/quote]
How do you prove this?[/quote]

Well, when we know that the integral exists, it's obvious, since the RHS is just a sequence of Riemann sums.  But the limit can exist even though the integral doesn't, so I wouldn't call it "true" exactly.


inequalities
linear algebra
matrix
complex numbers
linear algebra unsolved

Let $ A,B \in M_n{(\mathbb{C})}$ and $ I$ is $ n^2$x$ n^2$ identity matrix.
Prove inequality Kronecker product Matrix :
  1)$ \det(A\otimes{\overline{A}} \plus{} I) \geq 0$
  2)If $ AB \equal{} BA$   then  $ \det(A\otimes{\overline{A}} \plus{} B\otimes{\overline{B}}) \geq 0$
  Here $ \overline{A}$ is the conjugate matrix of $ A$
[hide="Answer of me"]Implies but Very interesting[/hide] :P

[hide="Solution 1)"]Let $ \lambda_1,\lambda_2,...,\lambda_n$ are eigenvalues of $ A$ matrix we can similar ,are real  or complex numbers .
       $ \beta_1,\beta_2,...,\beta_n$ are eigenvalues of $ B$ matrix we can similar ,are real  or complex numbers
 The exist $ T \in GL_n{(\mathbb{C})}$ Such that :
          $ A = T\begin{pmatrix}\lambda_1 & * & * & * & * & * & * \\
0 & \lambda_2 & * & * & * & * & * \\
0 & 0 & \lambda_3 & * & * & * & * \\
... & ... & .... & ... & ... & ... & ... \\
0 & 0 & 0 & ... & ... & ... & \lambda_n\end{pmatrix}T^{ - 1}$
Put $ T_A = \begin{pmatrix}\lambda_1 & * & * & * & * & * & * \\
0 & \lambda_2 & * & * & * & * & * \\
0 & 0 & \lambda_3 & * & * & * & * \\
... & ... & .... & ... & ... & ... & ... \\
0 & 0 & 0 & ... & ... & ... & \lambda_n\end{pmatrix}$
Then $ A = TT_AT^{ - 1}$
Use $ \forall X,Y \in M_n{(\mathbb{C})}$ then $ \overline{XY} = (\overline{X})(\overline{Y})$ We have
 $ \overline{A} = (\overline{T})(\overline{T_A})(\overline{T})^{ - 1}$
We have $ A\otimes{\overline{A}} = (TT_AT^{ - 1})\otimes{((\overline{T})(\overline{T_A})(\overline{T})^{ - 1})} = (T\otimes{\overline{T}})(T_A\otimes{\overline{T_A}})(T^{ - 1}\otimes{(\overline{T})^{ - 1}}) = (T\otimes{\overline{T}})(T_A\otimes{\overline{T_A}})(T\otimes{\overline{T}})^{ - 1}$
Then we have :
 $ \det(A\otimes{\overline{A}} + I) = \det(T_A\otimes{\overline{T_A}} + I) = \det\begin{pmatrix}\lambda_1\overline{T_A} + I_n & * & * & * & * & * & * \\
0 & \lambda_2\overline{T_A} + I_n & * & * & * & * & * \\
0 & 0 & \lambda_3\overline{T_A} + I_n & * & * & * & * \\
... & ... & .... & ... & ... & ... & ... \\
0 & 0 & 0 & ... & ... & ... & \lambda_n\overline{T_A} + I_n\end{pmatrix} = \prod_{i = 1}^{n}{(\lambda_i\overline{T_A} + I_n)} = \prod_{i = 1}^{n}{(|\lambda_i|^2 + 1)}\prod_{1\leq i < j \leq n}{(\lambda_i\overline{\lambda_j} + 1)(\lambda_j\overline{\lambda_i} + 1)} = \prod_{i = 1}^{n}{(|\lambda_i|^2 + 1)}\prod_{1\leq i < j\leq n}{|\lambda_i\overline{\lambda_j} + 1|^2}\geq o$[/hide]
[hide="Solution 2)"]$ AB = BA$ Then The exist $ T \in GL_n{(\mathbb{C})}$ Such that :
    $ A = TT_AT^{ - 1},B = TT_BT^{ - 1}$
Here $ T_B = \begin{pmatrix}\beta_1 & * & * & * & * & * & * \\
0 & \beta_2 & * & * & * & * & * \\
0 & 0 & \beta_3 & * & * & * & * \\
... & ... & .... & ... & ... & ... & ... \\
0 & 0 & 0 & ... & ... & ... & \beta_n\end{pmatrix}$
And $ A\otimes{\overline{A}} + B\otimes{\overline{B}} = (T\otimes{\overline{T}})(T_A\otimes{\overline{T_A}} + T_B\otimes{\overline{T_B}})(T\otimes{\overline{T}})^{ - 1}$
Hence
 $ \det(A\otimes{\overline{A}} + B\otimes{\overline{B}}) = \det(T_A\otimes{\overline{T_A}} + T_B\otimes{\overline{T_B}}) ==\prod_{i=1}^{n}{(\lambda_k\overline{T_A}+\beta_k\overline{T_B})}= \prod_{i = 1}^{n}{(|\lambda_i|^2 + |\beta_i|^2)}\prod_{1\leq i < j \leq n}{(\lambda_i\overline{\lambda_j} + \beta_i\overline{\beta_j})(\lambda_j\overline{\lambda_i} + \beta_j\overline{\beta_i})} = \prod_{i = 1}^{n}{(|\lambda_i|^2 + |\beta_i|^2)}\prod_{1\leq i < j \leq n}{|\lambda_i\overline{\lambda_j} + \beta_i\overline{\beta_j}|^2} \geq 0$[/hide]
 Sorry if I wrong  :blush:

2) implies 1)
If $ spectrum(A)\equal{}(\lambda_i)$ then $ spectrum(A\otimes\bar{A})\equal{}(\lambda_i\bar{\lambda_j})_{ij}$.
If $ AB\equal{}BA$ then $ A,B$ are simultaneously triangularizable ; thus $ A\otimes\bar{A},B\otimes\bar{B}$ are simultaneously triangularizable. Then there exists an ordering of $ spectrum(A)\equal{}(\lambda_i)$ and $ spectrum(B)\equal{}(\mu_j)$ such that $ spectrum(A\otimes\bar{A}\plus{}B\otimes\bar{B})\equal{}(\lambda_i\bar{\lambda_j}\plus{}\mu_i\bar{\mu_j})_{ij}$. If $ i\equal{}j$ then these values are non negative ; if $ i\not\equal{}j$ then these values are pairwise conjugate.

I  add inequality as :
$ A,B$ are Hermitian matricies (or $ SP_c(A) \subset R,SP_c(B) \subset R$) $ AB \equal{} BA$ then :
1)$ \det(A\otimes{A} \plus{} I) \geq O$
2)$ \det(A\otimes{A} \plus{} B\otimes{B}) \geq O$
3)$ \det(A\otimes{A} \plus{} B\otimes{B} \plus{} I) \geq O$

Let $ A,B,C \in M_n{\mathbb{(C)}}$ $ AB \equal{} BA,BC \equal{} CB,CA \equal{} AC$ then $ \det(A\otimes{\overline{A}} \plus{} B\otimes{\overline{B}} \plus{} C\otimes{\overline{C}}) \geq 0$
 If $ AB \equal{} BA,BC \equal{} CB,CA \equal{} AC$ Then The exist $ T \in GL_n{(\mathbb{C})}$ Such that :
    $ A \equal{} TT_AT^{ \minus{} 1},B \equal{} TT_BT^{ \minus{} 1},C \equal{} TT_CT^{ \minus{} 1}$
Here $ T_C \equal{} \begin{pmatrix}\phi_1 & * & * & * & * & * & * \\
0 & \phi_2 & * & * & * & * & * \\
0 & 0 & \phi_3 & * & * & * & * \\
... & ... & .... & ... & ... & ... & ... \\
0 & 0 & 0 & ... & ... & ... & \phi_n\end{pmatrix}$
And $ A\otimes{\overline{A}} \plus{} B\otimes{\overline{B}} \plus{} C\otimes{\overline{C}} \equal{} (T\otimes{\overline{T}})(T_A\otimes{\overline{T_A}} \plus{} T_B\otimes{\overline{T_B}} \plus{} T_C\otimes{\overline{T_C}})(T\otimes{\overline{T}})^{ \minus{} 1}$
Hence
 $ \det(A\otimes{\overline{A}} \plus{} B\otimes{\overline{B}} \plus{} C\otimes{\overline{C}}) \equal{} \det(T_A\otimes{\overline{T_A}} \plus{} T_B\otimes{\overline{T_B}} \plus{} T_C\otimes{\overline{T_C}}) \equal{} \equal{} \prod_{i \equal{} 1}^{n}{(\lambda_k\overline{T_A} \plus{} \beta_k\overline{T_B} \plus{} \phi_k\overline{T_C})} \equal{} \prod_{i \equal{} 1}^{n}{(|\lambda_i|^2 \plus{} |\beta_i|^2 \plus{} |\phi_i|^2)}\prod_{1\leq i < j \leq n}{(\lambda_i\overline{\lambda_j} \plus{} \beta_i\overline{\beta_j} \plus{} \phi_i\overline{\phi_j})(\lambda_j\overline{\lambda_i} \plus{} \beta_j\overline{\beta_i} \plus{} \phi_j\overline{\phi_i})} \equal{} \prod_{i \equal{} 1}^{n}{(|\lambda_i|^2 \plus{} |\beta_i|^2 \plus{} |\phi_i|^2)}\prod_{1\leq i < j \leq n}{|\lambda_i\overline{\lambda_j} \plus{} \beta_i\overline{\beta_j} \plus{} \phi_i\overline{\phi_j}|^2} \geq 0$
 case ) Let $ A,B,C \in M_n{\mathbb{(R)}}$ $ AB \equal{} BA,BC \equal{} CB,CA \equal{} AC$ then $ \det(A\otimes{{A}} \plus{} B\otimes{{B}} \plus{} C\otimes{{C}}) \geq 0$
 Generral is correct , I hope that You are complete it ....   :play_ball:  .............

[quote="QuyBac"]
   Let $ A,B,C \in M_n{\mathbb{(R)}}$ $ AB \equal{} BA,BC \equal{} CB,CA \equal{} AC$ then $ \det(A\otimes{{A}} \plus{} B\otimes{{B}} \plus{} C\otimes{{C}}) \geq 0$
 [/quote]
 It is same  :oops:
If $ AB \equal{} BA,BC \equal{} CB,CA \equal{} AC$ Then The exist $ T \in GL_n{(\mathbb{C})}$ Such that :
    $ A \equal{} TT_AT^{ \minus{} 1},B \equal{} TT_BT^{ \minus{} 1},C \equal{} TT_CT^{ \minus{} 1}$ ,note $ \overline{T^{ \minus{} 1}} \equal{} (\overline{T})^{ \minus{} 1}$
Then $ A \equal{} \overline{A} \equal{} (\overline{T})( \overline{T_A})( \overline{T})^{ \minus{} 1}$ ,$ B \equal{} \overline{B} \equal{} (\overline{T})( \overline{T_B})( \overline{T})^{ \minus{} 1}$ ,$ C \equal{} \overline{C} \equal{} (\overline{T})( \overline{T_C})( \overline{T})^{ \minus{} 1}$ .....
  and  $ \det(A\otimes{{A}} \plus{} B\otimes{{B}} \plus{} C\otimes{{C}}) \equal{} \det(A\otimes{\overline{A}} \plus{} B\otimes{\overline{B}} \plus{} C\otimes{\overline{C}}) \geq 0$
Ps: [color=red]If You think single that $ A \in M_n{\mathbb{(R)}}$ , $ \det(A\otimes{A} \plus{} I) \geq 0$[/color] [b]Is very hard [/b] [color=red]If you don't thinks to [/color] $ \det(A\otimes{\overline{A}} \plus{} I)\geq 0$ ???
If you see It is easy , I for example Let $ A \in M_n{\mathbb{(C)}},B \in M_n{\mathbb{(R)}}$ such that  $ AB \equal{} BA$ then $ \det(A\otimes{\overline{A}} \plus{} B\otimes{B}) \geq 0$ It is is very hard If you don't thinks to $ \det(A\otimes{\overline{A}} \plus{} B\otimes{\overline{B}}) \geq 0$..............