Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1976 USAMO Problems/Problem 5"
(→‎Solution 3)
 
(5 intermediate revisions by 2 users not shown)
Line 38: Line 38:
  
 
=== Solution 3 ===
 
=== Solution 3 ===
−
Let <math>z, z^2, z^3</math> be three of the 5th roots of unity not equal to one that satisfy <math>1 + z + z^2 + z^3 + z^4</math> as a result. Plugging them into the equation gives the linear system of equations in <math>(A(1), B(1), C(1))</math>:
+
Let <math>z, z^2, z^3</math> be three of the 5th roots of unity not equal to one that satisfy <math>1 + z + z^2 + z^3 + z^4 = 0</math> as a result. Plugging them into the equation gives the linear system of equations in <math>(A(1), B(1), C(1))</math>:
  
−
<math></math>A(1) + zB(1) + z^2C(1) = 0<math>
+
<cmath>A(1) + zB(1) + z^2C(1) = 0</cmath>
−
</math><math>A(1) + z^2B(1) + z^4C(1) = 0</math>
+
<cmath>A(1) + z^2B(1) + z^4C(1) = 0</cmath>
−
<math></math>A(1) + z^3B(1) + z^6C(1) = 0<math>
+
<cmath>A(1) + z^3B(1) + z^6C(1) = 0</cmath>
  
−
Direct observation gives </math>(A(1), B(1), C(1)) = (0,0,0)<math> as a solution, and there are no others because the system of equations is linear. Hence, </math>A(1) = 0<math>, and so </math>(x-1)<math> is a factor of </math>A(x)<math>, as desired. </math>\blacksquare$
+
Direct observation gives <math>(A(1), B(1), C(1)) = (0,0,0)</math> as a solution, and there are no others because the system of equations is linear. Hence, <math>A(1) = 0</math>, and so <math>(x-1)</math> is a factor of <math>A(x)</math>, as desired. <math>\blacksquare</math>
  
−
 
+
''Note: We can generalize this approach to prove the claim in Solution 1 in an equally fast, concise, and readily understandable fashion.''
−
{{alternate solutions}}
 
  
 
== See Also ==
 
== See Also ==

Latest revision as of 16:14, 16 August 2015

Problem

If $P(x)$, $Q(x)$, $R(x)$, and $S(x)$ are all polynomials such that \[P(x^5) + xQ(x^5) + x^2 R(x^5) = (x^4 + x^3 + x^2 + x +1) S(x),\] prove that $x-1$ is a factor of $P(x)$.

Solutions

Solution 1

In general we will show that if $m$ is an integer less than $n$ and $P_0, \dotsc, P_{m-1}$ and $S$ are polynomials satisfying \[P_0(x^n) + x P_1(x^n) + \dotsb + x^{m-1} P_{m-1}(x^n) = \sum_{k=0}^{n-1} x^k S(x),\] then $P_k(1) = 0$, for all integers $0 \le k \le m-1$. For the problem, we may set $n=5$, $m=3$, and then note that since $P(1)= 0$, $(x-1)$ is a factor of $P(x)$.

Indeed, let $\omega_1, \dotsc, \omega_{n-1}$ be the $n$th roots of unity other than 1. Then for all integers $1 \le i \le n-1$, \[\sum_{k=0}^{m-1} \omega_i^k P_k(\omega_i^n) = \sum_{k=0}^{m-1} \omega_i^k P_k(1) = \sum_{k=0}^{n-1} \omega_i^k S(\omega_i) = \frac{\omega_i^{n-1} - 1}{\omega_i - 1} S(\omega_i) = 0 ,\] for all integers $1 \le i \le n$. This means that the $(m-1)$th degree polynomial \[\sum_{k=0}^{m-1} x^k P_k(1)\] has $n-1 > m-1$ distinct roots. Therefore all its coefficients must be zero, so $P_k = 0$ for all integers $0 \le k \le m-1$, as desired. $\blacksquare$

Solution 2

Let $\zeta, \xi, \rho$ be three distinct primitive fifth roots of unity. Setting $x = \zeta, \xi$, we have \begin{align*} P(1) + \zeta Q(1) + \zeta^2 R(1) &= \frac{\zeta^5-1}{\zeta-1} S(\zeta) = 0, \\ P(1) + \xi Q(1) + \xi^2 R(1) &= \frac{\xi^5-1}{\xi-1} S(\xi) = 0 . \end{align*} These equations imply that \[\zeta Q(1) + \zeta^2 R(1) = \xi Q(1) + \xi^2 R(1),\] or \[Q(1) = - ( \zeta + \xi)R(1).\] But by symmetry, \[Q(1) = - (\zeta + \rho)R(1) .\] Since $\xi \neq \rho$, it follows that $Q(1) = R(1) = 0$. Then, as noted above, \[P(1) = P(1) + \zeta Q(1) + \zeta^2 R(1) = 0,\] so $(x-1)$ is a factor of $P(x)$, as desired. $\blacksquare$

Solution 3

Let $z, z^2, z^3$ be three of the 5th roots of unity not equal to one that satisfy $1 + z + z^2 + z^3 + z^4 = 0$ as a result. Plugging them into the equation gives the linear system of equations in $(A(1), B(1), C(1))$:

\[A(1) + zB(1) + z^2C(1) = 0\] \[A(1) + z^2B(1) + z^4C(1) = 0\] \[A(1) + z^3B(1) + z^6C(1) = 0\]

Direct observation gives $(A(1), B(1), C(1)) = (0,0,0)$ as a solution, and there are no others because the system of equations is linear. Hence, $A(1) = 0$, and so $(x-1)$ is a factor of $A(x)$, as desired. $\blacksquare$

Note: We can generalize this approach to prove the claim in Solution 1 in an equally fast, concise, and readily understandable fashion.

See Also

1976 USAMO (Problems • Resources)
Preceded by
Problem 4 		Followed by
Last Question
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1976_USAMO_Problems/Problem_5&oldid=71654"