Finding a Root of a Polynomial in New Year's Eve - 2021

Algebra Level 5

A sequence of polynomials { P n ( x ) } \{P_n(x)\} is defined recursively by the equations P 0 ( x ) = x , P_0(x)=x,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; P n ( x ) = 2 P n 1 2 ( x ) 1 , P_n(x)= 2 P_{n-1}^2(x)-1, where n n is any integer greater than or equal to 1. We can represent the real roots of P 11 ( x ) P_{11}(x) as a finite sequence { x k } 0 k m , \{x_k\}_{0\leq k \leq m}, such that x 0 > x 1 > x 2 > . . . > x m , x_0>x_1>x_2>...>x_m, where m + 1 m+1 is the total number of distinct real roots or this polynomial. If m 2021 , m\geq 2021, enter 1 0 6 x 2021 \lfloor -10^6 x_{2021}\rfloor as your answer. Otherwise, enter 555. 555.


The answer is 999173.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Arturo Presa
Dec 31, 2020

The key to solving this problem is to realize that we can represent the n t h n^{th} polynomial of the sequence by the formula P n ( x ) = cos ( 2 n arccos x ) , P_n(x) = \cos (2^n \arccos x), for all x [ 1 , 1 ] . x \in [-1,1]. This is easy to prove by Mathematical Induction.

We can use the previous representation to find the real roots of P n ( x ) . P_n(x). Indeed, we would need to solve the equation cos ( 2 n arccos x ) = 0. \cos (2^n \arccos x)=0. Then we obtain that 2 n arccos x = π 2 + k π . ( ) 2^n\arccos x =\frac{\pi}{2}+k \pi.\;\;\;\;\; (*)
Since 0 arccos x π , 0\leq \arccos x \leq \pi, then in the previous equation k k is any integer number satisfying 0 k 2 n 1. 0\leq k \leq 2^n-1. Solving the equation ( ) (*) for x , x, we obtain 2 n 2^n distinct real solutions given by the formula x k = cos ( π 2 n + 1 + k π 2 n ) x_k=\cos(\frac{\pi}{2^{n+1}}+k \frac{\pi}{2^n}) where k k is any integer number satisfying 0 k 2 n 1. 0\leq k \leq 2^n-1.

It is easy to see that the x k s x_k's introduced before are the 2 n 2^n distinct real roots of P n . P_n. Notice that the degree of P n P_n is 2 n . 2^n. Besides that, we can also see that x 0 > x 1 > x 2 > . . . > x 2 n 1 . x_0> x_1>x_2>...>x_{2^n-1}.

Now , assume that n = 11. n=11. Then P 11 P_{11} has 2 11 2^{11} distinct real roots given by x k = cos ( π 2 12 + k π 2 11 ) , x_k= \cos(\frac{\pi}{2^{12}}+k \frac{\pi}{2^{11}}), where 0 k m = 2 11 1 = 2047. 0\leq k \leq m=2^{11}-1=2047. Therefore m 2021 m \geq 2021 and x 2021 = cos ( π 2 12 + 2021 π 2 11 ) = 0.999173.... x_{2021}=\cos(\frac{\pi}{2^{12}}+\frac{2021\pi}{2^{11}})=-0.999173... . So, the answer for this problem is 999173 . \boxed{999173}.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...