# 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
5 years, 8 months 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.
• 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. 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?

- 4 years, 7 months 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.

- 5 years, 7 months 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 - 5 years, 7 months ago

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

- 5 years, 7 months ago

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

- 5 years, 7 months 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.

- 5 years, 7 months ago

Can you add these comments to the Functional Equations Wiki pages?

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

Staff - 5 years, 4 months ago

Thanks

- 5 years, 7 months 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?

- 5 years, 7 months 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.

- 5 years, 7 months ago

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

- 5 years, 7 months 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.

- 5 years, 8 months 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.

- 5 years, 8 months 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?

- 5 years, 8 months 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.

- 5 years, 8 months 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!

- 5 years, 7 months ago

Yeah I think that would be good

- 5 years, 7 months ago

Where did you learn your math from- Eddie?

- 5 years, 8 months ago

I mainly learn from books and online courses -why?

- 5 years, 8 months 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.

- 5 years, 8 months ago

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

- 5 years, 8 months ago

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

Staff - 5 years, 8 months 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?

- 5 years, 8 months 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 - 5 years, 8 months ago

By the remainder-factor Theorem,

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

- 5 years, 8 months ago

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

- 5 years, 8 months ago

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

Staff - 5 years, 8 months ago

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

- 5 years, 8 months 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?

- 5 years, 8 months 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$

- 5 years, 8 months ago

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

- 5 years, 8 months 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?

- 5 years, 8 months ago

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

Staff - 5 years, 8 months 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?

- 5 years, 8 months ago

A very common mistake.

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

- 5 years, 8 months ago

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

Thanks

- 5 years, 8 months ago

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

- 5 years, 8 months ago

What does #3 ask me to find?

- 5 years, 8 months 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 - 5 years, 8 months ago

Ok, thank you very much

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

- 5 years, 8 months ago

Extension on #3

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

- 5 years, 8 months 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

- 5 years, 8 months ago

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

- 5 years, 8 months ago

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

Thanks

- 5 years, 8 months 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)?

- 5 years, 8 months 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 - 5 years, 8 months ago

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

- 5 years, 8 months 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 - 5 years, 8 months 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.

- 5 years, 8 months 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.

- 5 years, 8 months ago

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

- 5 years, 8 months ago

Well first I need to get through AIME. :D

- 5 years, 8 months ago

No first u need 2 get through AMC 10 gg

- 5 years, 8 months ago

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

- 5 years, 8 months 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.

- 5 years, 8 months 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 :)

- 5 years, 8 months 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.

- 5 years, 8 months 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.

- 5 years, 7 months ago

Ah! Thanks! :)

- 5 years, 8 months 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 - 5 years, 8 months 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?

- 5 years, 8 months 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.

- 5 years, 8 months ago

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

- 5 years, 8 months ago

# 11 on page 255, yes.

- 5 years, 8 months ago

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

- 5 years, 8 months ago

Which step don't you get?

- 5 years, 8 months 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 - 5 years, 8 months 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-

- 5 years, 8 months 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?

- 5 years, 8 months 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 :)

- 5 years, 8 months 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?

- 5 years, 8 months ago

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

- 5 years, 8 months 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$.

- 5 years, 8 months ago

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

- 5 years, 8 months ago

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

- 5 years, 8 months 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$.

- 5 years, 8 months 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.

- 5 years, 8 months 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!

- 5 years, 8 months 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

- 5 years, 8 months 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.

- 5 years, 8 months 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

- 5 years, 8 months 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.

- 5 years, 8 months 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

- 5 years, 8 months ago

Roots of Unity is also a pretty good resource.

- 5 years, 8 months ago

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

- 5 years, 8 months 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

- 5 years, 8 months ago

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

- 5 years, 8 months 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 - 5 years, 8 months 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

- 5 years, 8 months 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! :)

- 5 years, 8 months 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

- 5 years, 8 months ago

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

- 5 years, 8 months 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

- 5 years, 8 months ago