Author Topic: TT's Maths Thread (Read 148037 times) Tweet Share

TrueTears · « **Reply #195 on:** November 27, 2009, 01:29:07 am »

Since I'm in a 'rearranging mood' (lolz) looking at $a+b+c \geq \sqrt{ab}+\sqrt{bc}+\sqrt{ac}$

becomes $a-\sqrt{ab}+b-\sqrt{bc}+c-\sqrt{ac} \ge 0$ Which is what we want to prove.

Let $x = a-\sqrt{ab}+b-\sqrt{bc}+c-\sqrt{ac}$

$\implies$ $x=a-\sqrt{ab}+b+b-\sqrt{bc}+c+c-\sqrt{ac}+a-b-c-a$

$x = a-2\sqrt{ab}+b+b-2\sqrt{bc}+c+c-2\sqrt{ac}+a-b-c-a+\sqrt{ab}+\sqrt{bc}+\sqrt{ac}$

$x = (\sqrt{a}-\sqrt{b})^2 + (\sqrt{b}-\sqrt{c})^2 + (\sqrt{c}-\sqrt{a})^2 - \left(a-\sqrt{ab}+b-\sqrt{bc}+c-\sqrt{ac}\right)$

$x = (\sqrt{a}-\sqrt{b})^2 + (\sqrt{b}-\sqrt{c})^2 + (\sqrt{c}-\sqrt{a})^2 - x$

$2x = (\sqrt{a}-\sqrt{b})^2 + (\sqrt{b}-\sqrt{c})^2 + (\sqrt{c}-\sqrt{a})^2$

$x = \frac{(\sqrt{a}-\sqrt{b})^2 + (\sqrt{b}-\sqrt{c})^2 + (\sqrt{c}-\sqrt{a})^2}{2}$

Since $(\sqrt{a}-\sqrt{b})^2 + (\sqrt{b}-\sqrt{c})^2 + (\sqrt{c}-\sqrt{a})^2 \ge 0$ $\implies \frac{(\sqrt{a}-\sqrt{b})^2 + (\sqrt{b}-\sqrt{c})^2 + (\sqrt{c}-\sqrt{a})^2}{2} \ge 0$

$\implies x \ge 0$

$\therefore a-\sqrt{ab}+b-\sqrt{bc}+c-\sqrt{ac} \ge 0$

No need for AM-GM :2funny:

Quote from: Ahmad on November 27, 2009, 01:27:57 am

Suppose the inequality is $f(x,y,z) \ge 0$ then it's homogeneous if $f(x,y,z) = f(kx,ky,kz)$ .

Ah right, thanks!

kamil9876 · « **Reply #196 on:** November 27, 2009, 01:37:23 am »

quite kool TT. I noticed a lot of inequalities can be solved either by making those substituions I tried on an earlier Q, or by using the fact that $\sum_{i=0}^n x_i =0$ iff $x_i=0 \forall 1\leq i \leq n$ . Rather than AM-GM. In fact a proof of AM-GM for the simple case is done using the latter method.

TrueTears · « **Reply #197 on:** November 27, 2009, 02:35:11 am »

Alright very last inequality question. It's a USAMO question so I left it until the end ^.^

Prove that the zeros of $x^5+ax^4+bx^3+cx^2+dx+e = 0$ cannot all be real if $2a^2<5b$

Ahmad · « **Reply #198 on:** November 27, 2009, 01:50:45 pm »

Rather easy for a USAMO question!

/0 · « **Reply #199 on:** November 27, 2009, 04:33:32 pm »

Don't know, but substitute $x = y-\frac{a}{5}$ and the coefficient of the $y^3$ term is $\frac{5b-2a^2}{5}$
Or expanding roots might help

TrueTears · « **Reply #200 on:** November 27, 2009, 05:42:13 pm »

I'm not sure if this is a rigorous proof but it includes a lot of wishful thinking.

Let the $5$ roots of $x^5+ax^4+bx^3+cx^2+dx+e$ be $q,w,r,t,u$ where $q,w,r,t,u \in \mathbb{R}$

$\therefore \mbox{By the fundamental theorem of algebra} \implies x^5+ax^4+bx^3+cx^2+dx+e = (x-q)(x-w)(x-r)(x-t)(x-u)$

Now equating coefficients for $x^4$ and $x^3$ coefficients yields:

$\frac{a_4}{a_5} = (-1)^{5-4}\left(\mbox{Sum of 5-4 different roots}\right)$

$\therefore a_4 = a = -(q+w+r+t+u)$

$\frac{a_3}{a_5} = (-1)^{5-3}\left(\mbox{Sum of 5-3 different roots}\right)$

$\therefore a_3 = b = (qw+qr+qt+qu+wr+wt+wu+rt+ru+tu)$

Now we require $2a^2 - 5b < 0$

Let $y = 2a^2-5b$

$\implies y = 2(q+w+r+t+u)^2 - 5(qw+qr+qt+qu+wr+wt+wu+rt+ru+tu)$

$\mbox{By the fundamental theorem of elementary symmetric polynomials} \implies q^2+w^2+r^2+t^2+u^2 = (q+w+r+t+u)^2 -2(qw+qr+qt+qu+wr+wt+wu+rt+ru+tu)$

$\therefore (q+w+r+t+u)^2 = q^2+w^2+r^2+t^2+u^2 + 2(qw+qr+qt+qu+wr+wt+wu+rt+ru+tu)$

$\implies y = 2(q^2+w^2+r^2+t^2+u^2) + 4(qw+qr+qt+qu+wr+wt+wu+rt+ru+tu)- 5(qw+qr+qt+qu+wr+wt+wu+rt+ru+tu)$

$\implies y = 2(q^2+w^2+r^2+t^2+u^2) -(qw+qr+qt+qu+wr+wt+wu+rt+ru+tu)$

$\implies y = 2q^2+2w^2+2r^2+2t^2+2u^2 -qw-qr-qt-qu-wr-wt-wu-rt-ru-tu$

$\implies y = 2q^2-4qw+2w^2+2q^2-4qr+2r^2+2q^2-4qt+2t^2+2q^2-4qu+2u^2+2w^2-4wr+2r^2+2w^2-4wt+2t^2+2w^2-4wu+2u^2+2r^2-4rt+2t^2+2r^2-4ru+2u^2+2t^2-4tu+2u^2-6(q^2+w^2+r^2+t^2+u^2)+3(qw+qr+qt+qu+wr+wt+wu+rt+ru+tu)$

$\implies y = (\sqrt{2}q-\sqrt{2}w)^2+(\sqrt{2}q-\sqrt{2}r)^2+(\sqrt{2}q-\sqrt{2}t)^2+(\sqrt{2}q-\sqrt{2}u)^2+(\sqrt{2}w-\sqrt{2}r)^2+(\sqrt{2}w-\sqrt{2}t)^2+(\sqrt{2}w-\sqrt{2}u)^2+(\sqrt{2}r-\sqrt{2}t)^2+(\sqrt{2}r-\sqrt{2}u)^2+(\sqrt{2}t-\sqrt{2}u)^2-3y$

$\implies 4y = (\sqrt{2}q-\sqrt{2}w)^2+(\sqrt{2}q-\sqrt{2}r)^2+(\sqrt{2}q-\sqrt{2}t)^2+(\sqrt{2}q-\sqrt{2}u)^2+(\sqrt{2}w-\sqrt{2}r)^2+(\sqrt{2}w-\sqrt{2}t)^2+(\sqrt{2}w-\sqrt{2}u)^2+(\sqrt{2}r-\sqrt{2}t)^2+(\sqrt{2}r-\sqrt{2}u)^2+(\sqrt{2}t-\sqrt{2}u)^2$

$\implies y = \frac{(\sqrt{2}q-\sqrt{2}w)^2+(\sqrt{2}q-\sqrt{2}r)^2+(\sqrt{2}q-\sqrt{2}t)^2+(\sqrt{2}q-\sqrt{2}u)^2+(\sqrt{2}w-\sqrt{2}r)^2+(\sqrt{2}w-\sqrt{2}t)^2+(\sqrt{2}w-\sqrt{2}u)^2+(\sqrt{2}r-\sqrt{2}t)^2+(\sqrt{2}r-\sqrt{2}u)^2+(\sqrt{2}t-\sqrt{2}u)^2}{4}$

But $y = 2a^2-5b < 0$

Thus $\frac{(\sqrt{2}q-\sqrt{2}w)^2+(\sqrt{2}q-\sqrt{2}r)^2+(\sqrt{2}q-\sqrt{2}t)^2+(\sqrt{2}q-\sqrt{2}u)^2+(\sqrt{2}w-\sqrt{2}r)^2+(\sqrt{2}w-\sqrt{2}t)^2+(\sqrt{2}w-\sqrt{2}u)^2+(\sqrt{2}r-\sqrt{2}t)^2+(\sqrt{2}r-\sqrt{2}u)^2+(\sqrt{2}t-\sqrt{2}u)^2}{4} < 0$

However if $q,w,r,t,u \in \mathbb{R}$ it is not possible for $y < 0$

Contradiction!

Thus if $2a^2<5b$ the polynomial $x^5+ax^4+bx^3+cx^2+dx+e$ can not have all real roots.

/0 · « **Reply #201 on:** November 27, 2009, 05:47:45 pm »

lol very nice

Summation notation could make it more readable though lol

e.g. $\sum_{sym}^n$ for the nth symmetric sum or $\sum_{cyc} q^2$

TrueTears · « **Reply #202 on:** November 27, 2009, 05:56:04 pm »

Quote from: /0 on November 27, 2009, 05:47:45 pm

lol very nice
Summation notation could make it more readable though lol

e.g. $\sum_{sym}^n$ for the nth symmetric sum or $\sum_{cyc} q^2$

Oh nice, can you show me an example of using that summation notation? I haven't used it before haha

/0 · « **Reply #203 on:** November 27, 2009, 06:12:28 pm »

I'm just taking this from the art of problem solving wiki but

I think if you let $P(x) = x^5+ax^4...$

$\sum_{sym} P(x)= q+r+w+t+u$

$\sum_{sym}^2 P(x)= qr+qw+qt+qu+rw+rt+ru+wt+wu+tu$

$\sum_{sym}^3 P(x)= qrw+qrt+qru+qwt+qtu+...$
.
.
.

$\sum_{sym}^5 P(x)= qrwtu$

And cyclic sum cycles through all the variables, so like $\sum_{q,r,w,t,u} q^2 = q^2+r^2+w^2+t^2+u^2$ or $\sum_{cyc} q^2$ if the context is clear

TrueTears · « **Reply #204 on:** November 27, 2009, 06:15:12 pm »

Quote from: /0 on November 27, 2009, 06:12:28 pm

I'm just taking this from the art of problem solving wiki but

I think if you let $P(x) = x^5+ax^4...$

$\sum_{sym} P(x)= q+r+w+t+u$

$\sum_{sym}^2 P(x)= qr+qw+qt+qu+rw+rt+ru+wt+wu+tu$

$\sum_{sym}^3 P(x)= qrw+qrt+qru+qwt+qtu+...$
.
.
.

$\sum_{sym}^5 P(x)= qrwtu$

And cyclic sum cycles through all the variables, so like $\sum_{q,r,w,t,u} q^2 = q^2+r^2+w^2+t^2+u^2$ or $\sum_{cyc} q^2$ if the context is clear

wow that's friggin awesome! Thanks!!

TrueTears · « **Reply #205 on:** November 27, 2009, 09:01:57 pm »

Just started combinatorics and I have a few general theory questions:

What is the number of different 9 letter 'words' we could make from the 9 letters "CHERNOBYL"

So this is just $\frac{9!}{(9-9)!}$

What is the number of different 3 letter 'words' we could make from the 9 letters "CHERNOBYL"

This would be $\frac{9!}{(9-3)!}$

What is the number of different 9 letter 'words' we could make from the 9 letters "RAMANUJAN"

This would be $\frac{9!}{3!2!}$ Since the A and N are indistinguishable so we must divide by the overcounting factor.

Now what if the question said: What is the number of different 3 letter 'words' we could make from the 9 letters "RAMANUJAN"

Do we still need to divide by the overcounting factor?

ie, the answer would be $\frac{\frac{9!}{(9-3)!}}{3!2!}$ or is that wrong?

/0 · « **Reply #206 on:** November 27, 2009, 09:26:49 pm »

I keep trying to prove it and I keep stuffing up, so I'll just say ~~yes~~ NO for now. That's edit: NOT right.

TrueTears · « **Reply #207 on:** November 27, 2009, 09:30:51 pm »

Yeah I think when you divide by the overcounting factor you are already taking into consideration the permutation 'formula'

So $\frac{9!}{3!2!}$ is really just $\frac{\frac{9!}{(9-9)!}}{3!2!}$ lolz

kamil9876 · « **Reply #208 on:** November 27, 2009, 10:42:55 pm »

I don't think it's just a simple division.

Let me derive the C(n,k) formula from the P(n,k) just to show how to generally use an overcounting factor:

say we have n distinct elements, and we want to know how many different combinations of k objects we can choose. There are P(n,k) permutations.

now for clarity, suppose we have n=5, and k=3. and our objects a,b,c,d,e:

Here is a list of permuations in a rectangle:

abc,acb,bac,bca,cab,cba
abe,aeb,bae,bea,eab,eba
.
.
.

etc.

that is, imagine that we list all the permutations, such that all permutations that are the same combination, are in the same row. Obviously there are C(n,k) rows, and a total of P(n,k) elements. But how many in each row? well the answer is k! since there are k! ways of arranging a fixed combination of k elements. Therefore P(n,k)=C(n,k) * k!

====================================================================================

Back to TT's modification of the RAMANUJAN problem:

Recall that our proof above used a bijection between rows and combinations, we will try to do something similair here. suppose that the A's are A1,A2,A3 and the N's N1 and N2. So basically we want to count (N2)R(N1) and (N1)R(N2) as the same thing. Again, arrange the words in a rectangle:

(N1)R(N2),(N2)R(N1)
(N1)J(N2),(N2)J(N1)
(N1)M(N2),(N2)M(N1)

.
.
.
etc.

Now it is looking good so far, we have that 2! factor represented in the length of each row, however this pattern does not continue, as eventually once we start listing words such as AMA, our row length will be bigger!:

(A1)M(A2),(A2)M(A1),(A1)M(A3),(A3)M(A1),(A2)M(A3),(A3)M(A2)

Therefore, I think in order to solve this problem, you must break it up into different cases, since in some cases we get a bigger length in each row.

TrueTears · « **Reply #209 on:** November 27, 2009, 11:03:20 pm »

Wow that proof up there for the relationship b/w C and P was ingenious especially with the reordering and regrouping!

Search the forums now!

We have moved!

Author Topic: TT's Maths Thread (Read 148037 times) Tweet Share

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

Ahmad

Re: TT's Maths Thread

/0

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

/0

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

/0

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

/0

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

Recent Posts

User:
Password: