Brilliant Polynomial Roots Contest - Season 1

Welcome to the first ever Brilliant Polynomial Roots Contest. This is inspired by many other contests in Brilliant. The aim is to improve the skills of Brilliant users in olympiad problems that ask you to find some functions involving the roots of a polynomial by vieta's, newton sums or other methods. The rules are:

  1. I will post the first problem. If someone solves it, he or she can post a solution and then must post a new problem.

  2. A solution must be posted below the thread of the problem. Then, the solver must post a new problem as a separate thread.

  3. Please make a substantial comment.

  4. Make sure you know how to solve your own problem before posting it, in case no one else is able to solve it within 36 hours. Then, you must post the solution and you have the right to post a new problem.

  5. If the one who solves the last problem does not post a new problem in 24 hours, the creator of the previous problem has the right to post another problem.

  6. No restriction in techniques you can use! use of calculus and roots of unity is allowed. use of cyclotomic polynomials and möbius inversion is also allowed.

  7. It is NOT compulsory to post original problems. But make sure it has not been posted on Brilliant.

  8. Your question must have a polynomial. it can be like f(x)=x21x1f(x)=\dfrac{x^2-1}{x-1} or f(x)=x+1f(x)=x+1. Both are allowed as long as the simplified form is a polynomial.

Format your proofs as

SOLUTION TO PROBLEM n

proof here

Question as

PROBLEM n

ask question relevant question here

To answer the latest question just shift to the "newest" mode


EDIT: for external discussion go to the discussion board

Note by Aareyan Manzoor
3 years, 11 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

PROBLEM 7

If a,b,ca, b, c are the roots of the equation

x32x23x4=0x^3 - 2x^2 - 3x - 4 = 0

Show that a2016b2016ab+b2016c2016bc+c2016a2016ca\frac{a^{2016} - b^{2016}}{a - b} + \frac{b^{2016} - c^{2016}}{b - c} + \frac{c^{2016} - a^{2016}}{c - a} is an integer.

This problem has been solved by Aareyan Manzoor but after time was finished, so Dev Sharma can Post the next problem

Dev Sharma - 3 years, 11 months ago

Log in to reply

Simple induction man, it not only holds for 2016 but for all natural no. n in the powers.

Reetun Maiti - 3 years, 10 months ago

Log in to reply

PROBLEM 1 given the roots of y8y7+y61=0y^8-y^7+y^6-1=0 are y1,y2,...,y7,y8y_1,y_2,...,y_7,y_8 find the value of 1y19+1y29+...+1y79+1y89\dfrac{1}{y_1^9}+\dfrac{1}{y_2^9}+...+\dfrac{1}{y_7^9}+\dfrac{1}{y_8^9} This problem has been solved by dev sharma

Aareyan Manzoor - 3 years, 11 months ago

Log in to reply

SOLUTION TO PROBLEM 1

y8y7+y61=0y^8 - y^7 + y^6 - 1 = 0

Now we have to form a polynomial whose roots are 1y1,.....\frac{1}{y_{1}}, .....

Now, let x=1yx = \frac{1}{y}

then y=1xy = \frac{1}{x}

Putting it in the above equation, we get

x8+x2x+1=0x^8 + x^2 - x + 1 = 0

x8=xx21x^8 = x - x^2 - 1

x9=x2x3x...(1)x^9 = x^2 - x^3 - x ...(1)

Putting x=1y1,...,1y8x = \frac{1}{y_{1}},..., \frac{1}{y_{8}} repeatedly in the equation and add them all and using bit Newton Sum (S1=S2=S3=0S_{1} = S_{2} = S_{3} = 0)

And answer is 0.

Dev Sharma - 3 years, 11 months ago

Log in to reply

Let wkw_k denote the 2015th primitive roots of unity. Find

n=1ϕ(2015)wnk=1ϕ(2015)wk\sum _{n=1}^{\phi \left(2015\right)}w_n\prod _{k=1}^{\phi \left(2015\right)}w_k

This problem has been solved by Aareyan Manzoor

Julian Poon - 3 years, 11 months ago

Log in to reply

SOLUTION TO PROBLEM 4 you forgot to format your question properly! the proof anyways:

claim: the product of all the primitive roots of unity are 1.

proof: we know that each primitive root of unity can be written as e2kπine^{\dfrac{2k\pi i}{n}}.for k coprime to n. when we multiply all of these we find: exp(2πin1x2015,gcd(x,2015)=1x)exp(\dfrac{2\pi i}{n}\sum_{1≤x≤2015,gcd(x,2015)=1} x) the formula for the sum of all co-primes less then n is nϕ(n)2\dfrac{n\phi(n)}{2} view this. put that there to get exp(ϕ(n)πi)exp(\phi(n)\pi i) ϕ(n)\phi(n) is always even apart from n=1,2. so this will always be 1 for n>2. at 2015 it is one then. the rest is easy i guess. we put 1 to find wn=μ(2015)=1\sum w_n=\mu(2015)=\boxed{-1}

Aareyan Manzoor - 3 years, 11 months ago

Log in to reply

PROBLEM 6

Let the roots of p(x)=x32x2p(x)=x^3-2x-2 be x1,x2,x3x_1,x_2,x_3. Evaluate: i=13xi+1xi2+xi+1\sum_{i=1}^{3} \dfrac{x_i+1}{x_i^2+x_i+1}

This problem has been solved by Dev Sharma

Alan Enrique Ontiveros Salazar - 3 years, 11 months ago

Log in to reply

SOLUTION TO PROBLEM 6

x32x2=0x^3 - 2x - 2 = 0

x31=2x+1...(1)x^3 - 1 = 2x + 1 ...(1)

Now, lets see what we need to find,

x+1x2+x+1\frac{x + 1}{x^2 + x + 1}

Now multiplying x1x - 1 in numerator and denominator.

x21x31\frac{x^2-1}{x^3 -1}

Now using (1)

x212x+1\frac{x^2 - 1}{2x + 1}

Now, using vieta

x1+x2+x3=0x_{1} + x_{2} + x_{3} = 0

x1x2+x2x3+x3x1=2x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{1} = -2

x1x2x3=2x_{1}x_{2}x_{3} = 2

Now putting x=x1,x2,x3x = x_{1}, x_{2}, x_{3} in the expression we want to find out and simplifying it, we get

x122x1+1+x222x2+1+x322x3+1(12x1+1+12x2+1+12x3+1)\frac{x_{1}^2}{2x_{1} + 1} + \frac{x_{2}^2}{2x_{2} +1} + \frac{x_{3}^2}{2x_{3} + 1} -(\frac{1}{2x_{1} + 1} + \frac{1}{2x_{2} + 1} + \frac{1}{2x_{3} + 1})

Now using those vieta relations, we can get answer 13\frac{-1}{3}

Dev Sharma - 3 years, 11 months ago

Log in to reply

We can simplify our last expression like this -

x122x1+1+x222x2+1+x322x3+1(12x1+1+12x2+1+12x3+1)\frac{x_{1}^2}{2x_{1} + 1} + \frac{x_{2}^2}{2x_{2} +1} + \frac{x_{3}^2}{2x_{3} + 1} -(\frac{1}{2x_{1} + 1} + \frac{1}{2x_{2} + 1} + \frac{1}{2x_{3} + 1})

= x12(4x2x3+2x2+2x3+1)+x22(4x1x3+2x1+2x3+1)+x32(4x1x2+2x1+2x2+1)(2x1+1)(2x2+1)(2x3+1)\frac{x_{1}^2(4x_{2}x_{3} + 2x_{2} + 2x_{3} + 1) + x_{2}^2(4x_{1}x_{3} + 2x_{1} + 2x_{3} + 1) + x_{3}^2(4x_{1}x_{2} + 2x_{1} + 2x_{2} + 1)}{(2x_{1} + 1)(2x_{2} + 1)(2x_{3} + 1)} - (4x2x3+2x2+2x3+1)+(4x1x3+2x1+2x3+1)+(4x1x2+2x1+2x2+1)(2x1+1)(2x2+1)(2x3+1)\frac{(4x_{2}x_{3} + 2x_{2} + 2x_{3} + 1) + (4x_{1}x_{3} + 2x_{1} + 2x_{3} + 1) + (4x_{1}x_{2} + 2x_{1} + 2x_{2} + 1)}{(2x_{1} + 1)(2x_{2} + 1)(2x_{3} + 1)}

Now, simplify it and get the answer!!

Dev Sharma - 3 years, 11 months ago

Log in to reply

@Dev Sharma Natural approach, there's another that is easier but it still good, well done. Now let's see your problem!

Alan Enrique Ontiveros Salazar - 3 years, 11 months ago

Log in to reply

PROBLEM 3 find ln(1ω3)\sum \ln(1-\omega^3) where ω\omega are 2015th roots of unity≠1.

This problem has been solved by Julian Poon

Aareyan Manzoor - 3 years, 11 months ago

Log in to reply

PROBLEM 5 given the polynomial x4+x32x+11=0x^4+x^3-2x+11=0 a,b,c,d are its roots. evaluate cyca3(a+1)a4+11\sum_{cyc}\dfrac{a^3(a+1)}{a^4+11}

This problem has been solved by Alan Enrique Ontiveros Salazar

Aareyan Manzoor - 3 years, 11 months ago

Log in to reply

SOLUTION TO PROBLEM 5

Surely there's an easier way, but this is a new way:

x4=x3+2x11x5=x3+2x213x+11x6=x313x2+13x11x^4=-x^3+2x-11 \\ x^5=x^3+2x^2-13x+11 \\ x^6=x^3-13x^2+13x-11

So x3(x+1)x4+11=2x112xx3\dfrac{x^3(x+1)}{x^4+11}=\dfrac{2x-11}{2x-x^3}

Now we say that 2x11=(2xx3)(Ax3+Bx2+Cx+D)2x-11=(2x-x^3)(Ax^3+Bx^2+Cx+D). Expanding and substituting the first three relations we get:

2x11=(3A+B+CD)x3+(13A2B+2C)x2+(9A+13B2C+2D)x11A11B+11C2x-11=(-3A+B+C-D)x^3+(13A-2B+2C)x^2+(-9A+13B-2C+2D)x-11A-11B+11C

Matching the coefficients and solving the system we get A=215A=\dfrac{2}{15}, B=415B=\dfrac{4}{15}, C=35C=-\dfrac{3}{5} and D=1115D=-\dfrac{11}{15}.

Hence, 2x112xx3=215x3+415x235x1115\dfrac{2x-11}{2x-x^3}=\dfrac{2}{15}x^3+\dfrac{4}{15}x^2-\dfrac{3}{5}x-\dfrac{11}{15}

So we want to find 215xi3+415xi235xi1115(4)\displaystyle \dfrac{2}{15} \sum x_i^3+\dfrac{4}{15}\sum x_i^2-\dfrac{3}{5} \sum x_i - \dfrac{11}{15}(4)

Using Newton's Sums we get S1=1,S2=0,S3=2,S4=11S_1=-1,S_2=0,S_3=2,S_4=11 and P1=S1=1P_1=S_1=-1, P2=S1P12S2=1P_2=S_1P_1-2S_2=1, P3=S1P2S2P1+3S3=5P_3=S_1P_2-S_2P_1+3S_3=5.

So the sum is 215(5)+415(1)35(1)1115(4)=75\dfrac{2}{15}(5)+\dfrac{4}{15}(1)-\dfrac{3}{5}(-1)-\dfrac{11}{15}(4)=\boxed{-\dfrac{7}{5}}.

Alan Enrique Ontiveros Salazar - 3 years, 11 months ago

Log in to reply

Problem 15

Prove that there doesn't exist polynomials with integer coefficients fk(x)f_k(x)(k=1,2,3,4), such that 9x+4=f1(x)3+f2(x)3+f3(x)3+f4(x)3 9x+4=f_1(x)^3+f_2(x)^3+f_3(x)^3+f_4(x)^3

solved by Xuming Liang

Xuming Liang - 3 years, 11 months ago

Log in to reply

Solution: Consider the third root of unity w1w\ne 1. Since w2=1ww^2=-1-w, we can express fi(w)=aw+bf_i(w)=aw+b for some integers a,ba,b. Thus fi(w)3=(aw+b)3=3ab(ba)w+a3+b33a2bf_i(w)^3=(aw+b)^3=3ab(b-a)w+a^3+b^3-3a^2b. Note that the coefficient of ww is always even, therefore the coefficient of ww on the LHS of the equality is even. However the same coefficient on the RHS is odd, thus these polynomials cannot exist.

Xuming Liang - 3 years, 11 months ago

Log in to reply

dont you think you need to prove thet fif_i is linear?

Aareyan Manzoor - 3 years, 11 months ago

Log in to reply

Problem 16

Among the polynomials P(x),Q(x),R(x)P(x), Q(x), R(x) with real coefficients at least one has degree two and one has degree three. If P(x)2+Q(x)2=R(x)2P(x)^2 + Q(x)^2 = R(x)^2 prove that one of the polynomials of degree three has three real roots.

Solved by Khang Nguyen Thanh

Xuming Liang - 3 years, 11 months ago

Log in to reply

SOLUTION OF PROBLEM 16: This is a problem of All-Russian MO 2002.

Define deg(P)\deg(P) to mean the degree of P(x)P(x), and likewise deg(Q)\deg(Q) and deg(R)\deg(R).

Observe that max{deg(P),deg(Q)}=deg(R)\max\{\deg(P), \deg(Q)\} = \deg(R).

This is because deg(R2)=deg(P2+Q2)=max{deg(P2),deg(Q2)}\deg(R^2) = \deg(P^2 + Q^2) = \max \{\deg(P^2), \deg(Q^2)\} (leading coefficients of P2P^2 and Q2Q^2 are positive and do not cancel), and 2deg(R)=deg(R2)=max{deg(P2),deg(Q2)}=2max{deg(P),deg(Q)}2\deg(R) = \deg(R^2) = \max \{\deg(P^2), \deg(Q^2)\} = 2 \max \{\deg(P), \deg(Q)\}.

Thus one of P,QP, Q (without loss of generality, QQ) must have degree 2, and both PP and RR must have degree 3.

Now we write P2=(R+Q).(RQ)P^2 = (R + Q).(R-Q). We know that both factors have degree 3.

Since PP has either 1 or 3 real roots, R+QR+Q and RQR-Q either both have one real root or three real roots accordingly.

Assume that P,R+QP, R+Q and RQR-Q each have one real root; let the root of PP be r1r_1.

Since r12P2r_1^2|P^2, this means that r1r_1 is a root of both R+QR+Q and RQR-Q, and is therefore a root of both RR and QQ.

Now let P0,Q0P_0, Q_0, and R0R_0 be the three polynomials P,QP, Q, and RR with the common root divided out.

We have P02+Q02=R02P_0^2 +Q_0^2 = R_0^2.

Then all three polynomials have real coefficients, P0P_0 and R0R_0 have degree 2, and Q0Q_0 has degree 1.

We also know that P0P_0 has 0 real roots, Q0Q_0 has 1, and R0R_0 has 0 or 2.

Since the latter case would imply that RR has 3 real roots, we instead assume that R0R_0 has 0 real roots.

Writing Q02=(R0+P0).(R0P0)Q_0^2 = (R_0 + P_0).(R_0 - P_0), we see that one of the factors must have degree 2 and the other degree 0.

If the first factor has degree 2, we may write P0=ax2+bx+c,R0=ax2+bx+dP_0 = ax^2 + bx + c, R_0 = ax^2 + bx + d for real a,b,c,da, b, c, d.

Then Q0=(dc)(2ax2+2bx+c+d)Q_0 = (d - c)(2ax^2 + 2bx + c + d). Since P0P_0 and R0R_0 have no real roots, we know that b24ac<0b^2 - 4ac < 0 and b24ad<0b^2 - 4ad <0.

Adding the two inequalities and multiplying by 2, this means 4b28a(c+d)<04b^2 - 8a(c + d) < 0.

But then Q0Q_0 has no real roots, a contradiction.

Similarly, if R0+P0R_0 + P_0 has degree 0, R0P0R_0 - P_0 has degree 2, we write P0=ax2+bx+c,R0=ax2bx+dP_0 = ax^2 + bx + c, R_0 = -ax^2 - bx + d.

Then Q0=(c+d)(2ax2+2b+(cd))Q_0 = -(c + d)(2ax^2 + 2b + (c - d)).

Again, P0P_0 and R0R_0 have no real roots, so b24ac<0b^2 - 4ac < 0 and b2+4ad<0b^2 + 4ad < 0.

Adding and multiplying by 2 gives 4b28a(cd)<04b^2 - 8a(c - d) < 0, which again implies that Q0Q_0 has no real roots.

Thus our original assumption is false, and either PP or RR must be a third-degree polynomial with 3 real roots.

Khang Nguyen Thanh - 3 years, 11 months ago

Log in to reply

Clearly, R(x)R(x) has degree 33 and P(x)P(x) and Q(x)Q(x) have degree 22 and 33 (W.L.O.G.)

Also,

R(x)=Q(x)±iP(x)R(x) = Q(x) \pm i P(x)

From the above equation, it is clear that if R(x)R(x) has a real root, it is also a root of P(x)P(x) and Q(x)Q(x). So, R(x)R(x) has at most 22 real roots (counted with multiciplity). (Since P(x)P(x) has degree 22 and non real roots occur in conjugate pairs)

If R(x)R(x) has 22 real roots (one with multiplicity), then we are done. If not, then let α\alpha be the common real root to all three polynomials.

Let β1\beta_{1} and β2\beta_{2} be the other two roots of Q(x)Q(x),

Since,

Q2(x)=(R(x)+P(x))(R(x)P(x))Q^2 (x) = (R(x) + P(x))(R(x) - P(x))

and the two polynomials in the brackets are not identical, the set of roots must be α\alpha, β1\beta_{1}, β1\beta_{1} and α,β2,β2\alpha, \beta_{2}, \beta_{2}. Again, since non real roots occur in conjugate pair, we must have β1,β2R\beta_{1}, \beta_{2} \in \mathbb R. Thus Q(x)Q(x) has three real roots.

Ishan Singh - 3 years, 11 months ago

Log in to reply

PROBLEM 20:

If a,b,ca,b,c are roots of the polynomial x33x2+2x+3=0x^3-3x^2+2x+3=0 , find the value of 1a3+b3+1b3+c3+1a3+c3\dfrac{1}{a^3+b^3} + \dfrac{1}{b^3+c^3} + \dfrac{1}{a^3+c^3}

Easy , because its created by me ;)

This problem is solved by Aareyan Manzoor

Nihar Mahajan - 3 years, 10 months ago

Log in to reply

By newtons sum P3=0P_3=0. so 1a3+b3=1c3\sum \dfrac{1}{a^3+b^3}=\sum \dfrac{1}{-c^3} pu x=1/x to have x3+23x2x+13=0x^3+\dfrac{2}{3} x^2-x+\dfrac{1}{3}=0 x3=(((x))((x)23(x1x2))+3x)-\sum x^3= -((\sum(x))((\sum x)^2-3(\sum x_1x_2))+3\prod x) the result follows from vietas.

Aareyan Manzoor - 3 years, 10 months ago

Log in to reply

Yo @Aareyan Manzoor damn you wrote the solution first ,

A Former Brilliant Member - 3 years, 10 months ago

Log in to reply

PROBLEM 2

If 1,x1,x2,.....,x481, x_{1}, x_{2}, ....., x_{48} are 49th roots of unity, then find

i=1481(1xi)3\displaystyle\sum_{i=1}^{48} \frac{1}{(1 - x_{i})^3} This problem has been solved by Aareyan Manzoor

Dev Sharma - 3 years, 11 months ago

Log in to reply

SOLUTION TO PROBLEM 2 the polynomial with roots xix_i is x48+x47+...+x+1=x491x1=0x^{48}+x^{47}+...+x+1=\dfrac{x^{49}-1}{x-1}=0 let y=11xy=\dfrac{1}{1-x} or x=y1yx=\dfrac{y-1}{y}.then we substitute: (y1y)491=0,y0(\dfrac{y-1}{y})^{49}-1=0,y\neq 0 y49=(y1)49y^{49}=(y-1)^{49} y4824y47+376y464324y45+.....+149=0y^{48}-24y^{47}+376y^{46}-4324y^{45}+.....+\dfrac{1}{49}=0 using newtons sum ap1=s1=24p2=s1p12s2=176p3=s1p2s2p1+3s3=276\begin{array}{c}a p_1&=&s_1&=&24\\ p_2&=&s_1p_1-2s_2&=&-176\\ p_3&=&s_1p_2-s_2p_1+3s_3&=&\boxed{-276}\end{array} we are done.

Aareyan Manzoor - 3 years, 11 months ago

Log in to reply

PROBLEM 8

Let p(x)p(x) be a polynomial with integer coefficients. Assume that p(a)=p(b)=p(c)=1p(a) = p(b) = p(c) = -1, where a,b,ca, b, c are three different integers. Prove that p(x)p(x) has no integral zeroes.

This problem has been solved by Svatejas Shivakumar

Dev Sharma - 3 years, 11 months ago

Log in to reply

SOLUTION TO PROBLEM 8

Lemma: If f(x)f(x) is a polynomial with integeral coefficients and aa is an integeral root of f(x)f(x) and mm is any integer different from aa, then ama-m divides f(x)f(x).

Proof: On dividing f(x)f(x) by xmx-m we get f(x)=(xm)q(x)+f(m)f(x)=(x-m)q(x)+f(m), where q(x)q(x) is a polynomial with integral coefficients. For x=ax=a, we get f(a)=0=(am)q(a)+f(m)f(a)=0=(a-m)q(a)+f(m) or f(m)=(am)q(a)f(m)=-(a-m)q(a). Hence ama-m divides f(m)f(m).

Suppose dd is an integeral root of p(x)p(x), then by the lemma, da,db,dcd-a,d-b,d-c divides 1-1 . But 1-1 has only 22 factors namely 1,1-1,1. Hence at least two of a,b,ca,b,c are the same but a,b,ca,b,c are different. Hence, p(x)p(x) has no integral zeroes.

A Former Brilliant Member - 3 years, 11 months ago

Log in to reply

PROBLEM 9

The polynomial ax3+bx2+cx+dax^3+bx^2+cx+d has integral coefficients a,b,c,da,b,c,d with adad odd and bcbc even. Show that at least one zero of the polynomial is irrational.

Nobody was able to solve this,so Svatejas Shivakumar can post the next problem

A Former Brilliant Member - 3 years, 11 months ago

Log in to reply

SOLUTION OF PROBLEM 9

Let xi,i=1,2,3x_i,i=1,2,3 be the rational roots of the given.polynomial. Then (ax)3+b(ax)2+ac(ax)+a2d=0(ax)^3+b(ax)^2+ac(ax)+a^2d=0.

Setting y=axy=ax,we get y3+by2+acy+a2d=0y^3+by^2+acy+a^2d=0.

yiy_i are the three rational zeros of the above equation,i.e. they must be integers. Also, since they are divisors of a2da^2d, they must be odd. Since y1+y2+y3=by_1+y_2+y_3=-b and y1y2+y2y3+y3y1=acy_1y_2+y_2y_3+y_3y_1=ac, both bb and acac must be odd,i.e., bb and cc are odd hence bcbc is odd. This contradicts the assumption that bcbc is even. Hence at least one zeros of the polynomial is irrational.

A Former Brilliant Member - 3 years, 11 months ago

Log in to reply

PROBLEM 10

The polynomial P(x)=xn+a1xn1++an1x+1P(x)=x^{n}+a_{1}x^{n-1}+\ldots+a_{n-1}x+1 with nonnegative coefficients a1,,an1a_{1},\ldots,a_{n-1} has nn real roots. Prove that P(2)3nP(2) \ge 3^{n}.

This problem has been solved by Aditya Agarwal

A Former Brilliant Member - 3 years, 11 months ago

Log in to reply

Because of the given condition (non-negative coefficients), the roots would be non-positive.

So the polynomial can be expressed as P(x)=(x+b1)...(x+bn)P(x)=(x+b_1)...(x+b_n) where b_i=-x_i\>0), and \(x_i are the roots.

Now, by the AM-GM inequality, we get, 2+bi3bi132+b_i\geq3{b_i}^{\frac13}

Now by Vieta's Formulas, we have, that the product of the roots is 11.

So P(2)=(2+b1)...(2+bn)3nP(2)=(2+b_1)...(2+b_n)\geq3^n


Those who are saying that the product b1b2...bn=1b_1b_2...b_n=-1, it won't be. Because bi>0b_i>0, and thus the product has to be greater than 1-1, so the product would definitely by 11. (The confusion arised because of the substitution, bi=xib_i=-x_i)

Aditya Agarwal - 3 years, 11 months ago

Log in to reply

PROBLEM 11:

Prove: For any polynomial g(x)g(x), deg(g(x))>1\text{deg}(g(x))>1, another polynomial k(x)k(x) can be substituted for xx, in such a way that g(k(x))g(k(x)) can be expressed as a product of non-constant polynomials. (All the polynomials have integral coefficients)

Nobody posted the solution, Aditya Agarwal posted the solution

Aditya Agarwal - 3 years, 11 months ago

Log in to reply

Solution for Problem 11:

It is evident that, g(a)g(x)g(a)-g(x) is divisible by axa-x. Now lets us take aa, such that axa-x, is divisible by g(x)g(x), for example, a=k(x)=x+p(x)a=k(x)=x+p(x). So, g(k(x))g(k(x)) is divisible by g(x)g(x). Now because deg(g(k(x)))\text{deg}(g(k(x))) is greater than deg(g(x))\text{deg}(g(x)), the second factor is not constant.

Aditya Agarwal - 3 years, 11 months ago

Log in to reply

Please post the solution and the next problem as well since no one has solved it within the time limit.

A Former Brilliant Member - 3 years, 11 months ago

Log in to reply

@Aditya Agarwal here is a problem!


Problem 14

Let P(x)P(x) be a polynomial of degree n>1n>1 with integer coefficients, and let kk be a positive integer. Consider the polynomial Q(x)=P(P(P(P(x))))Q(x) = P( P ( \ldots P(P(x)) \ldots )), where PP occurs kk times. Prove that there are at most nn integers tt such that Q(t)=tQ(t)=t.

Dan Shwarz,Romania

solved by Xuming Liang

Sualeh Asif - 3 years, 11 months ago

Log in to reply

This is the fifth problem of IMO 2006, I recognized it from a documentary about the USA IMO team. I will outline the basic idea of the proof:

The first idea shows why the case k=2k=2 is important(sufficient):

If Q(s)=sQ(s)=s but P(s)sP(s)\ne s, then P(P(s))=sP(P(s))=s. In other words, if ss is a fixed point of QQ but not of PP, then it is a fixed point of P(P(x))P(P(x)). So it suffices to consider(count) the fixed points of k=2k=2.

We now prove the case for k=2k=2:

If all fixed points of P(P(x))P(P(x)) are fixed points of P(x)P(x), then the result holds because PP has at most nn fixed points.

If not, then there exist aba\ne b such that P(a)=b,P(b)=aP(a)=b, P(b)=a. The next observation is that all pairs (a,b)(a',b') that satisfy the previous equations(a,ba',b' need not to be distinct) have the same sum, i.e. a+b=a+b=ca+b=a'+b'=c for some constant cc. Thus all the numbers in these pairs(fixed points of P(P(x))P(P(x))) are the roots to the polynomial P(x)+xcP(x)+x-c. Since this has the same degree as PP(n>1n>1), we are done.


I know this isn't the full solution, so feel free to fill in the steps.

Xuming Liang - 3 years, 11 months ago

Log in to reply

This has totally stumped me! I tried proving it for k=2. But even when I did that, I was unsure of what to do?

Aditya Agarwal - 3 years, 11 months ago

Log in to reply

Keep trying though!
The k=2k=2 is a very crucial step!

Sualeh Asif - 3 years, 11 months ago

Log in to reply

Problem 17

Consider the sequence of polynomials {Pn(x)}n=1,2,3,...\{P_n(x)\}_{n=1,2,3,...} such that Pn(2cosx)=2ncosnx,xR,nNP_n(2\cos x)=2^n\cos nx, \forall x\in\mathbb{R},\forall n\in\mathbb{N}^*.

Prove that: 1Pn(x)n2x2n,x>2,nN\large 1\le\dfrac{\sqrt[n]{P_n(x)}-2}{x-2}\le n, \forall x>2, \forall n\in\mathbb{N}^*

Khang Nguyen Thanh - 3 years, 11 months ago

Log in to reply

solution to Problem 17 Pn(2x)=2ncos(narccos(x))=2nTn(x)P_n(2x)=2^n\cos(n\arccos(x))=2^nT_n(x) chebyshev polynomials used here(of the first kind). we know:T2(x)=2x21,T3(x)=4x33x,Tn+1(x)=2xTn(x)Tn1(x)T_2(x)=2x^2-1 ,T_3(x)=4x^3-3x,T_{n+1}(x)=2xT_n(x)-T_{n-1}(x) we see hat cases 2,3 are allways satisfied.so 2x22Tn+1(2x)n+12(n+1)(2x2)2x22xTn(2x)Tn1(2x)n+1(n+1)(2x2)+2xn+14xPn(2x)4Pn1(2x)((n+1)(2x2)+2)n+12x-2≤2\sqrt[n+1]{T_{n+1}(2x)}-2≤(n+1)(2x-2)\\ 2x≤2\sqrt[n+1]{2xT_n(2x)-T_{n-1}(2x)}≤(n+1)(2x-2)+2\\ x^{n+1}≤4xP_n(2x)-4P_{n-1}(2x)≤((n+1)(2x-2)+2)^{n+1} we had (2x)nPn(2x)(n(2x2)+2)n((n1)(2x2)+2)nPn1(x)(2x)n1(2x)^n≤P_n(2x)≤(n(2x-2)+2)^n\\-((n-1)(2x-2)+2)^n≤-P_{n-1}(x)≤-(2x)^{n-1} multiplying and adding 4(2x)n+14((n1)(2x2)+2)n4xPn(2x)4Pn1(2x)4x(n(2x2)+2)n4(2x)n14(2x)^{n+1}-4((n-1)(2x-2)+2)^n≤4xP_n(2x)-4P_{n-1}(2x)≤4x(n(2x-2)+2)^n-4(2x)^{n-1} now notice that 4(2x)n+14((n1)(2x2)+2)nxn+14x(n(x2)+2)n4(2x)n1((n+1)(2x2)+2)n+14(2x)^{n+1}-4((n-1)(2x-2)+2)^n≥x^{n+1}\\4x(n(x-2)+2)^n-4(2x)^{n-1}≤((n+1)(2x-2)+2)^{n+1} Hence proved by induction.

Aareyan Manzoor - 3 years, 11 months ago

Log in to reply

PROBLEM 19

If x1,x2,x3x_1,x_2,x_3 are the roots of P(x)=x39x2+14x1P(x)=x^3-9x^2+14x-1, find all the possible values of x1x2+x2x3+x3x1\dfrac{x_1}{x_2}+\dfrac{x_2}{x_3}+\dfrac{x_3}{x_1}.

This problem is solved by both , Xuming and Nihar.

Alan Enrique Ontiveros Salazar - 3 years, 10 months ago

Log in to reply

SOLUTION TO PROBLEM 19:

First I let a=x1x2,b=x2x3,c=x3x1a=\dfrac{x_1}{x_2} , b= \dfrac{x_2}{x_3} , c= \dfrac{x_3}{x_1}.

Now using x1x2x3=1x_1x_2x_3=1 (By Vieta's) , we can easily obtain that ab+bc+ac=1a+1b+1cab+bc+ac=\dfrac{1}{a} + \dfrac{1}{b}+\dfrac{1}{c} .

Again by using x1x2x3=1x_1x_2x_3=1 we obtain :

ba+cb+ac=x13+x23+x33=(x1+x2+x3)33(x1+x2+x3)(x1x2+x2x3+x1x3)+3x1x2x3=933(9)(14)+3=354\dfrac{b}{a}+ \dfrac{c}{b}+ \dfrac{a}{c} = x_1^3+x_2^3+ x_3^3 \\ =(x_1+x_2+x_3)^3-3(x_1+x_2+x_3)(x_1x_2+x_2x_3+x_1x_3)+3x_1x_2x_3 \\ = 9^3-3(9)(14)+3 \\ =\boxed{354}

Again by using x1x2x3=1x_1x_2x_3=1 we obtain : ab+bc+ca=(x1x2)3+(x2x3)3+(x1x3)3\dfrac{a}{b}+ \dfrac{b}{c}+ \dfrac{c}{a}=(x_1x_2)^3+(x_2x_3)^3+(x_1x_3)^3. Now we let k=x1x2 , m=x2x3 , n=x1x3k=x_1x_2 \ , \ m=x_2x_3 \ , \ n=x_1x_3 So we have:

k3+m3+n3=(k+m+n)33(k+m+n)(km+mn+kn)+3(k2m2n2)k^3+m^3+n^3=(k+m+n)^3-3(k+m+n)(km+mn+kn) + 3(k^2m^2n^2)

Again by using x1x2x3=1x_1x_2x_3=1 we obtain : km+mn+kn=x1+x2+x3km+mn+kn=x_1+x_2+x_3 and k2m2n2=1k^2m^2n^2=1. Thus by using Vieta's again ,

k3+m3+n3=(14)33(14)(9)+3=2370k^3+m^3+n^3=(14)^3-3(14)(9)+3 = \boxed{2370}

We also have (a+b+c)(1a+1b+1c)=3+ab+bc+ca+ba+cb+ac(a+b+c)\left(\dfrac{1}{a} + \dfrac{1}{b}+\dfrac{1}{c}\right) =3 + \dfrac{a}{b}+ \dfrac{b}{c}+ \dfrac{c}{a}+ \dfrac{b}{a}+ \dfrac{c}{b}+ \dfrac{a}{c} that is :

(a+b+c)(ab+bc+ac)=3+2370+354=2727(a+b+c)(ab+bc+ac)=3 + 2370+354 = \boxed{2727}

We also have (ab+bc+ca)(ba+cb+ac)=a3+b3+c3+a3b3+b3c3+a3c3+3 \left(\dfrac{a}{b}+ \dfrac{b}{c}+ \dfrac{c}{a}\right)\left( \dfrac{b}{a}+ \dfrac{c}{b}+ \dfrac{a}{c}\right) = a^3+b^3+c^3+a^3b^3+b^3c^3+a^3c^3+3

Now we let p=ab , q=bc ,r=acp=ab \ , \ q=bc \ , r = ac , and we have p3+q3+r3=(p+q+r)33(p+q+r)(pq+qr+pr)+3p2q2r2p^3+q^3+r^3=(p+q+r)^3-3(p+q+r)(pq+qr+pr) +3p^2q^2r^2 . Now using abc=1abc=1 , we have pq+qr+pr=ab+bc+acpq+qr+pr=ab+bc+ac ,

p3+q3+r3=(p+q+r)33(p+q+r)(pq+qr+pr)+3p2q2r2=(ab+bc+ac)33(ab+bc+ac)(a+b+c)+3p^3+q^3+r^3=(p+q+r)^3-3(p+q+r)(pq+qr+pr) +3p^2q^2r^2 \\ = (ab+bc+ac)^3-3(ab+bc+ac)(a+b+c)+3

and we also have

a3+b3+c3=(a+b+c)33(a+b+c)(ab+bc+ac)+3a^3+b^3+c^3=(a+b+c)^3 - 3(a+b+c)(ab+bc+ac)+3

Adding above both equations ,

p3+q3+r3+a3+b3+c3=(ab+bc+ac)3+(a+b+c)36(a+b+c)(ab+bc+ac)+6(ab+bc+ca)(ba+cb+ac)=(ab+bc+ac)3+(a+b+c)36(2727)+6(ab+bc+ac)3+(a+b+c)3=855336p^3+q^3+r^3+a^3+b^3+c^3 = (ab+bc+ac)^3+ (a+b+c)^3-6(a+b+c)(ab+bc+ac)+6 \\ \Rightarrow \left(\dfrac{a}{b}+ \dfrac{b}{c}+ \dfrac{c}{a}\right)\left( \dfrac{b}{a}+ \dfrac{c}{b}+ \dfrac{a}{c}\right) = (ab+bc+ac)^3+ (a+b+c)^3-6(2727)+6 \\ \Rightarrow (ab+bc+ac)^3+ (a+b+c)^3 = 855336

Let a+b+c=f , ab+bc+ac=ga+b+c=f \ , \ ab+bc+ac = g , we have f3+g3=855336f^3+g^3=855336 and fg=2727fg = 2727 and substituting g=2727fg=\dfrac{2727}{f} in the former equation and solving the obtained quadratic , we get f=a+b+c=29,94f=a+b+c = 29 , 94.

HUSH!

Nihar Mahajan - 3 years, 10 months ago

Log in to reply

Well done! :D

Alan Enrique Ontiveros Salazar - 3 years, 10 months ago

Log in to reply

Log in to reply

Yeah for sure problem has long calculations ;)

A Former Brilliant Member - 3 years, 10 months ago

Log in to reply

The answers are indeed 94,2994,29. The key to finding the answer is constructing equations using symmetric sums. Note that our desired sum is equal to cycx12x3\displaystyle \sum_{cyc}x_1^2x_3, which we denote AA. Let BB denote its symmetric counterpart: cycx12x2\displaystyle \sum_{cyc} x_1^2x_2.

Note that A+B=symx12x2=9143=123A+B=\displaystyle \sum_{sym} x_1^2x_2=9\cdot 14-3=123