AoPS Academy
be an integer. Show that, if 
is an integer, then it is a perfect square.[/quote]
. If is an integer, then 
is at least rational, so that 
must be a perfect square then. Using Conway's topograph method, I have found out that the smallest non-negative pairs 
for which this happens are 
and 
, and that, for every such pair 
, the "next" such pair can be calculated as
The eigenvalues of that matrix are irrational, however, so that any calculation which uses powers of that matrix is a little cumbersome. There must be an easier way, but I cannot find it. Can you?
and 
satisfies the following recursion formulas: 
, 
and 
. Find 
and 
interesting if is composite and for every divisor 
of at least one of 
and 
is also a divisor of with 
+1 w
be a triangle, and let 
and 
be points on segment 
symmetric with respect to the midpoint of . Let 
denote the circle passing through and tangent to line 
at 
. Similarly, let 
denote the circle passing through and tangent to line 
at 
. Let the circles and intersect again at point 
(
). Prove that 
.
is an integer, and let 
be 
integers such that 
for any two integers 
and 
satisfying 
. Determine the maximum possible value of 
.
? Parity seemed to be sufficient...
to get area of 
., @above
is 3.
.Then,
.
,
.
lie on a single line 
,
implies 
contradiction.
is a line and all other 
makes a line.
is an integer, and let be integers such that for any two integers and satisfying . Determine the maximum possible value of . be the points representing 
, and define 
.
such that both of them are even. Similarly, we couldn't have two coordinates such that 
are both even. Furthermore, if and are congruent modulo 
. Then, 
, which is a contradiction. Therefore, we have 
(which is (O,O), (O,E), (E,O)), and is indeed possible by taking![\[ (1,1), (0,1), (1,0) \]](http://latex.artofproblemsolving.com/8/8/9/889d6474f64f61d1a729a75aa0e72b47d10dcebb.png)
coordinates of . By 2020 USOMO 4, the maximum number of pairs is 
, but since every pair must work, we have ![\[ 2r-3=\binom{r}{2} \implies r=2,3\]](http://latex.artofproblemsolving.com/5/f/d/5fdbec27c0c1c241429786fa86dc5639326460bd.png)
so is our maximum. To finish, a construction of 
, 
, and 
works.
is possible. Let 
. They will be linearly dependent. Let 
with 
integers and not all even. Then we can choose three of them, say 
such that either 
or 
of them are odd. But 
which is not possible bcoz x component will be odd.
is an integer, and let be integers such that for any two integers and satisfying . Determine the maximum possible value of .
be two of the pairs and x,y be another. Then we get four possible pairs of two equations in (x,y)(so 
)[Choose the 
's]. Then we get 
and the negatives of these 2. it is easy to check that no two of these 4 can have a product [its either 0 or 
2]. Thus we can have atmost one of these 4 and 3 is the ans.
be two of the pairs and x,y be another. Then we get four possible pairs of two equations in (x,y)(so )[Choose the 's]. Then we get and the negatives of these 2. it is easy to check that no two of these 4 can have a product [its either 0 or 2]. Thus we can have atmost one of these 4 and 3 is the ans.
in the cartesian palne. And let 
be the origin .
is clearly 
. (Just using the determinents) points in Cartesian plane as following .![[asy]
/* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */
import graph; size(8cm);
real labelscalefactor = 0.5; /* changes label-to-point distance */
pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */
pen dotstyle = black; /* point style */
real xmin = -1.1338271604938273, xmax = 1.1338271604938273, ymin = -0.6597530864197526, ymax = 0.6597530864197522; /* image dimensions */
pen ccqqqq = rgb(0.8,0,0); pen fuqqzz = rgb(0.9568627450980393,0,0.6); pen qqwuqq = rgb(0,0.39215686274509803,0);
draw((0.03358024691358025,0.19555555555555512)--(-0.2923456790123457,-0.0849382716049384)--(0.2804938271604938,-0.06320987654321003)--cycle, linewidth(2) + blue);
draw((-0.2923456790123457,-0.0849382716049384)--(0.03358024691358025,0.19555555555555512)--(-0.2607407407407408,0.2864197530864192)--cycle, linewidth(2) + ccqqqq);
draw((-0.2607407407407408,0.2864197530864192)--(-0.2923456790123457,-0.0849382716049384)--(0.2804938271604938,-0.06320987654321003)--cycle, linewidth(2) + fuqqzz);
draw((-0.2923456790123457,-0.0849382716049384)--(-0.5708641975308643,0.2587654320987649)--(-0.2607407407407408,0.2864197530864192)--cycle, linewidth(2));
draw(arc((-0.2923456790123457,-0.0849382716049384),0.05925925925925927,2.172246804777998,40.715486381229354)--(-0.2923456790123457,-0.0849382716049384)--cycle, linewidth(2) + ccqqqq);
draw(arc((-0.2923456790123457,-0.0849382716049384),0.05925925925925927,40.71548638122936,85.13548556223948)--(-0.2923456790123457,-0.0849382716049384)--cycle, linewidth(2) + qqwuqq);
draw(arc((-0.2923456790123457,-0.0849382716049384),0.05925925925925927,85.13548556223947,129.01940047523658)--(-0.2923456790123457,-0.0849382716049384)--cycle, linewidth(2) + blue);
/* draw figures */
draw((0.03358024691358025,0.19555555555555512)--(-0.2923456790123457,-0.0849382716049384), linewidth(2) + blue);
draw((-0.2923456790123457,-0.0849382716049384)--(0.2804938271604938,-0.06320987654321003), linewidth(2) + blue);
draw((0.2804938271604938,-0.06320987654321003)--(0.03358024691358025,0.19555555555555512), linewidth(2) + blue);
draw((-0.2923456790123457,-0.0849382716049384)--(0.03358024691358025,0.19555555555555512), linewidth(2) + ccqqqq);
draw((0.03358024691358025,0.19555555555555512)--(-0.2607407407407408,0.2864197530864192), linewidth(2) + ccqqqq);
draw((-0.2607407407407408,0.2864197530864192)--(-0.2923456790123457,-0.0849382716049384), linewidth(2) + ccqqqq);
draw((-0.2607407407407408,0.2864197530864192)--(-0.2923456790123457,-0.0849382716049384), linewidth(2) + fuqqzz);
draw((-0.2923456790123457,-0.0849382716049384)--(0.2804938271604938,-0.06320987654321003), linewidth(2) + fuqqzz);
draw((0.2804938271604938,-0.06320987654321003)--(-0.2607407407407408,0.2864197530864192), linewidth(2) + fuqqzz);
draw((-0.2923456790123457,-0.0849382716049384)--(-0.5708641975308643,0.2587654320987649), linewidth(2));
draw((-0.5708641975308643,0.2587654320987649)--(-0.2607407407407408,0.2864197530864192), linewidth(2));
draw((-0.2607407407407408,0.2864197530864192)--(-0.2923456790123457,-0.0849382716049384), linewidth(2));
/* dots and labels */
dot((-0.2923456790123457,-0.0849382716049384),dotstyle);
label("$O$", (-0.2962962962962963,-0.1422222222222223), NE * labelscalefactor);
dot((0.2804938271604938,-0.06320987654321003),dotstyle);
label("$P_1$", (0.2883950617283951,-0.04345679012345697), NE * labelscalefactor);
dot((0.03358024691358025,0.19555555555555512),dotstyle);
label("$P_2$", (0.04148148148148148,0.2153086419753082), NE * labelscalefactor);
dot((-0.2607407407407408,0.2864197530864192),dotstyle);
label("$P_3$", (-0.2528395061728395,0.3061728395061723), NE * labelscalefactor);
dot((-0.5708641975308643,0.2587654320987649),dotstyle);
label("$P_4$", (-0.562962962962963,0.278518518518518), NE * labelscalefactor);
label("$\alpha$", (-0.2271604938271605,-0.06518518518518535), NE * labelscalefactor,ccqqqq);
label("$\beta$", (-0.2706172839506173,-0.015802469135802678), NE * labelscalefactor,qqwuqq);
label("$\gamma$", (-0.33185185185185184,0.001975308641975082), NE * labelscalefactor,blue);
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle);
/* end of picture */
[/asy]](http://latex.artofproblemsolving.com/4/a/1/4a1ae61c44390008bfca248563e13804e311268e.png)
.![\[\frac{wy \sin (\alpha +\beta +\gamma )}{2} = \frac{zx\sin (\beta)}{2} = \frac{xy \sin (\alpha)}{2} = \frac{zy \sin (\alpha +\beta)}{2} = \frac{wz \sin \gamma )}{2} = \frac{1}{2}\]](http://latex.artofproblemsolving.com/a/6/8/a6884a48878448197e1b6e7f0aa4703bde4a7457.png)
![\[ \sin \alpha =\frac{1}{xy} , \sin \beta = \frac{1}{zx} \cdots (1)\]](http://latex.artofproblemsolving.com/0/b/c/0bc125e26790fcea3a65205e865abe7ed831699d.png)
![\[zy\sin (\alpha +\beta)=1\cdots (2)\]](http://latex.artofproblemsolving.com/d/d/2/dd295aed13eabad09543b1c6b757235e09d02d11.png)
![\[z\cos \beta +y\cos \alpha =x\]](http://latex.artofproblemsolving.com/3/7/5/37509cbdfe7c18a9a03c52074e31f521a36f1b8e.png)
with area and sides are 
respectively . as following![[asy]
/* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */
import graph; size(6cm);
real labelscalefactor = 0.5; /* changes label-to-point distance */
pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */
pen dotstyle = black; /* point style */
real xmin = -1.1338271604938273, xmax = 1.1338271604938273, ymin = -0.6597530864197526, ymax = 0.6597530864197522; /* image dimensions */
pen zzttff = rgb(0.6,0.2,1); pen qqwuqq = rgb(0,0.39215686274509803,0); pen zzttqq = rgb(0.6,0.2,0);
draw((-0.3851851851851852,0.2449382716049378)--(-0.5570370370370371,-0.12839506172839515)--(0.03753086419753081,-0.1501234567901235)--cycle, linewidth(2) + blue);
draw(arc((0.03753086419753081,-0.1501234567901235),0.05925925925925927,136.93680038622105,177.90706569471186)--(0.03753086419753081,-0.1501234567901235)--cycle, linewidth(2) + zzttff);
draw(arc((-0.5570370370370371,-0.12839506172839515),0.05925925925925927,-2.092934305288143,65.28255908891657)--(-0.5570370370370371,-0.12839506172839515)--cycle, linewidth(2) + qqwuqq);
draw(arc((-0.3851851851851852,0.2449382716049378),0.05925925925925927,-114.71744091108341,-43.06319961377892)--(-0.3851851851851852,0.2449382716049378)--cycle, linewidth(2) + zzttqq);
/* draw figures */
draw((-0.3851851851851852,0.2449382716049378)--(-0.5570370370370371,-0.12839506172839515), linewidth(2) + blue);
draw((-0.5570370370370371,-0.12839506172839515)--(0.03753086419753081,-0.1501234567901235), linewidth(2) + blue);
draw((0.03753086419753081,-0.1501234567901235)--(-0.3851851851851852,0.2449382716049378), linewidth(2) + blue);
/* dots and labels */
dot((-0.3851851851851852,0.2449382716049378),dotstyle);
label("$A$", (-0.377283950617284,0.26469135802469085), NE * labelscalefactor);
dot((-0.5570370370370371,-0.12839506172839515),dotstyle);
label("$B$", (-0.6123456790123457,-0.09086419753086432), NE * labelscalefactor);
dot((0.03753086419753081,-0.1501234567901235),dotstyle);
label("$C$", (0.0454320987654321,-0.13037037037037044), NE * labelscalefactor);
label("$Z$", (-0.5155555555555555,0.07901234567901204), NE * labelscalefactor);
label("$X$", (-0.2607407407407408,-0.18962962962962965), NE * labelscalefactor);
label("$Y$", (-0.15407407407407409,0.0711111111111108), NE * labelscalefactor);
label("$\alpha$", (-0.0671604938271605,-0.12246913580246922), NE * labelscalefactor,zzttff);
label("$\beta$", (-0.4938271604938272,-0.09481481481481494), NE * labelscalefactor,qqwuqq);
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle);
/* end of picture */
[/asy]](http://latex.artofproblemsolving.com/1/0/4/104d9ab7a63d435f8d3d54abcfc1518c5889a4b8.png)
.
which means 
.
.
at most one of 
and 
is even for all 
., 
works. Now, for the sake of contradiction, say 
works.
is odd, at least one of 
is even. WLOG, say 
is even.
is even. As 
can't be even, WLOG say 
is even.
is odd but none of 
can be even 
Contradiction. is the maximum value of that works.
which is even and at most one which is even. If 
, there exist two indices 
, such that 
are all odd, and we have that 
is even; it's absolute value cannot be .
is an integer, and let be integers such that for any two integers and satisfying . Determine the maximum possible value of .
. The relation 
means that no two of the 
or 
are even, else the corresponding 
is even, hence cannot be . Thus, atleast 
of the and of the are odd 
of the pairs 
are odd. WLOG, assume that all pairs are odd for 
. Clearly if 
, then 
and 
are odd 
is even, which is a contradiction. Thus, ., a simple construction like 
does the job. Hence is the required answer.
for all (the case where some 
is easy). Assume 
to be ascendingly sorted in that order, and assume 
for all (cause we can change the sign of both and 
), all WLOG. Then we have for all 
,
so 
for all . But that is absurd if , as we get 
and 
, and 
, which gives 
.. Then 
for all 
. Again, WLOG, we can assume 
for all 
. Then each must be . So 
, which is absurd.
and 
work, then the triangle formed by these two pairs and the origin has area .
work.. Then consider a quad 
that is part of this polygon. It must be that 
, , and 
lie at an equal distance from 
. By PHP, two of these three points lie on the same side of . WLOG assume, and are these points. Then 
is a parallelogram. If we repeat this same argument for 
, we get that must lie on the same side of ( and at the same distance from as well) as one of or , forming a parallelogram. Say . Then 
is a parallelogram. As does not lie on , 
and 
(and hence 
as well) cannot have the same area. Contradiction.
, we know that 
for any , by pigeonhole theorem, two of them must have the same value.
hence 
. Note that and 
are coprime, there is 
such that 
and 
(a special attention need to be paid when one of the , is zero)
, implies that 
.
and 
, implies that 
. Contradiction.
nd 
then if a third point must exist should be either of but not all of 
, 
, 
and call this point the "Good Point"
to be 
must be a parallelogram.
the Good Points generated by 6 of the triangles must be unique
is the same for two such triangles say for 
and 
then ![$[OP_1P_2G_1] = [ OP_3P_4G_1] $](http://latex.artofproblemsolving.com/b/c/3/bc3b7b8a1c309fc5efb7910d939f3817bc9895a2.png)
![$[OP_2G_1]=\frac{1}{2}$](http://latex.artofproblemsolving.com/6/e/a/6ea021d63bb5b7dfbcab55771790a4b6599f97aa.png)
and since 
This gives 
is collinear from which arises a contradiction.
. Therefore 
. We have 
for 
. isn't possible. As 
and 
satisfy the hypothesis, this would imply that is the required maximum.
, 
and 
form a basis of 
.
and 
have coordinates 
and 
in the basis 
, that is,![$$\vec v_3=A\begin{pmatrix}\lambda_1\\ \lambda_2\end{pmatrix}\text{and }\vec v_4=A\begin{pmatrix}\mu_1\\ \mu_2\end{pmatrix}\text{, where }A=[\vec v_1,\vec v_2].$$](http://latex.artofproblemsolving.com/6/8/0/6809f30bb85814b7c15821657efaafdf9b3ed59a.png)
.
. Similarly, 
.
which can only take the values 
and 
, a contradiction.
are integers.
is an integer, and let be integers such that for any two integers and satisfying . Determine the maximum possible value of . So both Can never Simultaneously be even. Now let's start with 
is odd for then we must have one of 
even, Say if 
is even, then is odd Then clearly by above relation we need all 
odd for all 
and then is even for all Now if 
then 
will be even and odd respectively but we also have 
which is never possible. Hence contradiction 
in this case. are of different parity say is even and is odd. Then 
so is odd for all is even then is odd for all then if But then 
can never be odd, Contradiction . Similarly we can achieve contradiction when is odd. Hence Max value of is in this case also. is 
are all odd,
is even. is even.
is odd. is odd for all 
.
.....(1),
is odd from (1).
is odd again.
is odd.
, which is a clear contradiction.
.,
and 
is .
and 
remind us of - matrix elements that are reflections of each other in the main diagonal. So let us arrange the numbers as follows for better intuition,
Notice that entries which are reflections of each other (the subscripts) about the main diagonals are of different parity. Assume is even which means all the entries in the first row are odd (except the first entry of course). Say is even then we know both 
and are odd (as 
and 
are reflections of each other) also 
is odd. Here comes the catch if you look closely, both 
and 
are odd which is a contradiction. Hence and for a number of constructions are already given. 
and so 
works as well.
given by 
work. Suppose we had a valid example for 
.
and 
each have at most one even number. Thus, we have at least 
integers 
for which both 
are odd. Picking two such indices, we see that the corresponding determinant has to be even, a contradiction!
during the contest...
be all the set of points .Denote them by 
.
be the point with the maximum sum of coordinates (also note that the coordinates should be co prime).Now see that the area of 
, then 
which gives that either 
or 
which is a contradiction.So no 
can be parallel to 
where ![$[\triangle OP_iP_r]=\frac{1}{2}$](http://latex.artofproblemsolving.com/3/6/6/366891b817aefd5f554815ecf85dab637c920444.png)
.
(copied from above bcoz I'm too lazy)