# Polynomials Sprint: Help Wanted

This post is used to collate any questions / uncertainties that you may have about Polynomials. Mentors will be looking in on this page, and providing explanations to help you understand. Do not be afraid to ask questions, as there will also be others with similar questions.

If you have a question, start a new comment and ask just that question (you can include related questions). State what you have done, and what you are having trouble with. Do not mix questions across different areas.

As an example,

I was working on question 5 and I got stuck. I can use rational root theorem to show that it has no rational roots. However, I do not know how to show that it has no real roots. Can someone guide me?

Note by Calvin Lin
6 years, 1 month ago

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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

So Is this note still active? May I ask a doubt?

- 5 years ago

How many of the problems do you expect us to be able to do and in how much time per problem? I could do all of them except for #37, but problems like #5, #3, #4, #18 took a few days of thought.

- 6 years, 1 month ago

The time taken will greatly depend on your ability level, and familiarity with proofs. I intended for people to spend some time thinking about these problems, which is why this stretches across 2 weeks.

You should give yourself a pat on the back for solving these problems. They are not easy, and are above the level of what is normally covered in high school.

Staff - 6 years, 1 month ago

You have a very good start. By the way, what troubles you in ques 37.??

- 6 years, 1 month ago

It's just that I am not very familiar with functional equations.

- 6 years ago

So there are a few basic ideas with functional equations:

Firstly, a function is not a polynomial! So you can't determine it's coefficient or anything of the sort. So we have a new toolkit:

1. Guess the functions. Normally we guess for linear and constant functions. Guessing these functions provides us with a structure to solve the problem. Gut feel for functional equations is that only linear and constant functions will satisfy, but for some more complex ones, there might be higher powers.

2. Substitute the variables with something else. Remember, you want to cancel stuff out, so if there are $f$ on both sides of the equation, say $f(a) + \text{blah} = f(b)$, then set try to manipulate the variables such that $a=b$.

But this problem does not require any of the machinery listed above, it is a $polynomial$ functional equation, meaning that we can still use our toolkit for polynomials. But step $1$ comes in really handy.

Next, notice that $x^2 + x + 1$, the complicated thing in this question, looks extremely like roots of unity. Once we notice roots of unity, analysing the complex zeroes sort of transforms this problem from a polynomial functional equation one to one which manipulates complex numbers.

Then once we get some roots, (through playing around and trying to force out a contradiction at all steps if possible $\Rightarrow$ this actually suggests extremal principle) then we pull out the roots that we already have, (in this case writing $f(x) = (x^2+1)^m g(x)$ ) at this step what we basically do is to substitute everything back into the original equation to solve for $g(x)$ and remembering our constraints at the same time.

- 6 years ago

Select "Write a summary", and then copy-paste your text into it (with minor edits). Thanks!

Staff - 5 years, 9 months ago

Thanks

- 6 years ago

I don't understand why we're taking $n=3k, 3k+1, 3k+2$, or why getting a zero after substituting $x=\omega$ in $x^{2n}+x^{n}+1$ means divisibility by $x^{2}+x+1$. How would this process come to mind?

- 6 years, 1 month ago

$x^{2}+x+1 = (x - \omega)(x - \omega^{2})$.

Mow let us take $f(x) = x^{2n}+x^{n}+1$.

So if we have $f(\omega) = 0$ and $f(\omega^{2})=0$ ,then we can write by the factor theorem $(x - \omega)(x - \omega^{2}) | f(x)$

that is

$x^{2}+x+1 | f(x)$

Now the divisibility of $f(x)$ is totally dependent on the value of $n$ modulo 3 and hence we have to consider 3 different cases as given by the book.

- 6 years, 1 month ago

Okay, I understand why the substitution works, but I still don't get why taking those values of n work. Please help.

- 6 years, 1 month ago

I'm curious to know how others solved #3.

Engel's solution involves taking modulo 5 and I'm not sure how that could come to mind. I used induction instead.

- 6 years, 1 month ago

I think that one of the motivations behind using the modulo 5 was to eliminate the $6S_{n-1}$ part to get $s_n = s_{n-1}-s_{n-2}$ looks relatively better to infer a solution from.NOw if we can show that this sequence recurs after a value without arriving at 0 then we have already proved that for all n the sequence is not divisible by 5.

If you have solved it in a different way using induction than feel free to post your solution after the due date so that others can learn from it.

- 6 years, 1 month ago

Thanks Eddie!

I believe seeing other people's solutions after solving, or failing to solve, a problem might be insightful. Also, we might understand shortcomings in our own solutions. However, there seems to be no designated place for discussing the solutions to (and not difficulties with) problems in Engel. Where and when do we post our solutions and discuss them?

- 6 years, 1 month ago

Actually Calvin Sir instructed this sprint to be about 2 weeks long and hence if we post our solutions now many will not try the problems on their own.But one thing that you $\textbf{can}$ do right now is make a generalization of the idea that you used to solve the problem and post it in form of a note!!Also make sure that you post a link to the note in the What I learnt page.

If you need help with Latex then I can help.

- 6 years, 1 month ago

What sort of generalization are you talking about?

I didn't play around with the problem after I solved it, so I really don't know in which way to generalize. Should I talk about a monic, integer-coefficient polynomial of n degrees; change the divisor from 5 to a broader set of numbers (primes??!); work with other forms that appear in Vieta's formulae$((x_1x_2)^{n} + (x_2x_3)^{n} + (x_3x_1)^{n})$? It'd be nice if there was some clarification!

- 6 years, 1 month ago

Yeah I think that would be good

- 6 years, 1 month ago

Where did you learn your math from- Eddie?

- 6 years, 1 month ago

I mainly learn from books and online courses -why?

- 6 years, 1 month ago

I asked this because you know a lot and also post lot of nice problems. I wanted to know if you learnt it in school ( age) or were doing it now.

- 6 years, 1 month ago

How does one think of a the method given in Example #6 (on page 250) himself? Is there any alternative method? Please help.

- 6 years, 1 month ago

Read Useful Lemma, which is the next installation in the series.

Staff - 6 years, 1 month ago

After I'd looked through some of the problems, I still don't know how to start, can anyone here tell me what should I do?

Example #13:

Should I expand the equation?

- 6 years, 1 month ago

We want to factorize the polynomial $f(x) = (x-a)^4 + (x-b)^4 - (a-b)^4$.

Hint: What can we say about $f(a)$ and $f(b)$?

Staff - 6 years, 1 month ago

By the remainder-factor Theorem,

$a$ and $b$ are the roots of $f(x)$

- 6 years, 1 month ago

If $f(a)=0$ and $f(b)=0$

- 6 years, 1 month ago

Great. And how would you continue, if you are interested in factorizing $f(x)$?

Staff - 6 years, 1 month ago

$(x-a)(x-b)g(x)$

- 6 years, 1 month ago

What do you expect to find after expanding the equation? What do you notice about the given equation that might let you make progress on the problem? After expanding, what is your plan?

- 6 years, 1 month ago

I came to this and I think I am near to the solution, so now what? Use the roots of unity? And what is the value of $a$ and $b$?

$x^4-(a^2+b^2)x+a^2b^2=0$

Edited:

$x^4-(a^2+b^2)x^2+a^2b^2=0$

- 6 years, 1 month ago

Please check your work. Once you're sure you expanded correctly, try to apply things you know about roots of polynomials. (ahem, vietas)

- 6 years, 1 month ago

Oh, the $x$ is supposed to be $x^2$, just a typo.

Is this ok?

$x^4-(a^2+b^2)x^2+a^2b^2=y^2-(a^2+b^2)y+a^2b^2$

By using Vieta's formula,

Sum of roots = $a^2+b^2$

Product of roots = $a^2b^2$

So the roots are $a^2$ and $b^2$

Am I right?

- 6 years, 1 month ago

I am not too sure what you are doing here. The expansion doesn't seem right to me.

Staff - 6 years, 1 month ago

This is how I expand it

$(x-a)^4$

$=[(x-a)^2]^2$

$=(x^2-a^2)^2$

$=x^4-2a^2x^2+a^4$

Then I do the same to others

$(x-b)^4=x^4-2b^2x^2+b^4$

$(a-b)^4=a^4-2a^2b^2+b^4$

$x^4-2a^2x^2+a^4+x^4-2b^2x^2+b^4=a^4-2a^2b^2+b^4$

$2x^4-2a^2x^2-2b^2x^2=-2a^2b^2$

$x^4-(a^2+b^2)x^2+a^2b^2=0$

Have I done anything wrong here?

- 6 years, 1 month ago

A very common mistake.

$(x-a)^2\not=x^2-a^2$

- 6 years, 1 month ago

Oh, right, what a mistake. Wrote it as $(x-a)(x+a)$

Thanks

- 6 years, 1 month ago

I may have epically screwed up, but I have a very different expansion.

- 6 years, 1 month ago

What does #3 ask me to find?

- 6 years, 1 month ago

Remember to state what you are having trouble with. Which phrase do you not understand?

Let $x_1, x_2$ be the 2 roots of $x^2 - 6x + 1 = 0$.
Let $A_n = x_1 ^n + x_2 ^ n$ for ever non-negative integer $n$.
1) Show that $A_n$ is an integer.
2) Show that $5$ does not divide $A_n$.

Staff - 6 years, 1 month ago

Ok, thank you very much

I just don't know what is the problem asking for

- 6 years, 1 month ago

Extension on #3

Show why $(\sqrt{2}+1)^n$ is very close to even integers for large integer $n$.

- 6 years, 1 month ago

I guess it's something to do with this thing's binomial expansion and then cancelling all the surds to obtain a multiple of 2. I know that I am not fully right

- 6 years, 1 month ago

Does anyone wanna do this or should I explain a solution?

- 6 years, 1 month ago

Can someone please explain the example problem solution for this article - I'm having trouble following it.

Thanks

- 6 years, 1 month ago

When you say "try not to refer to solutions" on the https://brilliant.org/profile/calvin-8u8hog/sets/2-week-sprint-through-polynomials/, does that mean not referring to the solutions to the examples in the text (p. 245-250)?

- 6 years, 1 month ago

You are referencing:

D. Work on the following problems in the book. Try not to refer to solutions. 3, 4, 5, 11, 13, 16, 17, 18.

I'm asking you to work on the problems listed on page 254-258. Solutions are given at the end of the chapter and you should not be referring to them.

With regards to

A. Read through pages 245 - 250 of Problem Solving Strategies. (Not the whole chapter)

You should be reading through the solutions to the examples.

Staff - 6 years, 1 month ago

@Calvin Lin Generally ,when solving Olympiad problems, after how many hours of trying should one look at the solutions?

- 6 years, 1 month ago

It greatly depends on the problem vs your ability level. A rough guide could be: Look at a solution only after you have given up for more than 30 minutes.

When you read solutions, don't simply see how it's done. An important aspect (which is often ignored), is to dissect and analyze them. Ask yourself:
1. Do I know enough to come up with this solution? If yes, why didn't I? If no, what do I need to know?
2. Is the solution motivated by some principle? What aspects of the question gave it away?
3. If I saw a similar (or even the exact same) problem in 6 months, can I solve it within an hour?

Staff - 6 years, 1 month ago

I am not Calvin but I think I can still answer. It depends on the problem. If you are doing AIME #15 level problems and you have about 1 hour to kill in the test, spend at least 30 minutes on it doing stuff (not just sitting idle)! If you are doing USAMO, I'd say do stuff for at least 1-1.5 hours. Same for IMO.

- 6 years, 1 month ago

Oh dude not to brag but I feel like the USAMO problems are really transparent. Like you can just look at it and know exactly what to do. AIME problems for me are more challenging because you have to actually problem solve.

- 6 years, 1 month ago

Then why don't you make USAMO and win? They aren't transparent at all.

- 6 years, 1 month ago

Well first I need to get through AIME. :D

- 6 years, 1 month ago

No first u need 2 get through AMC 10 gg

- 6 years, 1 month ago

Yeah. Dude I don't think that will be a problem this year. I've been practicing. :D

- 6 years, 1 month ago

Generally you shouldn't read the solutions until after solving it. The beauty of olympiad problems is that there is a lot to learn from solving them. If you cannot solve one after a few days put it away and come back to it. After solving other problems you will get ideas.

- 6 years, 1 month ago

Is there any alternative or easier way to solve 11 in the book other than the factorizing method given in the book? I must say that the questions are brain-wracking and thus this one made me give up factorizing :(. I must also include that few of the questions asked by Calvin to solve had an application of symmetric polynomial functions too, thus he shouldn't have included them! I would like to know methods to simplify eqautions like 11. I quite didnt know how to proceed to prove #4 and #5 though I'd got all of the rest right. I would like to get some exposure to some olympiad proofs as I'd actually learnt form the answers of these questions ( 4& 5)! Thanks :)

- 6 years, 1 month ago

The first thing you might notice is that the powers in the equation are all even. That suggests us to apply a substitution $x=z^2$ to simplify things. Calling the resulting expression $P(x)$ we have: $P(x)=x^4+4x^3-10x^2+4x+1=0.$ Now to factorize this, we get help from the Rational Root Theorem, which suggests us to try $\pm 1$. We see that $P(1)=0$, hence $(x-1)$ is a factor of $P(x)$ by the Remainder-Factor Theorem. Now rearrange terms and factorize: $P(x)=x^4-x^3+5x^3-5x^2-5x^2+5x-x+1$ $=x^3(x-1)+5x^2(x-1)-5x(x-1)-1(x-1)$ $=(x-1)(x^3+5x^2-5x-1)$ $=(x-1)\cdot Q(x) ~~~[\text{say}]$ Note that $Q(x)$ is also monic and the constant term is $1$. So it's easy to apply Rational Root Theorem again. Since $Q(1)=0$, $(x-1)$ is a factor of it. We again factorize: $Q(x)=x^3-x^2+6x^2-6x+x-1=x^2(x-1)+6x(x-1)+1(x-1)=(x-1)(x^2+6x+1)$ Therefore: $P(x)=(x-1)\cdot Q(x)=(x-1)(x-1)(x^2+6x+1)=(x-1)^2(x^2+6x+1)=0$ Now $x=1\implies z=\pm\sqrt{x}=\pm 1$ is a root and bash the other factor with Quadratic formula.

- 6 years, 1 month ago

Huh, you can also do it by noticing that the coefficients are symmetric with respect to the middle term and so you can pull it apart into the sum of two squares which share a common factor.

- 6 years ago

Ah! Thanks! :)

- 6 years, 1 month ago

Good question. That was one reason why I chose 11, because there is an 'easier' way to see the factorization.

5 is actually hard. I was surprised it was posted so early in the set.

Staff - 6 years, 1 month ago

Yes. Indeed 5 is hard and I actually had to learn from its solutions :(. Could you tell me what would the follow-ups for this course be?

- 6 years, 1 month ago

Sure!

First, let $y=z^2$ then we have $((y+1)^2)^2-(4y)^2=0$ factoring as a difference of squares we have $(y^2+6y+1)(y^2-2y+1)=0$ then we can find the roots of the two quadratic factors to be $-3\pm 2\sqrt{2}, 1$ so the solutions are $z=\pm\sqrt{-3\pm2\sqrt{2}}, \pm{1}$ Sorry if those aren't simplified.

- 6 years, 1 month ago

Hi! Are you talking about problem no.11? Not example, Problem!

- 6 years, 1 month ago

# 11 on page 255, yes.

- 6 years, 1 month ago

:D. But sorry, I don't get it :( EDIT- Ok....let me try working with the method you use now :)

- 6 years, 1 month ago

Which step don't you get?

- 6 years, 1 month ago

Whenever you write algebraic identities, you should clearly state them. For example, you should write

$z^8 + 4z^6 - 10z^4 + 4z^2 + 1 = y^4 + 4y^3+ 6y^2 + 4 y + 1 - 16 y^2 = (y+1)^4 - 16y^2$

It wasn't obvious how you arrived at the conclusion, and adding the intermediate steps would help.

Very nice observation!

Staff - 6 years, 1 month ago

Uhm...I actually didnt get that direct simplification..let me go through again, by this I mean- The expression you have written on the second line-

- 6 years, 1 month ago

How to convert cubic's of the form $x^3+bx^2+cx+d$ into $x^3+px+q$ in order to apply the solving method given in the book, The book says it can be done by translation, What does that mean?

- 6 years, 1 month ago

Hi Ishan,

Yes...just as @Pranshu Gaba said you must first translate the polynomial by $k$ units.and then since we must eliminate the $x^{2}$ part we must find the value of k for which the co-efficient of $x^{2}$ is 0.But in this case since the polynomial is monic the co-efficient of $x^{3}$ will remain unchanged inspite of the transformation...try it out to get the idea :)

- 6 years, 1 month ago

Hi Eddie,

I feel that even if a polynomial is not monic, translating it in any direction does not change the leading coefficient. This is because, essentially we are not changing the leading term when we translate the function. What do you think?

- 6 years, 1 month ago

You are correct it holds for all...nothing special about monic .. :) ......Cheers!

- 6 years, 1 month ago

Let the roots of the first cubic be $\alpha, \beta,$ and $\gamma$. By Vieta's theorem, we can see that $\alpha + \beta + \gamma = -b$.

Translation means shifting functions. If we translate the function horizontally by $k$, the roots become $\alpha + k, \beta + k$ and $\gamma + k$. Since the coefficient of $x^2$ in the second cubic is $0$, the sum of its roots is also $0$. Try to find a value of $k$ for which the sum of the new roots become $0$.

Once that is done, and the new roots are obtained, by Vieta's again, we can get value of $p$ and $q$ in terms of $b, c$ and $d$.

- 6 years, 1 month ago

If we shift $x$ by $k$, it would change the coefficient of $x^{3}$, wouldn't it?

- 6 years, 1 month ago

Thanks, @Samuraiwarm Tsunayoshi even if the coefficient would have changed, we could have still divided by that coefficient to get a monic cubic

- 6 years, 1 month ago

Shifting $f(x)$ by $k$ horizontally means $f(x \pm k)$, if $k$ is positive. If there is no restriction on $k$, we can simply write it as $f(x - k)$.

In this case, $x^3 + bx^2 + cx + d$ would become $(x - k)^3 + b(x - k)^2 + c(x-k) +d$. Note that the term of $x^3$ appears only once, and its coefficient is still $1$.

- 6 years, 1 month ago

I haven't encountered roots of unity before. I think the material in the book is too insufficient to understand for first-timers like me. Can somebody guide me to a good resource for roots of unity? Thanks.

- 6 years, 1 month ago

Hi Ananay!

If you are comfortable with basic trigonometry and complex numbers, you should be able to graph them on the complex plane given a unit circle. Given this, you should look at the AoPSWiki - this link is probably the best short fundamental explanation of roots of unity I have seen on the internet. Also, here is a nice blog post on AoPS expanding on roots of unity.

Lastly, if you are looking for a more visual approach, read this. Hope that helps!

- 6 years, 1 month ago

I'll admit they are a little confusing. If you're not one to memorize formulas, you can easily derive or find any root of unity by just drawing the unit circle and placing $n$ equidistant points along the circumference (for the $n$th roots of unity). You can use basic trig from there. :D

- 6 years, 1 month ago

The issue is that some students who are trying to learn roots of unity without De Moivre's Theorem will have trouble doing this. I think @Ananay Agarwal is looking for something geometrical to get an intuition about it.

- 6 years, 1 month ago

Yeah. That's what I was trying to say, is that you can easily construct the roots on a unit circle in the complex plane. I still have to do that sometimes. :D

- 6 years, 1 month ago

Yes, okay, I see what you're saying. I was just pointing out that writing stuff in $\text{cis}$ form is not the most obvious thing for some students. For me, it's very automatic at this point because I have practiced a lot, but I am sure that, the first time I saw roots of unity and $\text{cis}$ form, I was a bit confused for at least one moment.

- 6 years, 1 month ago

Same. I'm actually really terrible at trig and complex numbers, I have to rely fully on my intuition to solve them. Like converting rectangular to polar, I have to derive everything on the spot. I can't really memorize stuff like that. :P

- 6 years, 1 month ago

Roots of Unity is also a pretty good resource.

- 6 years, 1 month ago

I read through the notes but I don't understand how to change something into exponential form, can anyone tell me how?

- 6 years, 1 month ago

Be sure to check out the khan academy videos on the roots of unity!!!There Sal makes an excellent job to explain them for beginners...... Also check out this video by Patrick JMT Click here

- 6 years, 1 month ago

Sure! I commit to helping anyone in these topics to the maximum possible.

- 6 years, 1 month ago

Thanks for volunteering to be mentors. When the members have any questions about the material, they will post their question here. Please check in when you can, and help to clear out doubts. If this post become too long / unwieldly, I will come up with an alternative.

If any of you would like to post relevant notes and problems, you can state the links in a comment and I'd review them. (This includes posts made in the past)

Staff - 6 years, 1 month ago

You should make other posts like combinatorics, number theory, geometry, and another stuffs separately. To be honest, I'm completely suck at this kind of algebra and I haven't done this ever. I think I'll be just a student here. T__T

Hopefully, I'll come around and help at combinatorics and number theory. ^__^

Edit: I am completely confused what this topic is, so I just called it "this kind of algebra" . XD

- 6 years, 1 month ago

First of all, it's pretty obvious that the polynomials sprint is just a starter, so there will be other projects. I like how Calvin is taking these subjects once at a time, making things very organized.

Second, this is not abstract algebra. Abstract algebra is a totally different field of math (pun intended)! This is basic polynomial algebra, and considering you are Level 5, there is no reason that you should not be able to help. This thread is for Levels 2-3 so you are free to spectate but you should probably let the level 2-3s be the students.

Third, even I have my weak subjects. For example, I am better in algebra and number theory than I am in combinatorics. So don't feel bad if you are slightly less active in some of these sprints. Good to have you on board! :)

- 6 years, 1 month ago

I got lvl 5 algebra because of the completely different topics like algebraic identities, solving system of equations, little bit inequality, or stuffs like that. I can't even know what is the $i$ thing all about other than $\sqrt{-1}$. T__T

- 6 years, 1 month ago

That's fine; then you can be a spectator!

- 6 years, 1 month ago

When a topic is deleted it actually should disappear, this long list makes my head hurt @Suyeon Khim @Silas Hundt @Peter Taylor @David Mattingly @Calvin Lin @Arron Kau and all other staff members

- 6 years, 1 month ago