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.
such that for all positive integers 
,![\[
f(mn) = \mathrm{lcm}(m, n) \cdot \gcd(f(m), f(n)),
\]](http://latex.artofproblemsolving.com/6/0/7/6071692e2716901e88cc1cfc19ed60388c10701d.png)
where 
and 
denote the least common multiple and the greatest common divisor of 
and 
, respectively.
has a closed walk of length at most 
passing through each edge of 
at least once.
satisfying the following condition: for any real numbers 
and 
, the number 
is equal to 
or 
contains no term of the form 
and 
.
?
, similarly to 
, by SOS
be a triangle with 
. Let 
, 
, and be the midpoints of the sides 
, 
, and 
respectively. A circle 
passing through 
and tangent to at meets the segments 
and 
at 
and 
, respectively. The points 
and 
are symmetric to and about and , respectively. The line 
meets 
and 
at 
and 
, respectively. The line 
meets again at 
. Prove that 
.
of acute triangle is 
. The ray drawn from through the circumcenter 
intersects at 
. Let the midpoint of 
be 
. Define 
, 
, 
, 
, 
, 
similarly. Prove that 
, 
, 
are concurrent.
![$P(x) \in \mathbb{R}[x]$](http://latex.artofproblemsolving.com/4/5/3/453a624c3b002c1b0e78e0023b24dd22ddd03557.png)
such that:
with 
is an 
th prime and 
is an arbitrary positive integer.
grid with each cell colored with an integer from 
to 
. Two players take turns. On a turn, a player may increase any one cell’s value by a power of 2 (i.e., add 1, 2, 4, or 8 mod 16). The first player wins if, after their move, the sum of each row and the sum of each column is congruent to 0 modulo 16. Prove whether or not Player 1 has a forced win strategy from any starting configuration.
be a parallelogram with 
A point is chosen on the extension of ray past 
The circumcircle of 
meets the segment 
again at 
The circumcircle of triangle 
meets the segment 
at 
Prove that lines 
are concurrent.
be two positive integers, such that 
. Find all the integer values that 
can take, where ![\[ f(a,b) = \frac { a^2+ab+b^2} { ab- 1} . \]](http://latex.artofproblemsolving.com/c/b/2/cb27ccbcde6d90f98e10f8f6876c36ae8972af7f.png)
appeared not long ago in a USA TST. But it's very interesting what happens with this problem after you start solving it. It has a step curiously difficult. A very nice problem, like all the other problems given in this very difficult TST.
s.t. 
. We can go from the pair to a "smaller pair" 
until we eventually reach a "dead-end", i.e. a pair which can no longer become smaller by the above transformation. is invariant wrt the transformation mentioned, so the value we're interested in remains the same. I also think that the "dead-end", as I've called it, must be one of the pairs 
, 
and 
. By analyzing the 3 cases we obtain 
(it's 7 in the first two cases and 4 in the third case).
.
), only two contestants have managed to master the problem some more computations for clarification are required, but that's the main idea.
)..
,we have 
.Thus 
.i.e. 
,yielding 
.
and 
,WLOG 
,so we can set 
,thus we have
(☆)![$\leqq1+\frac{a^2+(a-1)^2+1}{ab-1}=1+\frac{2\left[(a-1)a+1\right]}{ab-1}\in\mathbb{N}$](http://latex.artofproblemsolving.com/2/f/0/2f0cfd97d719b166add7fd2cf76933fca86135e4.png)
,since 
is odd, we obtain 
,
,yielding 
and 
, in addition to from （☆）
G.M and 
,we obtain
. is 
.
ax^2+bxy+cy^2=k? I looked it up at MathWorld and became curious about a possible connection.
be two positive integers, such that . Find all the integer values that can take, where ![\[ f(a,b) = \frac{ a^2+ab+b^2} { ab- 1} . \]](http://latex.artofproblemsolving.com/f/e/2/fe2727185aa4224e2be19abf171add09105094af.png)
be two positive integers, such that . Find all the integer values that can take, where 
we have 
.
.
, 
. This equation has the second root (with respect to ), call it 
.
. We can repeat this while both 
. can be obtained while one of the numbers (i.e. b) is 0, 1 or 2, which is easy to handle.
I'm having troubles understanding why the new pair is "smaller" than the previous one. In IMO '88, that's clear, but here 
Does anyone dare to help me?
is divisible by 
, so 
is also divisible by . 
is divisible by . The rest is not so difficult.
![\[ k = \frac{a^2+ab+b^2}{ab-1} \iff a^2 - b(k-1) \cdot a + (b^2+k) = 0. \]](http://latex.artofproblemsolving.com/e/2/6/e26006b45238696f47eb0fe292c496b8d0176068.png)
We contend either 
or 
. These are achieved by 
and 
.
and suppose is a minimal pair for that . If we get 
which easily implies and hence 
.
and note that if is a solution then by Vieta jumping we get a neighboring pair ![\[ (a,b) \rightarrow \left( \frac{b^2+k}{a}, b \right) = \left( (k-1) \cdot b - a, b \right). \]](http://latex.artofproblemsolving.com/4/e/4/4e415a71ddabc4a6521802eb7abb326addbc733d.png)
This forces 
, so 
. A calculation then gives 
This can only occur for 
hence . and are given respectively by ![\[ (2,2) \xleftrightarrow{a^2-6a+8} (2,4) \xleftrightarrow{a^2-12a+20} (10,4) \longleftrightarrow \dots \]](http://latex.artofproblemsolving.com/8/9/b/89b6eefa67d88145584165de2946828eddf866c1.png)
and ![\[ \dots \longleftrightarrow (23,4) \xleftrightarrow{a^2-24a+23} (4,1) \xleftrightarrow{a^2-6a+8} (2,1) \xleftrightarrow{a^2-12a+11} (11,2) \xleftrightarrow{a^2-66a+128} (64,11) \longleftrightarrow \dots. \]](http://latex.artofproblemsolving.com/a/5/5/a55c935bd42ef79bb689cd18b9966cbd2fa12124.png)
The proof above can be phrased conceptually as saying that 
and are the unique pairs (across all ) which do not have a neighbor of lesser sum.
, say 
.
. is the pair for the particular that is an output of 
such that is minimal.
is another root of 
, and clearly 
. Assume 
.
.
.
, this implies 
or 
.
or .
.
Contradiction.
.
as 
or 
.
then should 
be a integer. so
so:
then: 
then we can check the possible roots and get solution.
. We first resolve some edge-cases.
, then 
.![\[g(a,1)=\frac{a^2+2}{a-1}=a+1+\frac{3}{a-1},\]](http://latex.artofproblemsolving.com/6/0/b/60b97b49f0ac9f65dff192171afc4c1fc6462ead.png)
so we get 
and 
. 
, then 
.![\[g(a,a)=\frac{2a^2+1}{a^2-1} = 2+\frac{3}{a^2-1}.\]](http://latex.artofproblemsolving.com/6/2/f/62f0c9bee9408433b8f907f007fb396940b3a12c.png)
This implies , so . 
WLOG. Set 
so we get![\[g(a,b)=\frac{a^2+b^2+1}{ab-1}=\frac{r^2b^2+b^2+1}{rb^2-1} = r+\frac{b^2+r+1}{rb^2-1}=r+\frac{1}{r}+\frac{r+1+\frac{1}{r}}{rb^2-1} \le r+\frac{1}{r}+\frac{r+1+\frac{1}{r}}{4r-1}.\]](http://latex.artofproblemsolving.com/2/9/e/29e5591c5cd863043e0d9a6465c022341915186a.png)
Then, note the inequality![\[4r-1>3r >r+1+1>r+1+\frac{1}{r},\]](http://latex.artofproblemsolving.com/5/a/0/5a0fcc2ddcd999c691654e326a8d8146bcc6d3bd.png)
so we must have![\[g(a,b)=\left\lceil r+\frac{1}{r}\right\rceil < r+\frac{1}{r}+1<r+2\]](http://latex.artofproblemsolving.com/8/d/9/8d9a15131f01f9d398f4f37394f58dce9872a209.png)
because![\[\frac{r+1+\frac{1}{r}}{4r-1}<1\]](http://latex.artofproblemsolving.com/4/6/a/46a75090d91dc7743a873ac023f269b9fc15f541.png)
and 
. Now, we use bruteforce to make Vieta Jumping work; we take some choice of and either reduce 
or get stuck at some particular points. WLOG assume as we already dealt with the other cases. Let 
. We can assume 
as we have already found constructions for those .![\[a^2+b^2+1=kab-k.\]](http://latex.artofproblemsolving.com/c/b/9/cb9a8651e8f9effb878303bf1ce0cecf99aaa4a3.png)
Rewrite this as![\[a^2-(kb)a+b^2+k+1=0.\]](http://latex.artofproblemsolving.com/d/6/d/d6da661aa6d079da39b51f45b32cf89438ff5d2e.png)
Thus, the other root of this quadratic in is![\[\frac{b^2+k+1}{a} < \frac{b^2+k+1}{b(k-2)} = \frac{b}{k-2}+\frac{k+1}{b(k-2)}.\]](http://latex.artofproblemsolving.com/3/a/f/3affae244522a84afed580288542a50afa20f51d.png)
We take the time to note that as 
and 
, we have![\[\frac{b^2+k+1}{a}<\frac{b}{2}+\frac{k+1}{2(k-2)} = \frac{b}{2}+\frac{1}{2}+\frac{3}{2(k-2)}\le \frac{b}{2}+\frac{1}{2}+\frac{3}{4} = \frac{b}{2}+\frac{b}{2}+\frac{1}{4}=b+\frac{1}{4}.\]](http://latex.artofproblemsolving.com/f/5/7/f57354a4e28035522e4b3de9b5672da0922f5e8a.png)
As the latter expression is an integer and cannot be (as that would give 
, which is disallowed), we get that is monotonically decreasing when we Vieta Jump, absurd. Thus, 
are the only possibilities and so 
.
Note that by 
we have 
Consider the solution 
with minimal sum, for which 
is an integer. Assume WLOG 
Consider the function 
We know that there is a number 
such that 
From here we easily deduce 
and therefore it must be the case 
and recall that 
We obtain 
so we must have 
so 
and now by simple polynomial division we obtain 
and so 
We then have 
and so 
In both cases we deduce 
and . First, note that when , the fraction becomes 
which is only an integer for . This yields . Now, assume that 
. We will use Vieta jumping. We have![\[ \frac{a^2+ab+b^2}{ab-1} = k \implies a^2 - (k-1)b \cdot a + b^2 + k .\]](http://latex.artofproblemsolving.com/5/7/9/579498da5110b38ffe12288b30c42c5107609d71.png)
Therefore, we can jump from the pair to 
. This process always produces a smaller pair when 
or when 
. In this case we have,![\[ \frac{a^2+ab+b^2}{ab-1} < a^2 - b^2 \iff \frac{2a+b}{a+b} < b(a-b) \]](http://latex.artofproblemsolving.com/b/e/8/be86b303c90d84a54a21849b368dc2cc8f733e79.png)
Note that 
when 
. Therefore, the only case when this breaks is when 
and 
. This yields 
, so we are done.
are , which can be obtained with 
respectively.
. Then, we have 
. Suppose is a solution. Then,
is also a solution. Observe that for 
, or 
then we have![\[2a+b < b(a-b)(a+b) = a^{2}b - b^{3} \Rightarrow 2a^{2} + ab < a^{3}b - ab^{3}\]](http://latex.artofproblemsolving.com/a/3/b/a3b003b0b2971f85bc7bde5b892e573b1aa7f4dd.png)
![\[\Rightarrow a^{2} + ab + b^{2} < a^{3}b - ab^{3} - a^{2} + b^{2} \Rightarrow a^{2} > \frac{a^{2} + ab + b^{2}}{ab-1} + b^{2} = k+b^{2}\]](http://latex.artofproblemsolving.com/d/2/6/d2641f21982b63b4e2893ea28c72733fa3b025da.png)
Therefore, for all or , when we flip the larger of , it always decreases it. Thus, we need to check when 
, or when 
and 
. When , we need 
is an integer, or 
is an integer. The only case where this is possible is 
. When and , this is when 
. For both these cases, flipping the larger one does not decrease, so all solutions can be continuously flipped to reach one of these two. Since is constant when flipped, the possible values of are 
.
which is the same as 
; given any solution with 
we Vieta jump to 
. It suffices to find all minimal solutions, which have 
, so 
. Letting 
for some 
, we have 
which is equivalent to 
When 
we see that all work, while when 
we can easily see that we must have . There's no solutions when 
for size reasons (for instance, 
). When we have , and so 
. When 
we get which indeed works. So the only minimal pairs with are 
, which in the context of the original problem give 
respectively.
. Suppose 
. Then![\[ a^2-(kb)a+(b^2+1+k) = 0. \]](http://latex.artofproblemsolving.com/d/e/3/de39f02a6241b568ccdd3d4b69b44419a27183b3.png)
So if works, then 
works. Also, if works, then 
works by symmetry. Consider the pair with minimal 
that works. Then we must have 
, so
Therefore, 
or . In the latter case, 
, and in the latter case, 
, which is an integer if and only if , in which case 
. The answer is 3 and 7.
gives 
must be a multiple of 
, forcing 
, both of which cases gives 
. similarly gives that 
is a multiple of 
, similarly forcing , and 
. Now, we claim that these are the only possible values. from here onwards, and let 
be a solution to 
such that 
is minimized. We have 
; treat this as a quadratic in , and with Vieta's formulas, we know that the other solution is 
, which must be equal to 
. The former gives that it is an integer, and the latter gives that it is positive, and therefore another valid solution; for a contradiction to not arise, we need 
, or 
.
can be rearranged to 
. Now, let 
; the inequality can be again rewritten as 
, from which we can solve 
, which makes it impossible for to be an integer.
![$\boxed{f(a,b) = \frac { a^2+ab+b^2} { ab- 1} \in [4,7]}$](http://latex.artofproblemsolving.com/6/f/e/6fe8f0b90e8643b1e3e9b3f6f5304171ed615d3e.png)
,and let .So if works, then works. Also, if works, then works by symmetry. with minimal sum:-Therefore, or . In the former case, , and in the latter case, , which is an integer if and only if , in which case .
. We can check that 
and . Further, if , then
so and . We can also check that if 
we only have . Now suppose that 
is in the range of , and pick such that 
, , and is minimal, so 
. as a constant, rewrites as the following quadratic in :
By Vieta jumping, 
is also a solution, and by minimality we must have
This forces
which evidently only holds for 
, contradiction. Thus such a does not exist, so as desired. 
.
. Then the equation simplifies to 
This means that if 
yields a particular value of , then 
yields this value of too. WLOG .
, 
unless .
as 
. On the other hand the final display is clearly true. can be generated by 
or 
. The only such values are 
, as needed.
.
, then one can check that all pairs such that is an integer are 
and we can check the case . Let be a pair such that is an integer and 
and let 
. Then we have 
, or equivalently 
. Let 
be a root of 
other that . Then 
and 
. Thus is an integer and 
. We'll prove that 
. Assume not. Then we get 
, or equivalently 
. Therefore 
. By expanding, we get 
, so 
. Thus we get 
. Hence 
, a contradiction. Thus we have 
.
, then 
decreases. Therefore repeating this process until , we obtain 
or . This completes proof. 
is , so assume WLOG . Letting , our equation can be rewritten as![\[a^2-(bk-b)a+(b^2+k) = 0.\]](http://latex.artofproblemsolving.com/d/1/b/d1b0707800672066d1190036c859775b4e6379dc.png)
is a valid solution, then 
is also a valid solution. To show this procedure always leads to smaller pairs, note
, where we find the only valid values of are 2 and 4, both of which give . Hence we stop our algorithmic decreasing only when
or 
, leaving 
, leaving 
. 
, where k is an integer. We get the quadratic equation 
. Now by Vieta jumping we can generate new solutions from (a,b) to 
. Now WLOG 
. If a = b, we need to have that 
, since a is a positive integer and 
a = b = 2 and we get the solution (a,b) = (2,2) and k = 4. Now the neighboring pair forces 
. Now plugging that in the original equation for f(a,b) we get 
, which is equivalent to 
we get that 
. Since and a and b are positive integers the only (a,b) that satisfies this condition is (a,b) = (2,1), where k=7 we got that the only possible k are k=4 when (a,b) = (2,2) and k=7 when (a,b) = (2,1) f(a,b) = 4;7. We are ready.
can take is 
which are clearly achieved by the triples and respectively. First note that if , it is easy to show that 
and hence .
for some positive integers and positive integer 
assuming WLOG that (
as this implies as we noted above) and in particular is the smallest such pair (i.e, is minimum).
,![\[X^2-(k-1)bX + b^2+k = 0\]](http://latex.artofproblemsolving.com/3/f/a/3fab0e626d9a33fdeebb46d94f9f3e8ac491245a.png)
of which is known to be an integral root. Consider the second root . By Vieta's relations we have, 
and hence is an integer but also,![\[ax = b^2+k >0\]](http://latex.artofproblemsolving.com/1/7/c/17c044ce01c16082f7c7e3e7473b58a60f78522d.png)
which allows us to conclude that is in fact a positive integer. Hence, 
is a valid pair of solutions to the given equation. Since is the minimal pair of solutions by assumption we must have 
and hence,![\[x = \frac{b^2+k}{a} > b\]](http://latex.artofproblemsolving.com/a/a/0/aa0d4583863dfe0bfcfb60a7848395b7958c727c.png)
so 
. But then,
But then,
which implies . Hence, if is the minimal solution such that we must have . However, solving the cases , 
and 
(which turns out to have no solutions) by hand yields and only which is a very clear contradiction. Hence, there exists no pairs of positive integers for which 
as desired.
which is achieved at 
and 
achieved at 
First, we check when one of the variables is 
If this happens, then we get
So, 
or 
and we find 
we get
so 
giving 
and 
Then, since the equation is symmetric, we can assume WLOG that 
Also, let 
i.e. both variables are minimized (notice that if one variable is smaller, then the other is too). We can expand to
So, there is another positive integer solution to this equation 
with
Claim: 
Notice that, if 
then 
iff 
which cannot happen, since 
so 
So,
Hence,
so we have that 
