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

SOLUTION TO PROBLEM 1

$y^8 - y^7 + y^6 - 1 = 0$

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

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

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

Putting it in the above equation, we get

$x^8 + x^2 - x + 1 = 0$

$x^8 = x - x^2 - 1$

$x^9 = x^2 - x^3 - x ...(1)$

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

And answer is 0.

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 $e^{\dfrac{2k\pi i}{n}}$.for k coprime to n. when we multiply all of these we find: $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 $\dfrac{n\phi(n)}{2}$ view this. put that there to get $exp(\phi(n)\pi i)$ $\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 $\sum w_n=\mu(2015)=\boxed{-1}$

SOLUTION TO PROBLEM 6

$x^3 - 2x - 2 = 0$

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

Now, lets see what we need to find,

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

Now multiplying $x - 1$ in numerator and denominator.

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

Now using (1)

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

Now, using vieta

$x_{1} + x_{2} + x_{3} = 0$

$x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{1} = -2$

$x_{1}x_{2}x_{3} = 2$

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

$\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 $\frac{-1}{3}$

SOLUTION TO PROBLEM 5

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

$x^4=-x^3+2x-11 \\ x^5=x^3+2x^2-13x+11 \\ x^6=x^3-13x^2+13x-11$

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

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

$2x-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=\dfrac{2}{15}$, $B=\dfrac{4}{15}$, $C=-\dfrac{3}{5}$ and $D=-\dfrac{11}{15}$.

Hence, $\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 $\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 $S_1=-1,S_2=0,S_3=2,S_4=11$ and $P_1=S_1=-1$, $P_2=S_1P_1-2S_2=1$, $P_3=S_1P_2-S_2P_1+3S_3=5$.

So the sum is $\dfrac{2}{15}(5)+\dfrac{4}{15}(1)-\dfrac{3}{5}(-1)-\dfrac{11}{15}(4)=\boxed{-\dfrac{7}{5}}$.

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

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

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

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

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

Thus one of $P, Q$ (without loss of generality, $Q$) must have degree 2, and both $P$ and $R$ must have degree 3.

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

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

Assume that $P, R+Q$ and $R-Q$ each have one real root; let the root of $P$ be $r_1$.

Since $r_1^2|P^2$, this means that $r_1$ is a root of both $R+Q$ and $R-Q$, and is therefore a root of both $R$ and $Q$.

Now let $P_0, Q_0$, and $R_0$ be the three polynomials $P, Q$, and $R$ with the common root divided out.

We have $P_0^2 +Q_0^2 = R_0^2$.

Then all three polynomials have real coefficients, $P_0$ and $R_0$ have degree 2, and $Q_0$ has degree 1.

We also know that $P_0$ has 0 real roots, $Q_0$ has 1, and $R_0$ has 0 or 2.

Since the latter case would imply that $R$ has 3 real roots, we instead assume that $R_0$ has 0 real roots.

Writing $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 $P_0 = ax^2 + bx + c, R_0 = ax^2 + bx + d$ for real $a, b, c, d$.

Then $Q_0 = (d - c)(2ax^2 + 2bx + c + d)$. Since $P_0$ and $R_0$ have no real roots, we know that $b^2 - 4ac < 0$ and $b^2 - 4ad <0$.

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

But then $Q_0$ has no real roots, a contradiction.

Similarly, if $R_0 + P_0$ has degree 0, $R_0 - P_0$ has degree 2, we write $P_0 = ax^2 + bx + c, R_0 = -ax^2 - bx + d$.

Then $Q_0 = -(c + d)(2ax^2 + 2b + (c - d))$.

Again, $P_0$ and $R_0$ have no real roots, so $b^2 - 4ac < 0$ and $b^2 + 4ad < 0$.

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

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

Clearly, $R(x)$ has degree $3$ and $P(x)$ and $Q(x)$ have degree $2$ and $3$ (W.L.O.G.)

Also,

$R(x) = Q(x) \pm i P(x)$

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

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

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

Since,

$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$, $\beta_{1}$, $\beta_{1}$ and $\alpha, \beta_{2}, \beta_{2}$. Again, since non real roots occur in conjugate pair, we must have $\beta_{1}, \beta_{2} \in \mathbb R$. Thus $Q(x)$ has three real roots.

By newtons sum $P_3=0$. so $\sum \dfrac{1}{a^3+b^3}=\sum \dfrac{1}{-c^3}$ pu x=1/x to have $x^3+\dfrac{2}{3} x^2-x+\dfrac{1}{3}=0$ $-\sum x^3= -((\sum(x))((\sum x)^2-3(\sum x_1x_2))+3\prod x)$ the result follows from vietas.

Yo @Aareyan Manzoor damn you wrote the solution first ,

SOLUTION TO PROBLEM 2 the polynomial with roots $x_i$ is $x^{48}+x^{47}+...+x+1=\dfrac{x^{49}-1}{x-1}=0$ let $y=\dfrac{1}{1-x}$ or $x=\dfrac{y-1}{y}$.then we substitute: $(\dfrac{y-1}{y})^{49}-1=0,y\neq 0$ $y^{49}=(y-1)^{49}$ $y^{48}-24y^{47}+376y^{46}-4324y^{45}+.....+\dfrac{1}{49}=0$ using newtons sum $\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.

SOLUTION TO PROBLEM 8

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

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

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

SOLUTION OF PROBLEM 9

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

Setting $y=ax$,we get $y^3+by^2+acy+a^2d=0$.

$y_i$ are the three rational zeros of the above equation,i.e. they must be integers. Also, since they are divisors of $a^2d$, they must be odd. Since $y_1+y_2+y_3=-b$ and $y_1y_2+y_2y_3+y_3y_1=ac$, both $b$ and $ac$ must be odd,i.e., $b$ and $c$ are odd hence $bc$ is odd. This contradicts the assumption that $bc$ is even. Hence at least one zeros of the polynomial is irrational.

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

So the polynomial can be expressed as $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+b_i\geq3{b_i}^{\frac13}$

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

So $P(2)=(2+b_1)...(2+b_n)\geq3^n$

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

Solution for Problem 11:

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

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

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=2$ is important(sufficient):

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

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

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

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

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

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?

solution to Problem 17 $P_n(2x)=2^n\cos(n\arccos(x))=2^nT_n(x)$ chebyshev polynomials used here(of the first kind). we know:$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 $2x-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)^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+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+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.

SOLUTION TO PROBLEM 19:

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

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

Again by using $x_1x_2x_3=1$ we obtain :

$\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 $x_1x_2x_3=1$ we obtain : $\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=x_1x_2 \ , \ m=x_2x_3 \ , \ n=x_1x_3$ So we have:

$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 $x_1x_2x_3=1$ we obtain : $km+mn+kn=x_1+x_2+x_3$ and $k^2m^2n^2=1$. Thus by using Vieta's again ,

$k^3+m^3+n^3=(14)^3-3(14)(9)+3 = \boxed{2370}$

We also have $(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 = \boxed{2727}$

We also have $\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 = ac$ , and we have $p^3+q^3+r^3=(p+q+r)^3-3(p+q+r)(pq+qr+pr) +3p^2q^2r^2$ . Now using $abc=1$ , we have $pq+qr+pr=ab+bc+ac$ ,

$p^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

$a^3+b^3+c^3=(a+b+c)^3 - 3(a+b+c)(ab+bc+ac)+3$

Adding above both equations ,

$p^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 = g$ , we have $f^3+g^3=855336$ and $fg = 2727$ and substituting $g=\dfrac{2727}{f}$ in the former equation and solving the obtained quadratic , we get $f=a+b+c = 29 , 94$.

HUSH!

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

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

$A\cdot B=\displaystyle \sum_{sym} x_1^3+\displaystyle \sum_{sym} (\dfrac {1}{x_1})^3+3(x_1x_2x_3)^2=2726$. Here I omit the routine calculation for the two sums.