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 such that number 
has exactly 
positive divisors. Prove that GCD 
be a triangle inscribed in a circle 
with orthocenter 
and altitude 
. Let 
be the midpoint of 
. Line 
meets again at 
. Line 
meets again at 
. Let 
be the orthogonal projection of 
on the line 
. Line 
meets again at 
. Prove that 
.
![\[
\int_0^1 \int_{x^2}^x (x^2 + y^2)^{-1/2} \, dy \, dx
\]](http://latex.artofproblemsolving.com/e/a/9/ea9f3a093b1d4c0fa39e5b6d42afa2f71dace1e0.png)
has no roots in the disc of unity.
consecutive even numbers, such that the sum of their squares divides the square of their product.
satisfying 
, find the biggest value the following equation could acquire:
and 
on 
and 
respectively in 
such that 
then draw line 
through 
such that 
let 
and 
reflection of 
and to respectively prove that 
and are congruence.
be a set of 
distinct integers all of whose prime factors are at most 
Prove that contains 
distinct integers such that their product is a perfect cube.
such that
for all 
.
modulo 
and use pigeonhole principle, and extend both forwards and backwards by 1 step but then I hand-waved by saying that "inductively they will all be periodic" (I did 3 inductions before that smh)
will imply the presence of the terms in the form 
which in turn implies the presence of the terms in the form by substituting variables 
into 
and 
into 
").
modulo and use pigeonhole principle, and extend both forwards and backwards by 1 step but then I hand-waved by saying that "inductively they will all be periodic" (I did 3 inductions before that smh)
for 
, I didn't think of using the Pigeonhole Principle. Also, I have excluded the case where 
. How many points can I possibly get?
be the th Chebyshev polynomial, which is the unique polynomial such that 
. Its existence is well known, so we won't prove it here, but the idea is to show by induction that 
and 
are polynomials in 
. We'll need to use the fact that 
has all of it's roots of the form for some real 
, so let's show that right now. It is known that the degree of is , so all we have to do is provide distinct roots of the form . It is easy to check that![\[\cos\left(\frac{\pi}{2n}+\frac{k}{n}\pi\right)\]](http://latex.artofproblemsolving.com/b/9/d/b9d822c61c5bea9d7ce19585f196bb29645841c2.png)
where 
is an integer all work. These are distinct as the arguments are distinct real numbers in 
, and the cosine function is injective on .
for some , then 
where 
is the th Fibonacci number. This is clear for 
, and we see that![\[x_{n+1}=2\cos(F_n\theta)\cos(F_{n-1}\theta)-\cos(F_{n-2}\theta).\]](http://latex.artofproblemsolving.com/5/7/b/57b7a561e86be3d423f736eb6a42ff3bebd23996.png)
We have by product to sum that![\[2\cos(F_n\theta)\cos(F_{n-1}\theta)=\cos((F_n+F_{n-1})\theta)+\cos((F_n-F_{n-1})\theta)=\cos(F_{n+1}\theta)+x_{n-2},\]](http://latex.artofproblemsolving.com/a/6/d/a6d08fb9146aad232f7b21b73ca2fe8c6ca4efa6.png)
thus showing that 
.
. It is clear from the recurrence that 
is some fixed polynomial in 
, and we have from above that and 
coincide for infinitely many values of , so they are in fact the same.
. Since all the roots of Chebyshev polynomials are cosines, we have some real such that and 
. This implies that is a rational multiple of 
, so can only take finitely many values. Thus, by pigeonhole principle, there are some two distinct and 
such that![\[(x_{n-2},x_{n-1},x_n)=(x_{N-2},x_{N-1},x_N).\]](http://latex.artofproblemsolving.com/8/6/2/86229ae4cd270be7143886325ca3c9a257416625.png)
The given recurrence then shows that is periodic.
, we define a sequence by 
, 
, and 
for 
. Prove that if 
for some , then the sequence is periodic.
denote the 
Chebyshev polynomial. Let 
be the Fibonacci number, where 
and 
for all .
.
.
, since 
and 
.
for a fixed constant 
. Therefore,
and therefore, we are done by induction.:
, then there exists 
such that 
. Therefore, by assumption, there exists such that![\[ T_{F_i}(a) = 0 \implies T_{F_i}(\cos(\theta)) \implies \cos(F_i \theta) = 0 \]](http://latex.artofproblemsolving.com/7/8/9/7893b268ef20ef0451610840e87954afa5f016c2.png)
Therefore, 
for some 
. However, note that Fibonacci numbers are periodic modulo , i.e. there exists such that 
for all 
. This is because there are finitely possible residue for 
. Now, we claim that 
is also periodic. Indeed, note that![\[ \cos(F_{a + N} \theta) = \cos(F_a \theta) \ \text{for all } a \in \mathbb{Z}_{\ge 0}. \]](http://latex.artofproblemsolving.com/2/9/e/29e1e0bbfeb6a8e876e9954cf0dc76de9b0db682.png)
, then there exists 
such that 
. Therefore, by assumption, there exists such that![\[ T_{F_i}(a) = 0 \implies T_{F_i} \left( \frac{x + x^{-1}}{2} \right) = 0 \implies \frac{x^{F_i} + x^{-F_i}}{2} = 0 \implies (x^{F_i})^2 + 1 = 0 \]](http://latex.artofproblemsolving.com/3/3/1/3319822e7d53090f6192fddd7efc87148eaa8174.png)
However, since 
, this has no solution.
denote the -th Chebyshev polynomial, so we have 
and 
. I now claim that 
for all , where is the Fibonacci sequence with 
. This is simply due to sum-to-product: we have![$$\cos(F_{n+1}\theta)+\cos(F_{n-2}\theta)=2\cos(F_n\theta)\cos(F_{n-1}\theta) \implies T_{F_{n+1}}(x)+T_{F_{n-2}}(x)=2T_{F_n}(x)T_{F_{n-1}}(x)~\forall x \in [-1,1],$$](http://latex.artofproblemsolving.com/1/5/1/1514c821bb59113ff9aaeb3bda5a6635babe1a92.png)
and since the latter equation is a polynomial identity, it follows that the two polynomials are equal.
, where 
can be complex. Then 
for all 
. Then, if 
for some , we must have 
for some (since even in 
, these are the precise roots of cosine). It is well-known that the Fibonacci numbers are periodic modulo any fixed integer (by the typical pigeonhole argument), so the Fibonacci times is periodic "modulo 
" as is a rational multiple of , so we're done. 
and 
so 
and 
.
so 
.
. This is true by induction because
for some , then must be a rational multiple of . It is well known that the Fibonacci sequence is periodic modulo any positive integer, so the sequence is periodic, as desired.
, let 
. The following term is 
, where is the nth Fibonacci number.
. It is true for 
.
, then 
for integers 
, 
. Note Fibonacci sequence module any integer is periodic, so this sequence must be periodic as well.
, the degree of the polynomial was 5, which suggested Fibonacci.
or 
, it is can be trivially proved that the sequence 
will be strictly increasing and approach infinity, meaning that it won't ever be periodic. If 
, we can use substitute 
., the sequence will satisfy 
for all , where is defined as the 
Fibonacci Number.
. Using our inductive hypothesis, we can write
where the second equality is from Product-to-Sum Formula. ., then 
for some rational . Because Fibonacci Numbers are periodic for all modulos of a positive integer, the sequence must also be periodic. 
I claim that if 
the sequence is non-decreasing for 
Proof is by induction. Hence, we only need to consider the case 
Make the substitution 
. I claim that for 
we have that 
We prove this via induct. Base cases are easy. 
from angle addition. Note that is also periodic. We also know that is a rational multiple of for . Thus, we are done.
.
with 
.
(where 
be a (complex) solution to 
.
.
,
and 
.
be a period for the Fibonacci sequence modulo 
(it is well-known such 
is periodic with period 
defined by 
,
and 
.
(which allows the assumption from 1).
)
.
.
and 
,
and 
.
,
and 
.
.
for all 
