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 divisible by 
for all positive integers 
.
and satisfying 
.
be a polynomial in one variable with integer coefficients. Prove that the number of pairs 
of positive integers such that 
, is finite.
be a cyclic quadrilateral. Assume that the points 
are collinear in this order, in such a way that the line 
is tangent to the circle 
, and the line 
is tangent to the circle 
. Let 
and 
be the midpoints of segments 
and 
, respectively. Prove that the following three lines are concurrent: line 
, the tangent of circle 
at point 
, and the tangent to circle 
at point 
.
+1 w
be nonnegative real numbers such that 
. Let 
. Prove that 
and determine when the equality holds.
from the nonnegative integers to the integers satisfying 
and ![\[ f(mn) = f(m) + f(n) + f(m)f(n) \]](http://latex.artofproblemsolving.com/e/f/f/eff10a32cffaec742403ebfc46ff09bc8ef7b7c5.png)
for all nonnegative integers and .
, an arbitrary point 
is chosen on the side 
. In triangles 
and 
, the angle bisectors 
and 
are drawn, respectively. The point 
is the circumcenter of 
. Prove that the second intersection point of the circumcircles of triangles 
and 
lies on the line 
.
be a point in the plane of triangle 
such that the segments 
, 
, and 
are the sides of an obtuse triangle. Assume that in this triangle the obtuse angle opposes the side congruent to . Prove that 
is acute.
and be two distinct rays not lying on the same line, and let 
be a circle with center 
that is tangent to ray at 
and ray at 
. Let 
be a point on segment 
. The line through parallel to intersects line at . Let be the intersection of lines 
and , and let be the intersection of line and the line through parallel to . Prove that line 
is tangent to . be an acute triangle with point 
lie on the plane such that 
is a parallelogram. 
is the orthocenter of 
intersects at 
and 
intersects at 
The circle with diameter 
intersects the circumcircle of 
again at 
Prove that: The circumcircle of 
passes through the reflection point of over 
with 
, let 
denote the incenter and the midpoint of side . The line through perpendicular to 
intersects the tangent from to the incircle (different from line ) at a point > Show that is tangent to the circumcircle of triangle 
.
and 
. At each step, it is allowed to add to one of the polynomials and to multiply another one by the polynomial 
. Can the polynomials become equal at some point?
such that for any positive integer number 
and any arrangement of the numbers from 1 to 
on a circle, there exists a pair of adjacent numbers whose ratio (when dividing the larger number by the smaller one) is less than .
make the equation ![\[\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor=\frac{n^2(n-1)}{4}\]](http://latex.artofproblemsolving.com/e/7/f/e7fb8c20a43535b5aaed5ab254f1ef043263c62b.png)
true?
be an integer, and let 
be pairwise distinct positive integers not exceeding 
. Suppose that the sequence![\[ \frac{a_1}{b_1}, \frac{a_2}{b_2}, \dots, \frac{a_n}{b_n} \]](http://latex.artofproblemsolving.com/8/5/8/858fe01a6be4b697f138d132d8fe927da6b81693.png)
forms an arithmetic progression. Prove that the terms of the sequence are equal.
be a set of 
primes. An arithmetic progression 
of positive integers is given, such that no prime in divides all terms in the progression. Then there exists 
such that 
is not divisible by any prime in .![\[ \frac{a_1}{b_1} = \frac{a+(n-1)r}{d}, \quad \frac{a_2}{b_2} = \frac{a+(n-2)r}{d}, \quad \dots, \quad \frac{a_n}{b_n} = \frac{a}{d} \]](http://latex.artofproblemsolving.com/9/9/5/995cb953f2bf4cea5e55f28325b21e5228effe0e.png)
for some positive integers 
, 
, 
with 
. Note that one can choose in such a way that 
, hence 
., by applying the lemma to the set of primes dividing . Let 
. We consider two cases.
. We claim that 
in this case. Indeed, since we only consider 
(since 
). But then ![\[ d \ge 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17^{k-6} \ge 30030 \cdot 2^{k-6} > 5 \cdot 36 \cdot 64 \cdot 2^{k-6}= 5 \cdot 36 \cdot 2^k. \]](http://latex.artofproblemsolving.com/9/f/8/9f864bfa2f78bef5880a580a82b716115aa5cc0e.png)
Hence 
, as claimed.
fractions, at least six of them have denominator divisible by , since the numerators share no common factor with . Hence one of the fractions, say the 
th one, must have denominator at least 
. The corresponding numerator is then at least ![\[ 6[a + (n-i)r] \ge 6[a + (n-6\cdot2^k)r] > 6\left[a + \frac56 n \cdot r\right] > 5n \]](http://latex.artofproblemsolving.com/f/a/0/fa0d3d4f77ed029656d2191419c2703f1c28fc0b.png)
which is a contradiction.
, but still . We claim that 
in this case. Indeed, since we only consider 
(since 
). Then ![\[ d \ge 2 \cdot 3 \cdot 5 \cdot \dots \cdot 31 \cdot 37^{k-11} > 4^{11} \cdot 25 \cdot 4^{k-11} = 25 \cdot 4^{k}. \]](http://latex.artofproblemsolving.com/5/1/9/519872c4c941b8dc142687b98e82208fc89fbf2c.png)
Then 
.
fractions, one of them is irreducible again, but then its denominator is a multiple of , despite . This is again a contradiction.
-adic lemma.
be an arithmetic progression of rational number and 
. Let 
. Then at most 
of them have 
greater of equal to 
. are integer such that 
. Then 
. Let 
and take 
. Then if 
, then
If 
then 
, contradiction to . Thus 
. Thus 
is subset of some residue class 
, implying the conclusion.
, we have 
for each 
.
then by our lemma, at most of all fractions have greater or equal to zero.
, then 
. As there are at most 
multiples of in 
, we get
, a contradiction for 
.
for each . Let 
, we split into two cases.
}
of are relatively prime to 
, these terms force 
to be multiple of . However, there are at most 
multiples of , contradiction.
for each . Thus
or 
. An integral estimation implies 
for 
. After rearranging terms, we get
, contradiction. (The computation is resonably derived by noting that 
.)
and suppose 
. Let 
. We claim the following:
for 
, then
then 
for some fixed integer .
must divide at least 
of the 's. We do this via casework on 
:
. In this case, 
. Since 
, it follows 
for all , so 
and thus divides all of the 's.
. This is equivalent to 
, or 
. Now, note that 
and 
, so we can treat this as a modular expression: 
. Then it follows 
where taking the modular inverse is defined since .
and that are equivalent to 
is less than 
, so more than 
values of do not satisfy , implying more than 
values of satisfy 
. For these values of , we have 
, so we have divides more than of the 's.'s are distinct, and there are at most 
multiples of among them, so we must have 
which implies 
. Since , we get the desired lemma. 
, so if 
then 
. Now, suppose 
and have the same denominator when simplified; that is, 
whenever . Then by CRT and the lemma above, it follows that there are at least 
residues such that we can have 
. be the denominator of when written in lowest terms. Then by the above discussion, it follows that 
for at least 
of the 's. It thus remains to bound . Now, clearly 
, so 
. Moreover, among the fractions , note that 
for at least 
of the 's. For these terms, note that 
, so it follows 
. Then 
, so 
. Thus 
, so there are at most 
multiples of between and . But for at least 
of the 's. Thus 
which is an obvious contradiction, as desired. 
to 
for large enough. Let 
; then, replacing 
with 
in the problem, and adopting the notation above, we see that if is the denominator of common difference, then for 
we must have 
, which is equivalent to 
.'s that are divisible by is at least 
, so there must be at least 
multiples of less than 
. On the other hand, we get 
so the number of multiples of less than 
is at most roughly 
. But 
while 
which gives our contradiction.
given by 
. We choose 
in such a way that 
.
(if we are done and if 
we can reverse the sequence. )
or 
if is odd, we get
must be very small. Together with the last bound on 
, we will get 
, contradicting our hypothesis that 
.
divides . Hence we must have that, since doesn't divide 
, that at most one reminder 
gives 
. The conclusion is that must divide for all but, at most, 
values of . are distinct, we must have 
(here we are counting the number of multiples of less than ). Its easy to verify that if 
is any prime or 
, then the last inequality fails. Therefore 
.
and divide simultaneously. If that happened, we can see that there are 
reminders 
such that divides when 
. With the same idea, there are two such reminders 
. Hence, for at least each of every 
consecutive , we have 
. Therefore 
(counting the multiples of less than ), which is clearly not true when .
, hence 
, contradiction. and couldn't divide at the same time was very important, since without this step we would have only proved our statement for 
.
with 
coprime with 
. So we have 
Call this 
. In particular, this means 
since coprime. have to be divisible by primes dividing and since the cant be big, itself must be small. But if is small, then the sequence grows too fast to have only small 
be the largest prime dividing . We have that 
for all 
. Suppose 
is a term such that 
and say 
. For every index such that 
, we have that 
. Since there are 
such indices, we have that among 
, we have at least 
terms divisible by . Since we have 
, there are at most 
numbers divisible by and 
, (ignore floors because the inequality works anyway), 
. So, has only prime factors 
. Say 
. Let be a prime and from , we have that 
since there's at least a 
of 
from the LHS. We will only use the fact that if 
, then 
denote the term with minimal and say then everything that is not 
has at least 
, so 
. Taking 
, we have that 
, similarly we get 
and 
. So, 
, as claimed. is small, the entire sequence 
grows too fast to have only numbers . We split into two cases:
. So, 
. Consider all the terms that are 
. There must be at least 
such terms. But for 
, we must have 
, so at most 
such terms can exist. So, 
, which is not true. .
, however, we know that at least 
of the are divisible by . So, consider terms among these which are 
. There must be at least 
such terms. The point is that since we have 
, there can be at most 
terms.
, a contradiction. 
, so the entire sequence is just constant, as desired. 
I reached my 199th post three months ago and wanted to use my 200th post for a more special problem.I believe I have found said problem. Both a very natural statement and a natural solution, a problem where trying to imagine what the final solution should look like may be in fact be detrimental. This problem took me approximately four times longer to write-up than to solve. I do not have any regrets and prefer both writing and reading solutions with motivational remarks.
and therefore one almost reduces to a "finite case check". I have tried to include as much of the motivation for the steps. Even though this is not a good way of advertising a solution, the solution below is the weakest on the thread, in the sense that if 
was replaced by 
, the proof doesn't immediately follow, we actually use the constant ! Nevertheless, I am sorry about the length of this solution but hope that you will enjoy.
for 
be the common difference, we have that 
, we are motivated consider the size constraint as a bound on the number of integers among the 
integers that are divisible by some 
, we shall therefore closely examine 
.
as we roughly have that if 
with 
and 
for 
in 
, then 
.
If 
then 
for all 
for all primes .
for 
.
If for some prime 
, there is some 
such that 
then 
.
.
.
It is not possible that 
in other words that 
.
Let us find an upper bound on depending on 
where is the length of the longest possible sequence 
such that 
is an arithmetic progression with integral common difference and 
for some 
with all 
integers distinct.
.
, we shall see if was much progress. Given the existence of any sort of bound we can get should be useful after all. for each 
write 
with 
.
. We wil analyze the case 
later.
above because the current bound of 
by 
is not sufficient as it is currently possible that 
.
and then apply our bounds to conclude the case when 
.
If 
and 
, then 
for 
, we can notice that 
as by the corollary of , we know that 
.
for some minimal and an appropriate 
and rewrite 
.
, 
.
-tuplets, 
into subsets 
contain at least 
integers such that 
this gives us the bound 
, as this bound is weaker than that we got in 
, we will analyze this inequality instead.
after rearranging this gives us that 
because 
by 
.
and 
by and , we get that 
because 
, in these cases it is easy to verify that 
, a contradiction. As mentioned before, this concludes as well. !
due to the fact that 
, we will not struggle in dealing with the case because it is a very specific case and we should intuitively be able to exploit the constant itself to improve various bounds., we will again look at sub-sequences of integral difference but this time rather than focusing on the sub-sequence 
, we will look at each of the 
sub-sequences created by starting at for 
.
and 
exhaust all possible cases for 
and due to the contradictions in each of the cases, we must have that the sequence is constant. 
(FTSOC assume that 
) where 
. WLOG assume that 
.
.
for all , so 
by induction. Now consider the set (here 
):![\[\left\{\frac{a_{s}}{b_{s}},\frac{a_{s+1}}{b_{s+1}},\dots ,\frac{a_{n}}{b_{n}}\right\}\]](http://latex.artofproblemsolving.com/b/7/1/b7121248c2efb0a6c1e36baac0ccfbc5bfb13a18.png)
and let 
. As there are 
different positive integers among 
, we get 
. Now we have the following inequality chain:![\[\frac{s-1}{d}+\frac{1}{5n}\leq \frac{j-1}{d}+\frac{1}{5n}\leq\frac{a_{j}}{b_{j}}\leq \frac{5n}{n-s+1}\]](http://latex.artofproblemsolving.com/e/3/4/e340622dac5c37b4708881361df664322b85fc21.png)
We examine two cases depending on the parity of :
is even. Then 
and the inequality above transforms into:![\[\frac{s-1}{d}+\frac{1}{10s}\leq \frac{10s}{s+1}\]](http://latex.artofproblemsolving.com/2/9/7/2977ea3da8850d661de2dfc266d498854c14457b.png)
![\[\Longrightarrow 10s(s^2-1)+(s+1)d\leq 100s^2d\]](http://latex.artofproblemsolving.com/a/c/d/acd17c77e14ea0c8c394c0b9b3424b16d8f92005.png)
![\[\Longrightarrow d\geq \frac{10s^3-10s}{100s^2-s-1}\geq \frac{s}{10}=\frac{n}{20}\geq \frac{2018}{20}>100\]](http://latex.artofproblemsolving.com/a/e/6/ae64a1cde2586ac95122a358274db068ff9823e9.png)
is odd. Then 
and the inequality above transforms into:![\[\frac{s-1}{d}+\frac{1}{10s-5}\leq \frac{10s-5}{s}\]](http://latex.artofproblemsolving.com/1/4/f/14f8a8ac47fcad0f244fda89093aef4acf3a0570.png)
![\[\Longrightarrow s(s-1)(10s-5)+ds\leq d(10s-5)^2\]](http://latex.artofproblemsolving.com/e/4/7/e47cc90b15def1d8feaa2393893832e76c082779.png)
![\[\Longrightarrow d\geq \frac{s(s-1)(10s-5)}{(10s-5)^2-s}\geq \frac{s-\frac{1}{2}}{10}=\frac{n}{20}>100\]](http://latex.artofproblemsolving.com/2/8/6/2868c75a164e0d3334c6f9d6688990f4366667cf.png)
We got that 
in both cases, so we're done. Now because 
we can write 
.
for all .
for some prime 
. Then at least 
of the simplified fractions have a denominator divisible by . Indeed, in the set 
at most one fraction has a denominator not divisible by . If we assume otherwise, that means that there exist 
such that doesn't divide the denominator in the simplified fractions 
and 
, so:![\[0\leq \min\left\{v_{p}\left(\frac{a_{j_{1}}}{b_{j_{1}}}\right), v_{p}\left(\frac{a_{j_{2}}}{b_{j_{2}}}\right)\right\}\leq v_{p}\left(\frac{a_{j_{1}}}{b_{j_{1}}}-\frac{a_{j_{2}}}{b_{j_{2}}}\right)=v_{p}\left(\frac{c(j_{2}-j_{1})}{d}\right)=\]](http://latex.artofproblemsolving.com/a/e/3/ae3d0492d76ce0fd4fbf55247603a97a431ee107.png)
![\[=v_{p}(c)+v_{p}(j_{2}-j_{1})-v_{p}(d)=-v_{p}(d)<0\]](http://latex.artofproblemsolving.com/6/f/3/6f362c289fe252db765149cf5e69ff1965b512bf.png)
as , 
and 
. Therefore there are at most 
of those simplified fractions which don't have a denominator divisible by . Now, the fractions which have a in their simplified denominator must have 
. However, there are only 
such integers between and inclusive, therefore:![\[n-\left\lceil\frac{n}{p}\right\rceil\leq \left\lfloor\frac{5n}{p}\right\rfloor\]](http://latex.artofproblemsolving.com/2/0/f/20f91114ef34fc81363a8ab315d48dde62294630.png)
Using the weak inequalities 
and 
we get:![\[n-\frac{n}{p}-\frac{p-1}{p}\leq n-\left\lceil\frac{n}{p}\right\rceil\leq \left\lfloor\frac{5n}{p}\right\rfloor\leq \frac{5n}{p}\]](http://latex.artofproblemsolving.com/d/1/c/d1c9f15967c6093bbae674c30f8cf73ab8b3163a.png)
![\[\Longrightarrow 0\leq (6-p)n+p-1\]](http://latex.artofproblemsolving.com/1/2/6/126ab6a3260cc29469a44c744123a3ade01071e5.png)
However, , so 
and thus we have:![\[(6-p)n+p-1\leq (6-p)2018+p-1=12107-2017p\leq 12107-7\cdot 2017=-2012<0\]](http://latex.artofproblemsolving.com/9/b/4/9b40ff81c317cf3d2398210b106553af19d20321.png)
which is a contradiction with out assumption, so the proof is complete.
. Note that from the first claim we know that 
, so we must have 
, 
or 
as otherwise 
. We consider the following three cases:
. Then at least 
of the simplified fractions have a denominator divisible by . Indeed, in the set 
at most one fraction has a denominator not divisible by 
. If we assume otherwise, then doesn't divide the denominators in the simplified fractions 
and 
, so:![\[-3\leq \min\left\{v_{2}\left(\frac{a_{i}}{b_{i}}\right), v_{2}\left(\frac{a_{i+1}}{b_{i+1}}\right)\right\}\leq v_{2}\left(\frac{a_{i}}{b_{i}}-\frac{a_{i+1}}{b_{i+1}}\right)=v_{2}\left(\frac{c(i+1-i)}{d}\right)=\]](http://latex.artofproblemsolving.com/2/c/5/2c5734bfd4ab5b11cdbb93d21fba32917aba95ea.png)
![\[=v_{2}(c)-v_{2}(d)\leq -4\]](http://latex.artofproblemsolving.com/e/e/5/ee50b3c9c99e14fa92cbc78c08babd03cee3079e.png)
as 
, 
. Therefore there are at most 
of those simplified fractions which don't have a denominator divisible by . Now, the fractions which have a in their simplified denominator must have 
. However, there are only 
such integers between and inclusive, therefore:![\[n-\left\lceil\frac{n}{2}\right\rceil\leq \left\lfloor\frac{5n}{16}\right\rfloor\Longrightarrow n-\frac{n}{2}-\frac{1}{2}\leq n-\left\lceil\frac{n}{2}\right\rceil\leq \left\lfloor\frac{5n}{16}\right\rfloor\leq \frac{5n}{16}\Longrightarrow 3n\leq 8\]](http://latex.artofproblemsolving.com/d/2/e/d2e2b6b2c706163d5ba3db75a368686656f3cf30.png)
However, 
, so this is obviously wrong.. Then at least 
of the simplified fractions have a denominator divisible by 
. Indeed, in the set 
at most one fraction has a denominator not divisible by . If we assume otherwise, that means that there exist 
such that doesn't divide the denominator in the simplified fractions and , so:![\[-1\leq \min\left\{v_{3}\left(\frac{a_{j_{1}}}{b_{j_{1}}}\right), v_{3}\left(\frac{a_{j_{2}}}{b_{j_{2}}}\right)\right\}\leq v_{3}\left(\frac{a_{j_{1}}}{b_{j_{1}}}-\frac{a_{j_{2}}}{b_{j_{2}}}\right)=v_{3}\left(\frac{c(j_{2}-j_{1})}{d}\right)=\]](http://latex.artofproblemsolving.com/3/e/c/3ec915e9b67c0a1d642dd45a04088c936076beb8.png)
![\[=v_{3}(c)+v_{3}(j_{2}-j_{1})-v_{3}(d)\leq -2\]](http://latex.artofproblemsolving.com/c/e/8/ce8074770cf14a1e8f62f0686307a35113eb7252.png)
as 
, 
and 
. Therefore there are at most 
of those simplified fractions which don't have a denominator divisible by . Now, the fractions which have a in their simplified denominator must have 
. However, there are only 
such integers between and inclusive, therefore:![\[n-\left\lceil\frac{n}{3}\right\rceil\leq \left\lfloor\frac{5n}{9}\right\rfloor\Longrightarrow n-\frac{n}{3}-\frac{2}{3}\leq n-\left\lceil\frac{n}{3}\right\rceil\leq \left\lfloor\frac{5n}{9}\right\rfloor\leq \frac{5n}{9}\Longrightarrow n\leq 6\]](http://latex.artofproblemsolving.com/3/3/6/3364698b2e5819b49075e57e1244f4ade6e216d2.png)
However, , so this is obviously wrong.. Then at least 
of the simplified fractions have a denominator divisible by 
. Indeed, in the set 
at most one fraction has a denominator not divisible by . If we assume otherwise, that means that there exist 
such that doesn't divide the denominator in the simplified fractions and , so:![\[-1\leq \min\left\{v_{5}\left(\frac{a_{j_{1}}}{b_{j_{1}}}\right), v_{5}\left(\frac{a_{j_{2}}}{b_{j_{2}}}\right)\right\}\leq v_{5}\left(\frac{a_{j_{1}}}{b_{j_{1}}}-\frac{a_{j_{2}}}{b_{j_{2}}}\right)=v_{5}\left(\frac{c(j_{2}-j_{1})}{d}\right)=\]](http://latex.artofproblemsolving.com/5/0/7/507b9eb240854e13a29fa8e544419fe1fd77b8b1.png)
![\[=v_{5}(c)+v_{5}(j_{2}-j_{1})-v_{5}(d)\leq -2\]](http://latex.artofproblemsolving.com/e/2/4/e24e4185ad9f395b2aaa48efd03527d0a25effb8.png)
as 
, 
and 
. Therefore there are at most 
of those simplified fractions which don't have a denominator divisible by . Now, the fractions which have a in their simplified denominator must have 
. However, there are only 
such integers between and inclusive, therefore:![\[n-\left\lceil\frac{n}{5}\right\rceil\leq \left\lfloor\frac{n}{5}\right\rfloor\Longrightarrow n-\frac{n}{5}-\frac{4}{5}\leq n-\left\lceil\frac{n}{5}\right\rceil\leq \left\lfloor\frac{n}{5}\right\rfloor\leq \frac{n}{5}\Longrightarrow 3n\leq 4\]](http://latex.artofproblemsolving.com/5/f/1/5f13f0643b5e29c2ad9c739c6df24ac38c945937.png)
However, , so this is obviously wrong.
, 
, 
. If any of these inequalities isn't an equality, then 
, so we must have 
. However, now we do the same trick for :
and 
. Then at least of the simplified fractions have a denominator divisible by . Indeed, in the set at most one fraction has a denominator not divisible by . If we assume otherwise, that means that there exist such that doesn't divide the denominator in the simplified fractions and , so:![\[0\leq \min\left\{v_{15}\left(\frac{a_{j_{1}}}{b_{j_{1}}}\right), v_{15}\left(\frac{a_{j_{2}}}{b_{j_{2}}}\right)\right\}\leq v_{15}\left(\frac{a_{j_{1}}}{b_{j_{1}}}-\frac{a_{j_{2}}}{b_{j_{2}}}\right)=v_{15}\left(\frac{c(j_{2}-j_{1})}{d}\right)=\]](http://latex.artofproblemsolving.com/e/3/a/e3a2e80b5d3066f820d364e927192e43a6d32807.png)
![\[=v_{15}(c(j_{2}-j_{1}))-v_{15}(120)=-1\]](http://latex.artofproblemsolving.com/3/7/9/3795193c078e98166879d9dd3f9a3e5e1ddd0016.png)
as 
, 
and 
. Therefore there are at most of those simplified fractions which don't have a denominator divisible by . Now, the fractions which have a in their simplified denominator must have 
. However, there are only 
such integers between and inclusive, therefore:![\[n-\left\lceil\frac{n}{3}\right\rceil\leq \left\lfloor\frac{n}{3}\right\rfloor\Longrightarrow n-\frac{n}{3}-\frac{2}{3}\leq n-\left\lceil\frac{n}{3}\right\rceil\leq \left\lfloor\frac{n}{3}\right\rfloor\leq \frac{n}{3}\Longrightarrow n\leq 2\]](http://latex.artofproblemsolving.com/6/2/d/62d119c3d236568eaf74d37348a66125f5e03b3c.png)
However, , so this is obviously wrong.
.
-adic structure of arithmetic progressions.
be an arithmetic progression with common difference . If is a prime and 
, then every term of the sequence has a -adic valuation of or exactly one of every consecutive terms has a -adic valuation other than .
, then all terms of the sequence have a -adic valuation of 
. If 
, then 
exists and is nonzero modulo . Thus, 
forms a complete residue class modulo , so exactly one of ![\[p^{-\ell} c_i,p^{-\ell} c_i+p^{-\ell} d,\ldots,p^{-\ell} c_i+(p-1)p^{-\ell} d\]](http://latex.artofproblemsolving.com/9/9/1/99135b46a8c512cd66f94a033d9341af5e2ea0ef.png)
is divisible by for 
. It follows that exactly one of 
has a -adic valuation not equal to 
. , let 
be the value of for the sequence 
given Claim 1.
, 
, 
, and 
for primes . with 
, at least 
terms of 
are divisible by 
by Claim 1. Since there are at most 
positive multiples of not exceeding , we have 
. This is equivalent to ![\[\left(\frac{p-1}{p}-\frac{5}{p^{-k_p}}\right)n \le 1.\]](http://latex.artofproblemsolving.com/8/9/6/8966526ad427deaa0c96de12b2faba34a49aaac5.png)
Notice that
, 
gives 
, 
gives 
, gives 
, 
gives 
,, we deal with an edge case.
.
instead of a prime power. Assume FTSOC that 
. By Claim 1, at least 
of every 
consecutive terms have a 
-adic valuation of 
, a -adic valuation of 
, and a -adic valuation of . This means there are at least 
indices such that is divisible by . We also have an upper bound of 
positive multiples of not exceeding , so we have 
, a contradiction. 
be the common difference of when written in lowest terms. Assume WLOG that 
, and assume FTSOC that 
. Claim 2 gives 
and Claim 3 gives 
, so we have 
. Notice that at least one of 
is at least 
and 
for 
. Therefore, at least one of 
is at least ![\[\frac{n}{2} \cdot \frac{\frac{n}{2}-1}{60} \ge \frac{n}{2} \cdot \frac{\frac{n}{3}}{60}=\frac{n^2}{360}>5n,\]](http://latex.artofproblemsolving.com/5/a/8/5a85bf9517e71558a74d3cb3f3f8575c26ea9a06.png)
a contradiction. Thus, we must have , as desired. 
and the common difference of the arithmetic progression be .
is an integer.
, and 
for all primes 
. Suppose for some this wasn't true (as in 
if 
, etc).
.![\[\nu_p(r_1) = \nu_p(r_2) = \cdots = \nu_p(r_n) < \nu_p(d)\]](http://latex.artofproblemsolving.com/f/a/6/fa631b2e99015552b21341df7a1497a69c9d1e2d.png)
Thus, must be divisible by 
for each . Since the are pairwise distinct, we must have 
be at most (or else one of the would exceed ), so 
. Now if 
, we must have that 
, so . If , then 
can't exceed , so 
, as desired.
. at least equal to 
. consecutive terms of the arithmetic sequence, say 
. Notice that if any two had a greater than , then by subtracting them, we get a contradiction as their difference is times a non multiple of . consecutive terms of the arithmetic sequence, at most one of them has a greater than . This implies that at least 
numbers in the arithmetic sequence have a equal to that of . of 
are multiples of 
, so at least one of them is at least 
, implying that![\[ p^{ - \nu_p(d) } \cdot \left(n - \frac np - 1 \right) < 5n \]](http://latex.artofproblemsolving.com/a/4/f/a4fbd2d630adb2723eeed19e9a2b2b55e8e75ef1.png)
The LHS is equal to 
, so the inequality rearranges to![\[ n \left( p^{ - \nu_p(d)} - p^{- \nu_p(d) - 1} - 5 \right) < p^{- \nu_p(d)} \]](http://latex.artofproblemsolving.com/e/0/0/e00067ae116c6f6369423a0c151efb1f62cd34db.png)
Now let 
. Assume 
as otherwise the claim would obviously be true. Now we claim that the LHS must be negative. If not, we would have that 
. But the reciprocal of this expression is 
and must be less than 
. If , then since 
, 
. Now if 
, then since 
, we have 
. Otherwise, if , then 
.
, so 
., we have 
, so 
, contradiction. If , then 
, so 
, meaning that 
. If 
, then 
, so , so 
. If , then 
, so 
, meaning 
, as desired. 
and 
is nonnegative.
. Recall that if , then 
, which is impossible for 
in this case. Hence for 
. We copy this again (for any prime with 
): consecutive terms of the arithmetic sequence, say . Notice that if any two had a greater than , then by subtracting them, we get a contradiction as their difference is times a non multiple of . consecutive terms of the arithmetic sequence, at most one of them has a greater than . This implies that at least 
numbers in the arithmetic sequence have a equal to that of .
numbers in the sequence have a 
over and at most 
numbers in the sequence have a 
over , implying that at least 
numbers in the sequence have a and equal to . Hence these numbers must have a denominator divisible by , so at least 
of the are multiples of , which means some is at least 
(for ), absurd. is written as a simplified fraction of two integers (since is nonzero), the denominator is a divisor of , but not a multiple of , so it is at most 
. Hence 
.
. Notice that at least one number in 
is at least 
. Let 
for some ![$k\in [m,n]$](http://latex.artofproblemsolving.com/9/e/3/9e372d589691176bd259534fabf4dc05105cdb9e.png)
. We have 
, so the common difference of the sequence is![\[d = \frac{r_k - r_1}{k - 1 } < \frac{r_k}{m - 1} < \frac{5n}{(n - m + 1) (m-1)} \]](http://latex.artofproblemsolving.com/f/3/0/f30a04e378f98243c9e5d492299d6d0924f57375.png)
Now if is even, let 
, so 
and 
. The value of is at most![\[ \frac{10t}{(t + 1)(t - 1)} < \frac{10(t+1)}{(t+1)(t-1)} = \frac{10}{t-1} < \frac{10}{1008} , \]](http://latex.artofproblemsolving.com/c/e/4/ce42f1b3940c0c97fd3ce1ac3f71a24820c1bf48.png)
which is much less than 
, absurd. is odd, let 
, where 
and . The value of is at most![\[ \frac{10t - 5}{t(t-1)} < \frac{10t}{t(t-1)} = \frac{10}{t-1} < \frac{10}{1009},\]](http://latex.artofproblemsolving.com/0/c/6/0c607e3dc28a86a8e443732610290234eb23f481.png)
which is much less than , absurd.
can be improved to 
be the common difference with and assume 
, and let 
and 
.![\[\frac{a_i}{b_i}+\frac{c}d(j-i) \iff c(j-i)b_ib_j=d(a_jb_i-a_ib_j) \implies d \mid (j-i)b_ib_j \implies d \mid b_ib_{i+1} \left(\clubsuit \right)\]](http://latex.artofproblemsolving.com/5/6/0/560d28780e74b2414dcd9a62a3629f58476177ac.png)
Claim: We have 
.
and 
and so ![\[p^e \mid b_ib_{i+1} \implies p^{\left \lceil \frac{e}2 \right \rceil} \mid \text{lcm}(b_i,b_{i+1}) \]](http://latex.artofproblemsolving.com/4/f/f/4ff27705f8114ab63fdc51b7664c39f0a868d0be.png)
And so there are minimum 
multiples of 
among and hence ![\[p^{\left \lceil \frac{e}2 \right \rceil} \left(\frac{n-1}2 \right) \leq 5n\]](http://latex.artofproblemsolving.com/5/b/8/5b8f19851c6dc61439678f29138919ab25050ccc.png)
And now by some trivial size observations we are done. .
.
. Now we have ![\[\nu_7(b_i)+\nu_7(b_{i+1})=\nu_7(d)+\nu_7(a_{i+1}b_i-a_ib_{i+1})\]](http://latex.artofproblemsolving.com/1/2/7/127c82822f5a038e76080dcd9f8ac0d7c4fdb7be.png)
And hence if there exists such that 
, then 
but 
. multiples of 
among elements in . Again this means we get ![\[49 \left(\frac{n-1}2 \right) \leq 5n\]](http://latex.artofproblemsolving.com/3/1/0/310a3be2164887e9f50918c223440cd189e775e2.png)
and contradiction.
, 
and 
. 
.
. Since 
, and so if 
for some then ![\[\ell \equiv k \pmod 7 \text{ for all } 7 \nmid b_{\ell}\]](http://latex.artofproblemsolving.com/9/e/a/9ea9f19d6c3b892f793bd8bdf804a34d8a374b33.png)
And hence there are atmost 
non multiples of 
among and hence there are atleast 
multiples of among . And hence ![\[7 \left(\frac{6n}7-1 \right) \leq 5n\]](http://latex.artofproblemsolving.com/d/f/d/dfd19c63b9d121fb6277e84884f966816b373d16.png)
and again contradiction. 
.
.
Finding such that 
. Say 
. Then 
for all 
.
non-multiples of among . Finding such that 
. Say for some and 
we have 
and 
. Then now referring to the main equation in 
, we get that 
but 
, contradiction.
elements among with -adic evaluation as .![\[n-\left \lceil \frac{n}3 \right \rceil-\left \lceil \frac{n}9 \right \rceil \geq \frac{5n}9-1 \text{ multiples of $9$ among $B$}\]](http://latex.artofproblemsolving.com/7/b/3/7b39333e30b85bd78bcf46ae2c3923c6e6483e21.png)
But see that there maximum 
multiples of among 
. And hence there is maximum multiple of among .
for some , such that 
And again referring to the main equation in , we get that ![\[\nu_3(\text{LHS}) \geq 2\nu_3(b_i)+2 \text{ but } \nu_3(\text{RHS}) \leq \nu_3(b_i)+3\]](http://latex.artofproblemsolving.com/2/6/8/268d19beba62cee4687f2dafb948ca1042164cfb.png)
which is a contradiction. multiplies of in , then for 
of those numbers we have that their -adic evaluation can be one of two consecutive fixed numbers (which must be and or else size issues), and hence there are maximum multiples of 
among 
, which is obviously false. ![\[d \mid 2^3 \cdot 3 \cdot 5=120\]](http://latex.artofproblemsolving.com/c/3/1/c312b92028714579f15250eeb38bdac588abb195.png)
Now we take two cases. If 
. See that we have ![\[\frac{a_i}{b_i} \geq \frac{i-1}{60} \implies \frac{a_n}{b_n} \geq \frac{n-1}{60} \geq 32\]](http://latex.artofproblemsolving.com/4/3/d/43d1343148e0a36edebbd46f4f6fb8202359da1b.png)
See that there is minimum 
numbers such that 
, and say 
is the maximum of those numbers and we get that ![\[5n \geq a_T>10b_T \geq 10(n-600) \implies n<1200\]](http://latex.artofproblemsolving.com/f/2/5/f2516cc73a1b7a5491f44e74806ef550c34a6295.png)
which is a contradiction. If 
. See that we must have 
and so 
; and![\[\frac{a_i}{b_i} \geq \frac{i-1}{120} \implies \frac{a_n}{b_n} \geq \frac{n-1}{120} \geq 16\]](http://latex.artofproblemsolving.com/b/0/9/b09a907f77d82f2cca71599898c13310f2ef2c09.png)
Now using similar arguments before we get that if we look at the set of indices , such that 
, then the set of for which 
must be in the same residue class modulo and hence there atleast ![\[\left \lfloor \frac45 (n-240) \right \rfloor\]](http://latex.artofproblemsolving.com/5/d/1/5d1b992a381272e6535b1bc1268dd50767d249a8.png)
indices in set of such of such that 
. Let be the maximum of them all and we get ![\[5n \geq a_T \geq 2b_T \geq 2(4(n-240)-5) \implies n \leq 644\]](http://latex.artofproblemsolving.com/3/0/6/306148bf3aac142c3326948732f88c0bac55d268.png)
which is a contradiction, and we are done.
, if for some prime we have that 
then either there's 
terms of the sequence satisfy 
. Or all terms are below this .
for all 
and 
, now let the difference of this sequence then if 
we get 
, now if then the minimun is no longer 
therefore we must have 
so such numbers are closed in a residue system 
which is enough to prove the Lemma.
for 
being an odd prime power then 
for all 
, from the lemma we know that at most 
terms of the sequence have non-negative so at least 
terms have negative which means that for any such we must have 
, now since we have that there's at most 
multiples of among all the 's which gives:
The last thing is clearly a contradiction, but this works for 
and , now otherwise use the lemma on 
then we have that at least 
terms have their on the minimun, but there's at most 
such terms, therefore if 
for 
we obtain our desired contradiction. we have that 
for all using the same method as above.
then we would also get that 
for being the difference in the sequence. So now if we had that 
for all terms in the arithmetic sequence and even 
, it would turn out that we need multiples of but we can only get at most 
which is a contradiction for , therefore either way 
, now WLOG the sequence is strictly increasing (assume FTSOC 
) which means that 
, now among any consecutive 
terms in the 's we have that one of them is greater or equal to , so we pick one such from 
and just note that:
Therefore it turns out that 
so the sequence is constant thus we are done 
.
are congruent modulo p.\ such that 
and 
and 
mod p.![\[\nu_{p}((i-j)\frac{a}{b}) = \nu_{p}(\frac{a_i}{b_i} - \frac{a_j}{b_j}) \geq \min\{ \nu_{p}(\frac{a_i}{b_i}),\nu_{p}(\frac{a_j}{b_j})\} \]](http://latex.artofproblemsolving.com/3/d/c/3dc26c31049ce66932f218d6fe6b48be279c1534.png)
But this works only when 
mod p as the least common denominator is not divisible by 
contradiction. are at most 5.
such vertices are there that have vp(b) > vp(b_i). so at least 
does not satisfy the given condition. Then assume contrary and we get![\[ 5n \geq \max\{b_i :p|b_i\} \geq ((\frac{p-1}{p})n -1)p = (p-1)(n-1) -1 \geq 6(n-1)-1 > 5n\]](http://latex.artofproblemsolving.com/b/2/2/b22c5cac01ab51084824db8927221b36455b6f95.png)
such that 
then the rest must at most 
, then this just gives us that 
done![\[5n > \max\{b_i: d|b_i\} > (\lceil \frac{n}{30} \rceil \cdot 8)\cdot b > (\lceil \frac{n}{30}\rceil \cdot 8)\cdot \frac{n-2}{20} > 5n\]](http://latex.artofproblemsolving.com/5/1/7/5171763768070aa00f31db679c62175d9874c6e5.png)
can be improved to 
by taking things 
instead of 
have denominator 
We must have 
for all 
or 
by pigeonhole. By pairing the 
.
and at most 
.
.
for any 
distinct divisors, so some 
for some 
for all 
then this would imply the largest 
which is a contradiction. Hence we have the following cases:
is a multiple of 
.
are in this list, when it was required that 
is constant. This is contradiction.
for all 
for all 
only has at most 
distinct divisors, which is not enough for 
.
for all 
has at most 
distinct divisors, there is not enough for all 
giving contradiction. So we are done.
denote the number of distinct prime divisors of 
denote the number of positive divisors of 
denote the exact power of 
as 
and 
,
meaning that 
,
,
,
which is not the case for 
,
then we have that 
and similarly 
which means that 
for all 
,
meaning that 
for all 
which are 
,
,
for all 
where 
,
.
such that 
,
where because 
as well.
and 
for some 
such that for each 
if 
we have there exists 
such that 
,
which does not hold for 
,
and lower bound 
possible values of 
.
where 
therefore for all 
we have 
such that 
and 
where 
for all 
we have some positive integer that is at least 
we therefore have to maximize 
where 
,
which is not all that random after all considering that the bound is attained using backwards.
and notice that there is an 
and therefore 
rearranging we get the desired inequality, that is 
form an arithmetic progression of integral difference as 
,
Now define 
,
meaning that 
.
therefore if 
we must have that 
by rearranging 
case by noting that 
means that 
and again 
.
case by firstly noting that 
and that if 
,
and we can therefore conclude that 
.
which immediately implies the result because then 
.
.
divide 
.
for 
,
.
,
which doesn't hold for 
,
when 
for all 
,
The next idea is the real main idea of the problem. The previous ideas were, of course, necessary and deserved their place in this post, but the following is surprisingly simple, yet powerful. Also, it makes it seem like one is doing some ad-hoc combinatorics rather than an N7.
,
is almost fixed.
.
for 
as 
meaning that when the 
will be relatively prime to 
.
,
distinct values of 
.
,
for all 
,
,
,
and similarly if 
then 
which again means that 
and if 
,
and if 
,
as 
and 
.
,
which can again be dealt with using a similar method as 
as 
for all 
,
.
and 
for some 
,
meaning that among said integers for exactly 
,
,
and therefore 
.
for which our bound will be weaker but we will still be able to conclude; this will therefore resolve 
where 
,
,
,
,
,
,
which is a contradiction as we will have some 
which is not possible because all the fractions must have equal 
.
for all 
,
we must have two different indices 
,
and 
for some 
such that 
,
.
and 
,
,
and 
,
to be such that 
where 
are all distinct.
and 
.
such that 
,
is achieved at 
where 
,
Then, if we define 
for which 
and is thus increasing for 
.
by 
,
is a contradiction, as desired. 
integers that are divisible by 
in relation to the common difference. Moreover, the additive nature allows us to bound 
,
to 
in Lemma 5), I concluded that 
more divisors of 
that we have to check for 
which will allow us to extract 
and then simply writing 
in the sense that here the variables and their 
are a lot more free. When we rewrite the sequence in the so called "natural-way" we can look at 
and notice that if 
then 
for all 
more closely and see how the numerator cycles 
and using the fact about the behaviour when 
,
.
and therefore we can only really get useful bounds if 
and we must therefore deal with this case. When solving the problem, I actually noted after completing the 
using PHP but assumed again that it was only eliminating only 
,
for all 
.
whereas I go for the weakest possible bound achieved by Lemma 2, that is 
,
be the common difference where 
.
.
.
multiples of ![$[1,5n]$](http://latex.artofproblemsolving.com/1/3/8/138f249d090d68ebd81a35555c923dfe2334a677.png)
.
of the denominators must be divisible by 
by noting a prime 
doesn't work because 
of the denominators are divisible by 
and the common difference is at least 
.
.
then 
.
it follows that 
,
.
,
where 
for 
.
then 
then 
for 
.
Since 
because 
,
.
and 
so 
then 
.
If 
since 
.
of the 
,
and there are at most 
distinct numbers between 
equal to the number of good positive integers less or equal to 
where 
equal to the number of good 
such that 
for each 
for 
.
for good 
so if we write 
,
for their respective prime. Therefore there are 
choices for each exponent of 
,
since 
for large 
where we take 
.
for 
,
,
for all