AoPS Academy
[/quote]
, do not answer with "
is a solution" only. Either you post any kind of proof or at least something unexpected (like "
is the smallest solution). Someone that does not see that is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
is given. Let 
be the foot of altitude dropped for 
. Tangents from to circles with diameters 
and 
intersects with the said circles at 
and 
, in respective. Point 
in the plane is given so that 
. Prove that 
and lie on a circle.
with 
with all the unit squares are initially white coloured. Every move, we can turn the color (from white to black or otherwise) from the 5 unit squares that form this T-pentomino which can be rotated or reflexed (see the image below). Determine all natural numbers 
such that all unit squares on the board can be made into all black after a finite number of moves.
be a square of center 
and let 
be the symmetric of the point 
with respect to point . Let 
be the intersection of 
and 
, and let be the intersection of 
and 
. Show that 
is the angle bisector of 
.
be a positive integer. For every positive integer 
the sequence 
is defined, where 
are integers. Among these sequences, for at most how many of them does all the elements of the sequence give different remainders when divided by ?
?
vertices, each edge has one of the colors 
, 
, or 
. For each 
, if the vertices can be divided into 
groups such that any two vertices connected by an edge of color 
are in different groups, find the minimum possible value of 
.
such that, for all 
,
such that for all integer 
and a subset of ![$[n],$](http://latex.artofproblemsolving.com/d/2/7/d27d2715f4f95c24a28b7c6371a006d4c803b2cf.png)
satisfy 
for all 
then 
be the set of positive integers. Find all functions 
such that for all 
, ![\[m^2f(m) + n^2f(n) + 3mn(m + n)\]](http://latex.artofproblemsolving.com/0/f/f/0ff783fa217b7be4bda5006e417f1471ea3a6fca.png)
is a perfect cube.
![$\mathbb{R}[x]$](http://latex.artofproblemsolving.com/a/8/8/a88b9f4858016b1771635c611d44b56161a08009.png)
be the set of all polynomials with real coefficients. Find all functions ![$f: \mathbb{R}[x] \rightarrow \mathbb{R}[x]$](http://latex.artofproblemsolving.com/0/3/3/033be3ab043bd47e537f01791c813739ad5c7da5.png)
satisfying the following conditions:
maps the zero polynomial to itself,![$P \in \mathbb{R}[x]$](http://latex.artofproblemsolving.com/f/7/c/f7c4c970908aa5570a9afcc45fc16c1d36cc3d5d.png)
, 
, and![$P, Q \in \mathbb{R}[x]$](http://latex.artofproblemsolving.com/c/3/0/c301578bade5b93056d77454921cba0a9812212c.png)
, the polynomials 
and 
have the same set of real roots.
and 
be the largest prime divisor of 
. Note that 
and 
. Then we want to prove that there exist infinitely many positive integers such that 
, there exists a positive integer 
such that 
.. Firstly, manually check that![\[g(f(36))=\text{max}(g(f(5)),g(f(6)))=g(f(6)).\]](http://latex.artofproblemsolving.com/3/1/8/318a170daa14b6fff4f07b8db8fc6ddf615a560a.png)
Now note that there must be some positive integer 
such that 
. Then![\[g(f((k+1)^2))=\text{max}(g(f(k)),g(f(k+1)))=g(f(k+1)).\;\blacksquare\]](http://latex.artofproblemsolving.com/f/6/d/f6de44cec26cca96f8cf7d3b8b3b657b267d5ddf.png)
such that 
and 
.
is strictly increasing or strictly decreasing past one point, which is impossible due to the previous claim. satisfy the given constraint. QED.
and 
be the largest prime divisor of . Then we wish to show that![\[P(f(n^2)) = P(f((n+1)^2).\]](http://latex.artofproblemsolving.com/c/0/2/c026b8e89b18f0ed4ff603bab560d5956cc708c5.png)
However, 
, so this is equivalent to![\[\max(P(f(n), P(f(n-1)) = \max(P(f(n), P(f(n+1)).\]](http://latex.artofproblemsolving.com/5/4/0/540fc47d9f8ff8387d975111e0bc7c7bdcafecee.png)
We will show that there exist infinitely many so that 
; this clearly finishes. Note that this is equivalent to showing that the sequence 
cannot be strictly increasing; however, since 
this is impossible and we are done. 
denote the largest prime factor of 
. The largest prime factor of 
is just 
because 
such that 
. Note that given any prime 
, there is a value of 
such that is not divisible by . Thus, given any finite list of primes, by Chinese Remainder Theorem we can pick to avoid all of them. Thus, the sequence is unbounded, which clearly shows the claim. such that 
. Suppose for the sake of contradiction that after some point, the sequence is strictly increasing. Then, after a certain point, the largest prime divisor keeps increasing. The slowest that the "largest prime divisor" sequence is allowed to increase is by going to the next prime, and counting primes grows at a faster than linear rate by PNT, so for sufficiently large , all has a prime factor greater than say 
. However, when is a perfect square, we have that 
Both of these factors are less than , hence contradiction as we know that there is a prime factor at least for all sufficiently large .
and 
, then 
. Notice that if we can find infinitely many such that 
, then all these will satisfy the problem statement. It just suffices to show that there cannot exist an such that 
is strictly increasing for all 
.
where 
and 
. It follows that for every 
, 
By picking large enough we have 
, hence contradiction. switches from increasing to decreasing and vice versa infinitely many times. Picking these maximum critical points yields the desired solutions.
and let 
denote the largest prime factor of . Note that 
is clearly unbounded. Also it cannot be increasing or decreasing due to obvious reasons. Therefore it must have infinitely many "peaks". Hence we're done.
and 
. Define 
as the largest prime divisor of 
. Then, we have that . such that 
. Since 
, this is equivalent to showing that has infinitely many ``local maxima.'' has finitely many ``local maxima.'' Then, this implies that for big enough , is either strictly increasing or strictly decreasing for 
. Since always outputs a positive number, it is impossible for it to be always strictly decreasing, so we would like to show that cannot be strictly increasing forever. and 
, so clearly it cannot be strictly increasing, done.
, and notice that our desired expressions factor as 
and 
. for which the largest prime factor of is greater than or equal to the largest prime factor of 
or . In other words, the largest prime factor of is neither always increasing or decreasing for large . for which the largest prime factors of each term in 
is always strictly increasing. However, we simply note that![\[f((m+1)^2) = f(m) \cdot f(m+1),\]](http://latex.artofproblemsolving.com/f/e/4/fe48589da43825212a5edfc858d774bd7305276f.png)
is the greatest prime factor of 
, contradiction. 
denote the largest prime factor of some and . We basically want that ![\[W(n^4+n^2+1)=W((n+1)^4+(n+1)^2+1)\]](http://latex.artofproblemsolving.com/7/3/9/7395fc83adf508bddb31d4fba66c6fffbe8209d6.png)
however notice the factorizations, ![\[n^4+n^2+1=f(n)f(n-1) \ \land \ (n+1)^4+(n+1)^2+1=f(n)f(n+1)\]](http://latex.artofproblemsolving.com/1/7/a/17adcaa03116348a86556b66a99c0f9cadeda087.png)
which gets us to 
although, there are a few cases to deal with. We check a few 
points by hand and want that 
on both points are as then we are automatically done. We just want, ![\[W(f(n)) \ge max\{W(f(n+1)),W(f(n-1))\}\]](http://latex.artofproblemsolving.com/6/1/3/61383056ea3f84ddf6344b3bbcb85cebbfdb5cd5.png)
to hold and call all such pairs as "good tuples".
then, obviously 
such that 
we have, 
as in this function becomes decreasing after a finite point. However this means that the primes dividing are bounded above. We shall prove the opposite. Basically 
arbitrarily large divisble by arbitrarily large primes . Consider a large prime of the form 
by dirichlet's theorem now by a bit of trivial quadratic residue check, one realizes that 
is a quadratic residue and for any such we have some 
. Now we have that, ![\[n^2+n+1 \equiv 0 \ (mod \ p) \iff (2n+1)^2 \equiv (-3) \ (mod \ p) \iff (2n+1) \equiv d \ (mod \ p) \iff n \equiv \frac{d-1}{2} \ (mod \ p)\]](http://latex.artofproblemsolving.com/3/5/6/356e78307daaf00056b5ae42e61176935d8040f3.png)
so arbitrarily large exist. Also modular inverse of 
exists due to 
.
then we would be done. Hence assuming the opposite we have only finite such points where our original condition holds. So there is some finite constant 
above which whenever there is a ![\[W(f(n)) \ge W(f(n-1)) \implies W(f(n))<W(f(n+1))\]](http://latex.artofproblemsolving.com/4/3/9/4390ecbf24698b7e216c33e13fcb692707e7356a.png)
and hence pick the first such point and on the next point if 
then this pair is a "good tuple" but we have already assumed that we have exceeded the finite set (Euclid's Infinitude Style Argument) and thus we must have a strict increasing 
after that point. We shall prove this is not the case as arbitrary points have, what we called "sign-flips" earlier.
and so on. All these forms have some conclusion which is not something we like. Generalizing to a general power seems too wanky to work with, but testing 
turns out we can wish for 
and thus, ![\[a^2+a+1 \mid b^2+b-a^2-a \iff a^2+a+1 \mid (b-a)(b+a+1)\]](http://latex.artofproblemsolving.com/6/9/9/6994fbaed61a1e1ae5e403971a42834b2e34fde4.png)
again by a bit of Evan's "Blackjack Analogy" we have that, 
when we suddenly realize 
and thus, ![\[W(f(n+1)^2))=max\{W(f(n)),W(f(n+1))\}\]](http://latex.artofproblemsolving.com/a/9/c/a9c7a4b194def1c41e5e2208a112852420bc6512.png)
when we let 
arbitrary so that 
and hence 
however, 
and thus 
due to condition which creates an obvious contradiction!
observation but whatever. 
and 
gives 
and 
respectively.
infinitely many times, we are done.
and the other factor. Take the successive number, we see they share a factor Eg; take 
, we see that it factorizes to 
, the larger polynomial becomes the smaller one. So, if after some , the largest prime always comes from the larger polynomial, this means that the largest prime will always increase in form (in 
is just 
). This is obviously false as the largest prime of 
(n^4+n^2+1) equals that of , so all the numbers in between and 
will either have equal or smaller largest prime than , this solves our problem by contradiction. As there should be some for which the largest prime belongs to the smaller polynomial, in a chain of numbers where it belongs to the larger one. So, we can find two consecutive numbers. but this can not happen due to the same above argument.
and let 
satisfy 
. Then the two possible values of sum to 
so one of them is 
. Let this be . Then choose minimized such that 
. Then 
. Fron 
we get 
for 
and large enough. Now if is the largest prime factor of then from the identity 
we have 
for large and 
. Thus the values of from 
to 
have some maximum 
. Then 
, so for arbitrarily large we generate arbitrarily many values of 
as desired.
and 
be the largest divisor of .
and hence 
.
never becomes monotonous.. is bounded. To see other wise obs that 
is a 
when 
which, by dirichlet, shows that infinite primes divide some value of .
.
a contradiction.
, let 
, and let 
be the maximum prime divisor of . Observe that 
can clearly not equal . such that 
., when 
, is always less than , which is absurd because this sequence obviously reaches 
. such that 
. for which whenever . However, we have an easy contradiction here because 
is either or because of the identity 
. such that 
and 
. satisfying Lemma 3, and observe that 
and hence 
. Similarly, 
. By the statement of Lemma 3, we conclude that 
, and we are done.
and 
Show that
Let 
Show that
Prove that
and 
.
is equal to the largest prime divisor of 
.
![\[ n^4 + n^2 + 1 = (n^2+1)^2 - n^2 = (n^2-n+1)(n^2+n+1) = f(n-1)f(n) \]](http://latex.artofproblemsolving.com/e/b/2/eb2b67a171520e9615463c7d17a726179f21184a.png)
![\[ (n+1)^4 + (n+1)^2 + 1 = f(n)f(n+1). \]](http://latex.artofproblemsolving.com/5/7/b/57bc6b0d29c4d32083859bf5f36404172c968e53.png)
and largest prime divisor of 
.
we have 
,
)
and 
(exactly the equalities in the beginning of solution). It means that 
an similarily 
.
we have 
,
is the largest. Then obviously 
-- contradiction.
we have 
(remember that 
!
,![\[g(n)=(n^2+1)^2-n^2=(n^2-n+1)(n^2+n+1)=f(n-1)f(n),\]](http://latex.artofproblemsolving.com/8/f/1/8f1caa58d391ee3797e39256f3598aba875c29c9.png)
and 
have the same largest prime divisor. To this end it is enough to guarantee that the largest prime divisor of 
.
the largest prime dividing 
for infinitely many 
is bounded from above by some positive integer 
,
.
,
,
,
.
for every 
would be an infinite decreasing sequence of positive integers, absurd. Therefore there exists an 
.
for infinitely many 
.
for some 
(under the assumption 
)
,
,
.
,
will either divide 
.
,
,![\[\frac{f(m)}p<\frac{f(m)}{\frac23(m+p)}\le \frac{\frac43(m+p)^2}{\frac23(m+p)}=2(m+p),\]](http://latex.artofproblemsolving.com/0/6/0/060e32a6e1611609f17e5707910c26a6580c376d.png)
for 
.
,
.
(maybe 
)
.
for which 
.![\[ n^4 + n^2 + 1 = (n^2+n+1)(n^2-n+1) = f(n)f(n-1). \]](http://latex.artofproblemsolving.com/c/e/0/ce0411e51ab1868c48258e3eda722216783c7946.png)
So it suffices to show that 
is at least the larger of 
and 
infinitely often, where 
is the largest prime dividing 
is eventually strictly increasing or strictly decreasing. Since the latter is impossible for integer sequences, we only need to show this sequence cannot decrease monotonically. But 
,
is at most 
,
,
,
satisfied 
.
denote the greatest prime factor of 
.
.
cannot be monotonically strictly decreasing, since there is no infinite sequence of strictly decreasing positive integers.
we have 
.![\[\sigma(f ((N+1)^2-1)) < \sigma(f((N+1)^2)) = \sigma (f(N+1)f(N)) = \max \{\sigma(f(N)), \sigma(f(N+1))\}\]](http://latex.artofproblemsolving.com/4/d/6/4d6013cad3529029c93af7d7d57c04b3975a4764.png)
which is contradiction.
.
![\[ n^4+n^2+1=(n^2+n+1)((n-1)^2+(n-1)+1) \]](http://latex.artofproblemsolving.com/f/5/5/f552f3187c336ab344aebd0de188738ec438d90d.png)
let 
and 
.![\[ max_p(a_{n^2})\le max(max_p(a_n),max_p(a_{n-1})) . \]](http://latex.artofproblemsolving.com/0/2/c/02cac3ddbe81162db6630258754d95b0eb74ff99.png)
.
.
must be strictly increasing or decreasing (note consecutive 
can never be equal as 
for positive integers 
)
or 
for all n.
that takes the greatest prime divisor of 
as they are relatively prime. Moreover, we want to show that 
for infinitely many 
,
.
be 
.
.
.
cannot happen and it is enough to show that for all 
is not monotone. However this is easy to show with some easy inequalities, so done.
be the greatest prime divisor of 
.
And that 
So 
.
,
.
and 
then this 
.
for 
.
our claim is proved.
.
then we have our desired contradiction. Hence we may assume 
and so on. However from Claim 2 this cannot go on forever. At some point 
.
.
we want to show that there are infinitely many 
and 
.
.
.
becomes monotonic starting at some point. Note that we cannot have 
since 
by Euclidean Algorithm. It cannot be monotonically decreasing, so it must be increasing.
.
.![\[ f(g(n)g(n-1)) = \max(f(g(n)), f(g(n-1))),\]](http://latex.artofproblemsolving.com/2/a/3/2a374c6fd71b96ab16d2b4614ad82bd063dc5506.png)
which is a contradiction.
,
.![\[ f(4n^2+4n+4) > f(4n^2-4n+4), f(4n^2+12n+12). \]](http://latex.artofproblemsolving.com/0/b/5/0b5cb0745d050656b3c54eeb62a406469f94c054.png)
This becomes![\[ f((2n+1)^2) > f((2n-1)^2+3), f((2n+3)^2+3). \]](http://latex.artofproblemsolving.com/f/6/2/f62bad3576b1bb385b6ad661e8d362799ac97fdc.png)
At this point, we have reduced the problem to showing that the function 
for odd 
.
![\[n^4+n^2+1=((n-1)^2+(n-1)+1)(n^2+n+1)\]](http://latex.artofproblemsolving.com/f/4/8/f4870a6c948b52b99b3fc3ea41e0cf3602b5b959.png)
![\[(n+1)^4+(n+1)^2+1=(n^2+n+1)((n+1)^2+(n+1)+1)\]](http://latex.artofproblemsolving.com/e/3/a/e3ae82a6ef7dd1bdb7113fc7a9c39205d7fc5163.png)
we just want to find values of ![\[f(n)\ge f(n-1),f(n+1).\]](http://latex.artofproblemsolving.com/6/8/8/6882900ba227ff4c6c08b38ddb00d6c483dce622.png)
Therefore, it is enough to show that 
this is true, and we are done. 
)
infinitely often. If this were not the case, it would mean that the sequence 
.