AoPS Academy
be an acute angled triangle with orthocenter 
and 
. Let 
be any other point on the arc 
of the circumcircle of 
and let line 
intersect line 
at 
and let line 
intersect line 
at 
. Let the circumcircles of 
and intersect again at 
(
). Let the lines 
intersect the circumcircle of 
again at 
(
). Prove that the lines 
concur.
+1 w
such that:
for any positive integer 
, the numbers 
are all distinct, and for any positive integers and 
, 
?
have altitudes 
circumcenter 
and orthocenter . Let 
be a point on line 
. The points 
are on lines 
respectively such that 
and 
. Prove that 
is perpendicular to 
.
with real coefficients is the average of two monic polynomials of degree with real roots.
be the given polynomial, and we're about to prove that there exist ![$ Q(x),R(x)\in\mathbb{R}[x]$](http://latex.artofproblemsolving.com/5/9/0/590bd82c227eb97a8b538d9f842264644b92eb6b.png)
, both having 
real roots, and![\[ R(x) = 2\cdot P(x) - Q(x)\]](http://latex.artofproblemsolving.com/9/9/4/99405651639454b8c5068e5e6dd3eab907ac81f3.png)
be arbitrary real numbers, and suppose that 
, and let's take some real numbers 
, such that for all odd 
:![\[ 2\cdot a_i < b_i, b_i > 0\]](http://latex.artofproblemsolving.com/7/2/d/72dfb7c250f34eaab0023d6d6b9895d22f2e9288.png)
we have:![\[ 2\cdot a_i > b_i, b_i < 0\]](http://latex.artofproblemsolving.com/8/c/d/8cdd18de3620aa5068c22171046eadc9d2c75be0.png)
. As we know,
and 
, so 
has at least 
real roots, consequently it has precisely real roots. On the other hand, 
, 
and so on. Therefore, 
has exactly real roots either.
. Note that when using Interpolational Formula, we used only points, 
so we may choose another point 
, such that is monic. Hence, 
is monic either, seeing as 
.
. Let 
be any number greater than the maximum value of 
as 
. Then, let 
, where 
is the 
st Chebyshev polynomial. Then define 
. We get ![\[Q(x_k) = P(x_k) + M T_{n-1}(x_k) = P(x_k) + M (-1)^{n-1 - k},\]](http://latex.artofproblemsolving.com/f/4/f/f4f12539ac36ee78ac1cc23e5310efde9f91e7c5.png)
which has the same sign as 
.
is monic of degree , there is some (large negative) 
such that 
has the same sign as 
, and some (large positive) 
such that 
has the same sign as 
(i.e. is positive).
, by the Intermediate Value Theorem, the number of real roots 
of is at least the number of pairs of consecutive members in the sequence ![\[Q(x), Q(x_0), Q(x_1), \cdots, Q(x_{n-1}), Q(X)\]](http://latex.artofproblemsolving.com/b/a/1/ba112fc6a437d3e71dbe3774aa95d28a0e5a4c7d.png)
with opposite signs. By our previous results, the members of this sequence have the same signs as the members of the sequence ![\[(-1)^n, (-1)^{n-1}, (-1)^{n-2}, \cdots, -1, 1, 1.\]](http://latex.artofproblemsolving.com/4/8/b/48b4462b3e8f20a442ea03d243273e19cb6483d0.png)
Since this sequence has pairs of consecutive members with opposite sign, has at least real roots. Since it has degree , it has exactly real roots. By the same argument, 
has exactly real roots. is the average of two polynomials ( and 
) of degree with real roots.
be the monic polynomial and let 
.
and 
such that for each 
, we have
We may interpolate monic polynomials 
and 
through the 
and 
(if the , are selected "generically" from each other).
works.
. 
is trivial.. If is odd or has a real root, then has a factor 
(
real), in which we are done by factoring out and applying the induction hypothesis on . Now assume that 
is even and 
for all real 
.
where the 
's are strictly increasing and positive reals and 
is arbitrarily large and 
. Note that 
, since 
does not have any real factors. is arbitrarily large, 
i.e. 
. Also, 
. Thus, there are two roots of in each of the intervals 
, so we are done.
are virtually random. Could someone tell me if this is right? Thank you!
be the monic polynomial and let .
necessary in the first place? Couldn't we just state that is arbitrarily large?
with real coefficients is the average of two monic polynomials of degree with real roots.
polynomials. with real roots, the first thing that comes to mind is indeed, Intermediate Value Theorem. Why do we think of this? real roots, but to do this you just need 
distinct points such that 
if 
is odd and 
if is even. Then, by Intermediate Value Theorem, there would be a root in the interval 
for every 
, satisfying the hypothesis that we wanted.
such numbers that passes through, by 
, we are pretty much done, since there must exists polynomial of degree at most that pass these 
points. and that has roots, and we can indeed choose 
. Formalizing this, choose 
being roots of , and 
being roots of , such that![\[ g_i + h_i = 2f(x_i) \]](http://latex.artofproblemsolving.com/7/3/7/7370429546df12cfa3e25e8a4b01e8db9bc4c09b.png)
for some 
and 
for a large value of 
and 
switch signs depend on parity (
as well).
is not necessarily monic. But this is easy to fixed. Suppose we have pick points: 
. This could determine a polynomial of degree and we could somehow control 
such that this is monic. is monic, we could simply check the leading coefficient of 
, is monic as well. So we are done.
. Our base case is 
, where the polynomial 
, we can just take 
as our two monic polynomials., we will prove it for polynomials of degree . Let the polynomial be . If had a real root , then let 
. By our inducktive hypothesis, there exists 2 polynomials 
with all real roots such that 
. Then take 
, which will sum to 
, and are both monic and have all real roots, which proves the problem. Thus, assume has no real roots (which also means is even), and since is monic this means 
for all real . Now, consider points 
that satisfy the following conditions:![\[y_{i} > P(x_{i}), x_{i} < x_{i+1}\]](http://latex.artofproblemsolving.com/6/3/0/630217afb93e037740736620d77d86344f61818d.png)
Let be the degree polynomial that passes through 
for each 
. This means![\[R(x_{2k+1}) > P(x_{2k+1}), R(x_{2k+2}) < P(x_{2k+2})\]](http://latex.artofproblemsolving.com/5/e/d/5edce5ca71975f384d78799deba858232636aca7.png)
and by the intermediate value theorem, this means and must intersect at least times. Furthermore, since is an degree polynomial, which is odd degree, then there exists some 
such that 
, but since 
, they must intersect before 
as well, so and intersect times, which means 
has real roots. We can similarly deduce that and 
intersect times, so 
has real roots. Then, taking 
as our two polynomials, they both have real roots and average to , which completes our inducktive step.
with real coefficients is the average of two monic polynomials of degree with real roots.
we need to show that ![$$f \equiv \frac{1}{2}\left[g+h \right]$$](http://latex.artofproblemsolving.com/2/5/6/25681fa0b612af94f4369bfaeab32ee902c44d5c.png)
i.e 
By Lagrange interpolation choose points 
such that 
The first condition ensures 
and the second condition by IVT ensures both and have an real root.
be the polynomial. Pick 
; and let 
, 
be reals such that 
and 
for all .
be the unique polynomial with degree at most n-1 that passes through points 
in alternating order. Similarly define 
to be the polynomial that passes through points 
. Then, we let 
and 
.
and 
each have roots by Intermediate Value Theorem, and since 
for 
, the roots are preserved in 
and 
. Casework on the parity of yields that in either case, the end-behavior of and yields another root, giving roots.
such that 
—i.e. the statement holds for 
—then the statement holds for 
for any real as well, as 
, and the two polynomials on the RHS are still monic and have all real roots. Hence it suffices to consider the case where our monic polynomial (that we want to express as the average) has no real roots. In particular, its degree must be even, so it's always positive (by looking at end behavior).
for 
, so 
for all . By Lagrange Interpolation, there exist (not necessarily monic) polynomials 
of degree at most such that
Then let 
and 
, so 
are monic polynomials of degree which agree with 
respectively over 
. Then,
hence has a root in each of the intervals 
by IVT. LIkewise,
hence has a root in each of the intervals 
. are all monic, 
is a polynomial of degree which is evidently zero at 
, hence it is identically zero and we have 
for all as desired. 
. If has a real root, WLOG 
. Then write 
, and let 
be such an average. So 
is the average of two polynomials with real roots, since 
have real roots. Replace 
by 
if need be so that do not have a root at 
. Then 
have real roots. does not have a real root, it is of even degree 
, and we can take 
for some sufficiently large huge . Now, is the average of and 
. Clearly has real roots. We claim that 
has two real roots on each of 
. Note that is positive on these intervals 
but at their endpoints. As 
, it blows up on each of these intervals, and so intersects the graph of at two points, when is big enough. We have 
, and as is monic of even degree, 
. However, if is sufficiently large, 
, since 
.
be the given monic polynomial, and select some random pairwise distinct -values 
. At each value , select two other values 
for which 
If is even, make 
and if is odd, make 
. Clearly, if we can find monic polynomials for which 
, 
then we are done by the Intermediate Value Theorem. Fortunately, we can let ![\[Q(x)=c_0+c_1x+c_2x^2+\dots + c_{n-1}x^{n-1}+x^n\]](http://latex.artofproblemsolving.com/5/8/b/58b953a036d0ab2512e859b732d39cadec6beb28.png)
and plug in values 
into that, and we get a system of equations and variables (
) Since the coefficients behind the variables have different ratios in each equation, we have a unique solution. We are done.
and real numbers 
. Let 
for each . Set two polynomials 
such that 
and 
if is odd, and vice versa if is even by Lagrange interpolation. and both have at least one root in ![$[x_i, x_{i+1}]$](http://latex.artofproblemsolving.com/f/f/6/ff6a619efefba44c0248103116cce5ccce8d583b.png)
, hence they both have at least real roots. Furthermore, 
for values of ; thus 
exactly, and we're done.
real roots as distinct real roots, but idk. be the given polynomial with degree . Let 
. Let be a gigantic real number which we will establish later.![\[ P(x) + MQ(x), P(x) - MQ(x). \]](http://latex.artofproblemsolving.com/c/f/6/cf647e513b11b83f0557c330b07d1c1fc3fcd847.png)
Note that these two polynomials are monic.. Fix an arbitrarily small 
. For each 
, choose some 
such that 
, we have 
. This follows from the definition of continuity, and the fact that a subset of a set is in fact a subset of a set [that's craaazy]. Now take the set 
, and define![\[ T := \{ t \in \mathbb R | \exists x \in U \text{ s.t. } |P(x)| = t \}. \]](http://latex.artofproblemsolving.com/3/a/9/3a9501f83e0f7c9523d04da0c6cb1728186ba6e3.png)
Observe that 
is nonempty as 
is in this set. Thus it makes sense to take 
, and choosing 
, we can guarantee that for 
, 
.It follows then that 
has a root on each of these intervals, and hence has at least distinct roots. Likewise 
has a root on each of these intervals too.
, by choosing such that the maximal absolute size of 
on any of the delta intervals is bounded by some 
such that ![$0 \not \in [Q'(x) - c, Q'(x) + c]$](http://latex.artofproblemsolving.com/d/3/5/d35d17b15c997ec42db74cafa031e4f7e6501e9a.png)
, also tightening 
even more such that the derivative is never zero on the interval.) so I'll leave it as an exercise to the reader to work out all the details. is a real polynomial. Thus the remaining root is real. We're done.
be our quadratic, and say it is the average of 
and 
for some reals i, j, k, l. It is sufficient to prove that i, j, k, l exist for all a, b. Thus, 
, 
. Say that 
, 
for some arbitrary . By AM-GM, 
, 
, thus 
, or 
. If 
, we are simply done. Otherwise, set 
, with 
, 
. We can confirm that this works. We are thus done.
values where it keeps having one polynomial be really big then really small next so it keeps crossing the -axis. Then the last degree of freedom for Lagrange Interpolation is used to make the polynomials monic, gg.
the desired monic polynomial that we want to express as an average.
where each are pairwise distinct, there exists a unique monic polynomial ![$Q \in \mathbb{R}[x]$](http://latex.artofproblemsolving.com/1/f/8/1f85aaec57759a5f93cc9df4de444b6e53b4b457.png)
of degree where 
for each .![$R \in \mathbb{R}[x]$](http://latex.artofproblemsolving.com/4/d/a/4da527ded09c721d368e1335555f0d97d0b81791.png)
of degree where 
. Thus, setting
gives the unique monic polynomial of degree satisfying![\[ Q(a_i) = a_i^n + R(a_i) = a_i^n + (b_i-a_i^n) = b_i\]](http://latex.artofproblemsolving.com/8/4/2/8421c2d64a0f98d491bbfbd3cf9fbfbcb160fc50.png)
and let and be the unique monic polynomials where![\[ f(i) = P(i)+ M \cdot (-1)^i \text{ } \text{ and } \text{ } g(i) = P(i) - M \cdot (-1)^i\]](http://latex.artofproblemsolving.com/a/3/9/a398846877b2e436323629d423510aacab479b37.png)
for each 
. We claim and are the desired monic polynomials. Indeed, first notice that for all 
we have![\[ \frac{f(x)+g(x)}{2} = \frac{P(x)+P(x)+M-M}{2} = P(x) \]](http://latex.artofproblemsolving.com/4/6/4/464bfa0cc0e1075bab9ab2f7ad4c6461900c59bc.png)
Since 
and are both monic polynomials of degree and agree on distinct inputs, by monic polynomial interpolation they must be the same polynomial. and have distinct real roots. Indeed, notice that if 
is even then 
and since 
and is positive, we have 
. Moreover, 
and for the same reason, this implies that 
. Thus, the sequence 
has alternating sign. Thus, by IVT, has a root in the interval 
for 
. This implies has distinct real roots. To get the final root, we look at the parity of . is even, then 
is positive for all 
and 
. But, 
and have opposite sign, implying it will hit at some other point. is odd, then 
as and 
as . But, and have the same sign, and thus must hit at another point..
points in the plane we can find a monic polynomial that passes through them. Consider the points,
, \dots, 
. Let 
. Now consider the points 
, \dots, 
. Clearly there existsth degree polynomial passing through these points because of legrange interpolation, now let this polynomial be , clearly 
is athe degree polynomial and clearly it passes through , \dots, . Thus for any points in the plane we can find a be a monic th degree polynomial. Now suppose that for two polynomials and .
. Clearly for any value , we have that 
. Thus for any polynomial, , the corresponding polynomial , such, for any the 
values are reflections over the value of . Thus for , choose , \dots, 
, such that 
for any 
is positive and its reflection over 
is negative, and
for any 
is negative and its reflection over 
is positive. Clearly there exists a monic polynomial passing through, \dots, . Clearly because of 
and polynomial stuff, this polynomial has roots, let this polynomial be . Clearly, we have that due to the reflection property that must also have roots.
, and consider distinct real numbers 
. Take sufficiently large positive 
such that
for all . Then if you let 
, and 
. Then the points we have determine monic degree polynomials 
, and 
with real roots such that 
, because of IVT and lagrange interpolation.
there exists positive integers 
such that
