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.
be a positive integer that is not divisible by 
. Furthermore, let 
be a positive integer. Prove that none of the numbers of the form 
is a square number.
different bus lines in a city, each stopping at exactly 
stations and running in both directions. Nevertheless, for every two different stations there is always a bus line connecting these two stations. Determine the maximum number of stations in this city.
be an isosceles triangle with 
and circumcircle 
. The line through 
perpendicular to 
is denoted by 
. Furthermore, let 
be any point on . The circle 
with center and radius 
intersects 
once more at point 
and the circumcircle once more at point 
. Prove that the points 
and 
lie on a straight line.
be a positive integer. Furthermore, let ![$x_1, x_2,\ldots, x_n \in [0, 2]$](http://latex.artofproblemsolving.com/b/2/a/b2a6731961601353e26224c285a32923fbb54eb3.png)
be real numbers subject to 
. Prove the inequality
When does equality hold?
such that 
is a perfect square.
as the set of all numbers of the form 
for some nonnegative 
and 
. Find (with proof) all pairs 
such that 
and 
.
, Elbek writes 
. Prove that there will be two numbers on the board after some minutes, such that one is divisible by the other.
- Greatest common divisor of numbers 
and 
board, there is initially a tree of height 
. A gardener and a lumberjack alternate turns playing the following game, with the gardener taking the first turn:
. Determine the largest 
such that the gardener can ensure there are eventually majestic trees on the board, no matter how the lumberjack plays.
such that the equation
be a positive integer and 
be a polynomial with integer coefficients such that 
.
is divisible by 
.
such that for every positive real 
, there exists an integer 
satisfying![\[
\frac{\varphi(n!)}{n^\alpha\,(n-1)!} \;>\; c.
\]](http://latex.artofproblemsolving.com/4/4/4/4443cf7166cc65e67e2e504a826c4ac5f91aab2b.png)
be a positive integer and let 
be a strictly increasing sequence of positive real numbers with sum equal to 2. Let 
be a subset of 
such that the value of![\[
\left|1-\sum_{i \in X} a_{i}\right|
\]](http://latex.artofproblemsolving.com/2/5/1/2515e074de1782f38453e1fce8ab7c2ec7cfe4c0.png)
is minimised. Prove that there exists a strictly increasing sequence of positive real numbers 
with sum equal to 2 such that![\[
\sum_{i \in X} b_{i}=1.
\]](http://latex.artofproblemsolving.com/3/7/4/37410820fc4c546f11d57212cfce53a7ec4941e3.png)
such that if and are distinct rational numbers satisfying 
or 
, then 
? Justify your answer.
and the leaf to the right with 
. It seems to work.
for some 
where 
for all 
. From now on this will be denoted as ![$ [a_0; a_1, a_2, \dots, a_m] $](http://latex.artofproblemsolving.com/1/c/4/1c47e13850fd92c24cf30707900dc53e12c32418.png)
.
, let 
. Then let 
and for all 
let 
. I claim that this 
satisfies the desired properties. To prove this, consider two rational numbers 
.
If 
then by definition 
as desired.
If 
and 
then by definition as desired since 
.
If and 
then to prove that it suffices to show that 
. Let ![$ -x = [a_0; a_1, a_2, \dots, a_m] $](http://latex.artofproblemsolving.com/1/0/e/10e2dcb8e4ad502ecb43d7e1c2744f3995658d81.png)
. Then ![$ y = [a_0 + 1; a_1, a_2, \dots, a_m] $](http://latex.artofproblemsolving.com/2/c/e/2ce601c354188bdad5e03d9833f5a0efd26eb275.png)
and so 
as desired.
If and 
we can let ![$ y = [0; 1, a_2, \dots, a_m] $](http://latex.artofproblemsolving.com/e/6/b/e6b1ac208f52b35a47ba274b63b6aede8c05b3b5.png)
so that ![$ x = [0; a_2 + 1, a_3, \dots, a_m] $](http://latex.artofproblemsolving.com/5/c/a/5ca981e9723d9f4c0ee0a619a2f05b17f18fee09.png)
so 
and 
which implies that as desired.
If 
, we can assume WLOG that 
. Then letting ![$ x = [0; a_1, a_2, \dots, a_m] $](http://latex.artofproblemsolving.com/f/a/4/fa41f1dfed52008255c6fe47ad8f150591dc820c.png)
we have that ![$ y = [a_1; a_2, a_3, \dots, a_m] $](http://latex.artofproblemsolving.com/1/6/6/166a8243036f6a8f2362c13f93282945d869aff5.png)
so 
and 
which implies that as desired.
. Anyway, here's my solution: For two integers 
, let 
denote the number of steps taken in the Euclidean Algorithm to find 
. In other words, if we let 
and write the system of equations 
then 
where 
. Then we claim that the following function works-
for 
and 
for 
for 
with , 
when 
. For 
and 
, this easily follows from the definition, so we can ignore these cases. WLOG assume 
and suppose 
for some 
with 
. Then from property 3 of our function, we have 
and 
. Since 
so it suffices to show that 
for 
.
for , and first suppose 
. We have 
But, as 
, so the first step of our Euclidean Algorithm while finding 
will be 
. So 
. Also, using 
, we get 
. Thus, we have 
Thus, for 
we have . Finally, if 
then 
and 
. Since 
, then the previous result gives 
. Combined with the above equalities, we get . Thus, the result is true for all 
.
for 
. For 
, the result is true by definition. And for 
, by the above result, we have 
which directly gives the desired property.
when 
. Since 
(proved before), so it suffices to show the result for positive . Also, WLOG we can take 
, and write with 
and 
. Then 
But, while finding 
we simply start from the second step in the Euclidean Algorithm to find . So we have 
. This gives us 
Thus, we have as desired. 
is that 
, which we can manually enforce at the end. Thus, we assume that the inputs to 
are nonzero rationals.
where 
and 
. We set ![\[s(x) = \begin{cases}1 &\text{if } (a^{-1}\mod b)\le b/2 \\ -1 &\text{if } (a^{-1}\mod b)>b/2.\end{cases}\]](http://latex.artofproblemsolving.com/2/7/e/27e64eb277458c6bc8cbe17ca29ebb109bc722d2.png)
From this definition, it is clear that 
and 
, so it suffices to show that 
. Since we know is odd, it suffices in fact to show for .
are relatively prime positive integers, then ![\[a\cdot(a^{-1}\mod b) + b\cdot(b^{-1}\mod a) = ab+1.\]](http://latex.artofproblemsolving.com/b/5/a/b5a225156975a80139966b83b5c971e5a88c9bbc.png)
be the left side of the above equation, we see that 
and 
, so 
since .![\[a+b\le T\le a(b-1)+b(a-1)<2ab,\]](http://latex.artofproblemsolving.com/6/c/e/6ce6d2e84ed2e9ff81a63c24ce53b9e60861da84.png)
so we must in fact have 
, as desired. 
if and only if 
, which implies that 
..
on the positive rational numbers to be the number of terms in the continued fraction of . Then let 
and . Then, clearly . If 
and 
then 
and therefore 
, so 
.
. WLOG, 
. If 
then ![$x=[0;1,a,\dots]$](http://latex.artofproblemsolving.com/d/3/e/d3ef3f221323abf5c6356691c994845c9be62918.png)
and ![$y=[0;1+a,\dots]$](http://latex.artofproblemsolving.com/3/9/7/397e02bb78e1b1f429fefe70e1cc92de4f6bd7bd.png)
where the 
is the same. If then 
so they have the same number of terms in the continued fraction, thus 
as desired.
directly.
. For any we have![\[s(x)=-s(-x)=s(x+1)\]](http://latex.artofproblemsolving.com/3/2/9/3290f550427475170362f031c558fd9666b859ce.png)
and we also have 
. Hence for any 
we have 
.
(starting from the smallest), we now choose 
for 
starting from and relatively prime to 
according to the following rules:
then 
.
then 
. and the conditions hold. Importantly our selection of outputs satisfies 
as well. (The only restriction on is which clearly holds.)
then WLOG with . From the first rule in the previous section we are fine.
cannot hold. If then write 
and 
. Then![\[s(x)=-s(1/x)=-s(1/x-1)=-s(b/a)\]](http://latex.artofproblemsolving.com/1/c/a/1caf3a4fbffbd73479bcd305c2ea6fb18a4daadf.png)
![\[s(y)=-s(1/y)=-s(1/y-1)=-s(a/b)\]](http://latex.artofproblemsolving.com/3/c/6/3c68f657f66c8a332250c67b4a232a5945f615a8.png)
thus . for positive .
and are distinct, negative and satisfy we are okay: 
. and are distinct and satisfy we are okay by definition. and WLOG is negative while is positive, then![\[s(y)=s(y-1)=-s(1-y)=-s(x)\]](http://latex.artofproblemsolving.com/6/8/b/68be493bd6889d204c9d6942ed7daac1e44801c2.png)
and we are okay.
for coprime nonzero inputs as follows: let 
for all 
. Then we define recursively![\[
f(a+b,b) = f(a,a+b) = f(a,b).
\]](http://latex.artofproblemsolving.com/8/c/e/8ceba577222d7c91c373379932ec1491f1b7773d.png)
This is well defined as 
is defined on input by Euclidean algorithm, and 
is defined uniquely by whichever of 
is smaller.
follows since 
recursively with the Euclidean algorithm. Furthermore, for 
, 
. to negative coprime inputs by defining 
. By and by the definition, it follows that for 
![\[
f(a, b) = f(a+b, b), f(b, a) = f(b, a+b)
\]](http://latex.artofproblemsolving.com/4/d/9/4d926a668585ac7af2668c27070453b5c09e9fbc.png)
holds for all 
. We finally define 
for coprime . Then 
holds over the extension for the same reasons, 
holds by definition, and 
holds since![\[
f(b-a,b) = f(-a,b) = -f(a,b)
\]](http://latex.artofproblemsolving.com/d/1/3/d1370636d2818f96924dd00e3dd6a4fa66ebfda5.png)
so we are done.
, such that for all 
:![\[ f(x+f(y))=\dfrac{f(x)}{1+f(xy)}\]](http://latex.artofproblemsolving.com/1/4/1/1418fad9fd00b31c38bfbc5657e2a322d66ef450.png)
,![\[\frac{a}{b}+\frac{b}{c}+\frac{c}{d}+\frac{d}{a}\geq 4+\frac{8(a-c)^2}{(a+b+c+d)^2}.\]](http://latex.artofproblemsolving.com/7/b/6/7b6e32d32d89ca058a06974e7276f0a5874d90a7.png)
.
from 
.
is a number of subfractions in the continuous fraction representing 
if we use 
contradiction.
and ![$x=[a_0;a_1,\ldots,a_m]$](http://latex.artofproblemsolving.com/5/6/e/56ed080618e6b06c10a5648cf6102fbcd6fea56c.png)
.
and 
.
,
,
,
and 
,
,
.
to be the minimum repeated applications of 
until an integer is obtained, and 
if ![\[\{s(0) = -1,\ s(x) = (-1)^{g(x)}|\ x > 0,\ s(x) = (-1)^{g(-x) + 1}|\ x < 0\}\ \forall\ x\ \in\ \mathbb{Q}\]](http://latex.artofproblemsolving.com/7/6/3/7639d6b32b78dd339446b8411afa6547cabb97b9.png)
.
,
,
,
.
,
,
,
as well. Finally, we will show that for any 
.
,
is equal to 
,
,
![$[0, 1]$](http://latex.artofproblemsolving.com/a/b/1/ab178d831a786b92cb4c9ddc2d33578223036f98.png)
.
,
.
,
,
,
,
and the other is greater than 
Therefore, we can express 
.
.
.
,
,
,