AoPS Academy
. Let 
be its incenter, 
be its 
-excenter, 
be midpoint of arc 
, 
is the midpoint of 
.
be the intersection of the line 
with 
, 
be the intersection of the angle bisector of 
with the line .
,the intersection of line 
with 
and 
,the intersection of 
and 
such that 
. Ana wins if the points 
are collinear. Who has a winning strategy?
and let 
be positive integers such that 
. Prove that 
and determine when equality holds.
+1 w
different ropes. She then performs a experiment that causes 
children, each connected to each other with the same type of rope, to be cured. Two experiments are said to be of the same type, if each of the ropes connecting the children has the same medicine imbued in it. She then unties them and lets them go back home.
be the minimum m such that Myla can perform at least 
experiments of the same type. Prove that:
For every 
there exists a 
and 
such that for all 
, ![\[f(n, k) = a_kn + b_k.\]](http://latex.artofproblemsolving.com/6/6/0/660699c6cec811eee25f727076665a6df3257f57.png)
Find the value of 
for every .
inscribed in a circle with center 
. 
is any point not on (O). 
intersect 
at 
. Let 
be the Lemoine points of triangle 
respectively. Prove that 
are collinear.
for which ![$\dfrac{n^2+1}{[\sqrt{n}]^2+2}$](http://latex.artofproblemsolving.com/7/e/d/7ed6c67114c0c7d262f67e5b7a733daab7997415.png)
is an integer. Here ![$[r]$](http://latex.artofproblemsolving.com/2/f/c/2fcabe2c2b8ebe2c428830acb9874cb8a8df790f.png)
denotes the greatest integer less than or equal to 
.
.
where 
. Then we require ![\[
\frac{(m^2+k)^2+1}{m^2+2} = m^2 + (2k-2) + \frac{(k-2)^2+1}{m^2+2}
\]](http://latex.artofproblemsolving.com/5/1/e/51e7271de40a69d05f3f617965dbb517563c68eb.png)
to be an integer. Now 
, and hence 
must be either 
, 
or . We will examine each case.
, then 
, which is impossible unless 
and 
, so no solution in this case.
, then 
. Modulo we get that 
which is enough to force 
, and yet this implies 
, contradiction.
, then 
. Again, taking modulo , we get 
which is not possible..
.
divides 
then is of the form 
. So all prime divisors of 
are of the form 
. However, this would imply that 
, which can't happen.
divides then is of the form . So all prime divisors of are of the form . However, this would imply that , which can't happen.
is even, then it's possible that 
, which is definitely permissible. In particular, 
is a solution here.
, and after some calculations, we have 
. Combine these two and use the inequality method, we easily found that there is no solution.
be the greatest square less than or equal to , then 
. Now let 
where 
. So ![$[\sqrt{n}]^2=m^2$](http://latex.artofproblemsolving.com/0/2/b/02b56d681735b1c9051095e44745be0e374355ef.png)
and thus![\begin{align*}\frac{n^2+1}{[\sqrt{n}]^2+2} &=\frac{(m^2+r)^2+1}{m^2+2}\\
&=\frac{m^4+2m^2r+r^2+1}{m^2+2} \\
&=m^2+\frac{2m^2r+r^2+1-2m^2}{m^2+2} \\
&=m^2+(2r-2)+\frac{r^2+1-4r+4}{m^2+2} \\
&=m^2+2r-2+\frac{r^2-4r+5}{m^2+2}
\end{align*}](http://latex.artofproblemsolving.com/3/b/f/3bfb9c193466f7c460138efc9ab9e049eb1d9a5f.png)
![\[r^2-4r+5\leq (2m+1)^2-4(2m+1)+5=4m^2-4m+2< 4(m^2+2).\]](http://latex.artofproblemsolving.com/6/9/8/698670f0858a9ed415b9c41b76caf209cd35211f.png)
is impossible since there are no two consecutive numbers that are squares. The second case is impossible by taking modulo 
since the quadratic residues modulo are 
and 
, then 
can be congruent to 
, none of which are quadratic residues. And the last case take modulo and see that 
is congruent to modulo which is not a quadratic residue. Therefore there are no such integers . 
, where . Therefore, ![$[\sqrt{n}] = m$](http://latex.artofproblemsolving.com/4/f/0/4f0ad7c2f261b91020519bb3dc123487777bef70.png)
. We are therefore trying to see when 
is an integer. We rewrite the fraction as 
. So we want 
. But notice that since 
, we have 
. Therefore, if 
is an integer, then it is either 
. We now go through the casework:
which leads to 
. The only squares the differ by are 
and . which would give us 
, contradiction. There are no solutions for this case.
. Let 
and 
. Then, we have 
. Since 
, we see that 
but then 
, yet another contradiction. There are no solutions for this case.
which would give us , yet another contradiction.
![$[\sqrt{n}]=m$](http://latex.artofproblemsolving.com/c/4/0/c40b798ee91009ca3d321f4c55462cca48a73c5d.png)
, i.e. 
.
where 
. The rest of the solution is then standard divisibility ideas and bounding.
, i.e. . where . The rest of the solution is then standard divisibility ideas and bounding.
where 
; then 
so we want to find when 
is integral.
is integral. Since 
, we have three cases:
. In this case 
clear contradiction.
. In this case 
; taking mod 8 gives the LHS equal to 1, 5, or 6 mod 8 and the only possible one is 6 mod 8. But then 
contradiction.
. In this case 
. Taking mod 9, the LHS can be 4, 5, 8, or 2 mod 9 which are all impossible, contradiction.
. where . Then we require to be an integer. Now , and hence must be either , or . We will examine each case., then , which is impossible unless and , so no solution in this case., then . Modulo we get that which is enough to force , and yet this implies , contradiction., then . Again, taking modulo , we get which is not possible..
for which is an integer. Here denotes the greatest integer less than or equal to .
with 
.
or 
. As 
and 
we get that 
. If is odd then 
is mod but since 
has no divisor of the form 
this gives a contradiction. So let 
. Thus 
. So 
is odd so let 
for some . So we have 
. We get that 
or 
. Thus 
for 
. So for if 
then is odd, obviously 
as 
can never be equal to for positive integers 
, and 
. So we have 
. So we get that 
which is a contradiction by mod check. Thus 
if . One can easily check that no solutions exist for . Hence no solutions for 
exist. Thus no solutions for the original problem exist
divides then is of the form . So all prime divisors of are of the form . However, this would imply that , which can't happen. is even, then it's possible that , which is definitely permissible. In particular, is a solution here. is odd".
.
, where 
. Then, we need:
to be an integer. This is equivalent to saying 
is an integer, call this . We now consider the following cases on which integer is:
. Then we need 
. However, the only consecutive perfect squares are 
, which implies 
and 
. But since , we also need 
which is a contradiction.
. Then we need 
. Now take 
, which shows that the LHS is either and the RHS is either 
. This implies that 
and 
, so 
and 
for some positive integers 
. When we substitute, the equation becomes:
wherupon taking 
implies that no solutions exist.. Then we need 
. Taking , the LHS is either 
and the RHS is , so no solutions exist in this case.
. This implies 
. But for 
we have:
so equality never holds (the reason we need is because the first inequality is not true if 
and , for instance). If the LHS is still less than the RHS, since the LHS is at most 
and the RHS is at least 
. Thus there are no solutions in this case either.
for which is an integer. Here denotes the greatest integer less than or equal to .
. Assume that exists solutions:
is surjective on 
. So we can let where 
and hence ![$[\sqrt{n}]=a$](http://latex.artofproblemsolving.com/a/9/9/a99b541b9c74efd3333f797253aff43af9260c87.png)
now lets use these informations:
That means 
where 
Case 2.- 
Case 3.- 
Hence no such positive integers.
![$n=m^2+k,k\in[0,2m]\cap\mathbb Z,m\in\mathbb Z$](http://latex.artofproblemsolving.com/8/3/e/83eb3e3f5c2c0eb664856a0709d06a3ddfde6ce0.png)
then we have:
By the aforementioned bounds, we obtain 
.
, and it's well-known that the only squares which are one apart are and , but there are no solutions here after testing 
, .
, now
gives that 
and 
. Now 
while if 
, 
, so no solutions.
, by
we have 
, which enforces and . Then 
while, if 
, 
, contradiction. satisfy this condition. 
, where 
are both nonnegative integers and ![$m \in [0,2k]$](http://latex.artofproblemsolving.com/b/1/2/b12c63dba33198485915249fad9b4a30b9a02b9a.png)
.
needs to be an integer, so 
needs to be an integer. Since , we have that can only be 
or . I claim that it can't be any., we have that 
, and this clearly holds false., we have that 
. Observing this in mod , we see that 
and 
. Let 
and 
. Substituting these values in we get that 
, which clearly isn't possible again by observing in modulo ., we have that 
. The right hand side is equal to 
, hence this is absurd. can never be an integer, so there exist no solutions for . 
. Let 
and 
for some 
. Clearly 
. Due to clear size reasons the quotient of the last divisibility cannot exceed . When the quotient exceeds working mod yields contradiction and when the quotient is there is only one possibility; which fails as well.
.
, where 
.
is an integer.
.
is a positive integer.![\[(c-2)^2+1\le (2m-2)^2+1=4m^2-8m+5<4m^2+8=4(m^2+2)\]](http://latex.artofproblemsolving.com/0/c/7/0c7704d9a836a8582151da9e9b46b2528164fa91.png)
and 
are positive, we have ![\[\frac{(c-2)^2+1}{m^2+2}\in \{1,2,3\}\]](http://latex.artofproblemsolving.com/5/6/e/56e6f82ee47b114f0420c8d2608ecb976c340e99.png)
. is a perfect square, which is not possible as 
.
. is a perfect square.
, so 
, both are not QR's.
. is a perfect square. Clearly not possible as it is 
.
where 
. Our question turns into
Long division yields
Since 
, the maximum value our expression can get is
Hence we will divide into cases
Hence we have proven our claim, therefore we are done.
works.
, then 
. Let 
, then![\[\frac{n^2+1}{\left\lfloor\sqrt n\right\rfloor^2+2}=\frac{(x^2+r)^2+1}{x^2+2}\rightarrow x^2+2\mid (r-2)^2+1.\]](http://latex.artofproblemsolving.com/a/f/9/af94f74bc6c14824326af910f2ba2be7f757ed98.png)
, so![\[\frac{(r-2)^2+1}{x^2+2}\in\{1,2,3\}.\]](http://latex.artofproblemsolving.com/4/0/4/40488a7b8852be59edf809942110de8696ff0d6b.png)
. Then 
, so 
. So 
, so 
, absurd as is positive.. Then 
, but taking mod yields a contradiction.. Then 
, but taking mod yields a contradiction.
has no integer solutions. 
is either 0 or 1 mod 3, and 
is also either 0 or 1 mod 3. For the total to be a multiple of 3, both have to be 0 mod 3, so and 
are both multiplies of 3, so the LHS is a multiple of 9, contradiction.
has no integer solutions. is either 0, 1, or 4 mod 5, and 
is either 0, 2, or 3 mod 5. The only way for the total to be 0 mod 5 is if both and are multiples of 5, so the LHS is a multiple of 25, contradiction.
. From now on, suppose 
. Suppose that 
for a positive integer 
and nonnegative integer 
such that 
(essentially make as large as possible). Then, 
Thus, 
Then, note that 
so we must have one of 
The first one clearly cannot happen as a positive square plus 1 is never a square, while the other two cannot happen by Claims 1 and 2, so we are done.
where . Note that this implies that 
. Note that we require 
Note that we can rewrite this as 
Equivalently, 
so we are left with 
. This is trivial to prove. It suffices to check three cases.
from which we get 
and 
. This yields that so there are no solutions.
.
. We will prove that cannot be a square. Note that if 
then 
which is bad. So let 
such that 
. However, this means that 
which is clearly false. Therefore, cannot be a square and there are no solutions for this case.
.
. Note that since 
we know that cannot be a square and there are no solutions in this case.
s.t. m is maximal but k stays a positive integer; we want ![\[\frac{(m^2+k)^2+1}{m^2+2} = m^2 + (2k-2) + \frac{(k-2)^2+1}{m^2+2}\in\mathbb{Z}.\]](http://latex.artofproblemsolving.com/7/c/e/7ce785e512e87806d33a16a9f9652be7021d018d.png)
Since , we only need to compute if the fraction equals 1,2,3.
, which is impossible unless 
, contradiction.
, contradiction.
, contradiction. We've exhausted all cases, so there is no solution for such n.
.
, and let 
. Then the condition becomes 
is an integer and 
. Thus 
. Since 
, so 
.
, then 
, a contradiction.
, then 
. So taking mod 3 forces 
. Then taking mod 9 gives 
, a contradiction.
, then 
, so 
and 
. This contradicts .
exist. Let 
and set 
, where 
. The divisibility condition 
after some reduction. In particular, this implies that 
, then 
must be a square, which is impossible.
, then 
must be a square, which is impossible by mod .
, then 
must be a square, which is impossible by mod .
and thus no valid .
.
. Then using the floor function inequalities, we get,![\[ \dfrac{k^4+1}{k^2 + 2}\le \dfrac{n^2 + 1}{k^2 + 2} \le \dfrac{(k+1)^4 + 1}{k^2 + 2}. \]](http://latex.artofproblemsolving.com/a/c/d/acd5191f37517735d9abe976da1aa31f5f63cd99.png)
. This gives us that 
. Also, we have that 
. This gives us 
. Combining these two bounds, we get,![\[ k^2 - 1 \le \dfrac{n^2 + 1}{k^2 + 2} \le k^2 + 4k + 3. \]](http://latex.artofproblemsolving.com/d/9/0/d90577bd715bb152b7573a072e856b8901ff8bb7.png)
, that is 
. Now we first need to find all the set of possible perfect squares in the interval ![$[k^4 + k^2 -3, k^4 + 4k^3 + 5k^2 + 8k + 5]$](http://latex.artofproblemsolving.com/9/d/5/9d500ee88443bcc54364cbc627e04cf365f7353b.png)
. Now we can note that all the perfect squares in this range are 
. This gives us that 
. as 
where 
. Since 
is an integer, we get that 
, that is,![\[ k^2 + 2 \mid (k^2 + i)^2 + 1 \equiv (-2 + i)^2 + 1. \]](http://latex.artofproblemsolving.com/8/0/b/80b6bf43184b6882bef8d4192ec8d0cd42d3d9eb.png)
which gives that the only possible values for 
are 
. Now among these possibilities, 
fails due to 
. Also, 
fails due to 
.
. This is only possible if 
. So now we are working with 
which forces 
, contradiction as was a positive integer.
. Suppose otherwise, then 
where 
and .
, so by plugging in 
(i.e. long division), we have:
.
, since the numerator is positive and 
. These cases each fail by 
, modulo , modulo respectively, so there are no solutions.
, so we have 
where 
we have:
has no solutions , and so no such works. 
where 
and 
. Then we want 
to be an integer. Subtracting 
means we want 
to be an integer. Since , we must have that the fraction is , , or .
gives 
, which is not possible.
gives 
. Since squares are never 
, let 
and 
. Then, 
so 
. This is clearly not possible because 
.
gives 
. Since perfect squares are 
, let 
and 
. Then 
so 
. This is clearly not possible because 
..
such that 
(so that 
). We have that:
However, since 
we have that 
Hence, we have that 
and by difference of squares, 
Hence, 
However, neither of these satisfy 
we have that 
Hence, 
By taking modulo 8, this is impossible.
we have that 
Hence, 
By taking modulo 3, this is impossible.
u
such that ![$f\in [0, 2m]$](http://latex.artofproblemsolving.com/b/4/f/b4fcc264e19eb861b8f41f929100f56f1c76f5c9.png)
.
.![\[m^2 + 2 | (m^2 + f)^2 + 1 \iff m^2 + 2 | (f - 2)^2 + 1\]](http://latex.artofproblemsolving.com/e/c/1/ec1b364313537e99889ea91f1dfe150e213ad631.png)
Note that![\[(f-2)^2 + 1\leq (2m - 2)^2 + 1 = 4m^2 - 8m + 5 < 4m^2 + 5 < 4(m^2 + 2)\]](http://latex.artofproblemsolving.com/6/2/3/623074c602927299c4500907fed75ff4b8c1f7c2.png)
Thus, 
.![$k = f -2, k \in [-2, 2(m - 1)]$](http://latex.artofproblemsolving.com/d/c/e/dceea117acc432dfcaec70bfca08ff12e7802842.png)
.
.
.![$k\in [-2, -2]$](http://latex.artofproblemsolving.com/3/b/8/3b87cc1fe72b9575926e220f70373616cc3ca1fc.png)
,
,
.
(since 
)
which is absurd.
.
which is impossible.
.
.
,
.
,
.
.
,
or 
.
,
,
and 
.
,
,
,
or 
,
where 
From the above bound we know that 
where 
which is impossible.
and by FLT we know that if 
then 
which is a contradiction and therefore 
but then 
which is impossible.
but 
no solution.
with 
;
.![\[a^2+2\mid (r-2)^2+1\]](http://latex.artofproblemsolving.com/4/8/6/486c669dd046ad3498b2a9e6f87ca5cca075da7b.png)
and by bounding we obtain either![\[(r-2)^2=a^2+1\]](http://latex.artofproblemsolving.com/d/5/2/d52ddf1a795a9cbebf1a0e97e5bc108920dfcd54.png)
![\[(r-2)^2=2a^2+3\]](http://latex.artofproblemsolving.com/b/b/8/bb82a107d970b88f334c88d68907174c5228fff1.png)
![\[(r-2)^2=3a^2+5\]](http://latex.artofproblemsolving.com/e/9/7/e97027756a252bac6866680d282a9882c7c5ea44.png)
and the first equation fails by DOS, the second by noting that we must have 
,
.
![$[\sqrt{n}]=k$](http://latex.artofproblemsolving.com/4/e/3/4e32b7ca7323a82482648f1606573594fe7e217b.png)
.
Note that 
and 
.
,
which yields no solutions.
,
.
,
.
,
which is impossible as 
.
for 
.![\[ \frac{(k^2 + m)^2 + 1}{k^2 + 2} = \frac{k^4 + 2k^2m + m^2 + 1}{k^2 + 2} = k^2 - 2 + 2m + \frac{m^2 - 4m + 5}{k^2 + 2} \]](http://latex.artofproblemsolving.com/8/6/e/86e11a43e9504d55822cae7352ef4344ab932cab.png)
This implies that 
for 
.
,
,
,
gives no solutions. If 
,
must divide![\[a^4+2a^2b+b^2+1 \implies 2a^2b-2a^2+b^2+1 \implies b^2-4b+5.\]](http://latex.artofproblemsolving.com/a/f/c/afc3f7099c11f5f96b8beeb1408616884e8637d7.png)
,![\[b = \sqrt{2a^2+3}+2, \quad \sqrt{3a^2+5}+2.\]](http://latex.artofproblemsolving.com/c/5/d/c5d4e981ce2f280775255a5b7ed1e09954911ff6.png)
.
If 
then 
,
.
,
,
which implies 
,
which implies 
,
which is a contradiction since the lhs is always even and the rhs is always odd. If 
then 
which is impossible. Thus no solutions exist and we are finished. 
and 
and 
.
Note that 
.
or 
then 
,
then 
which is not possible. Thus no solutions exist.