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.
+1 w
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?
interesting if is composite and for every divisor 
of at least one of 
and 
is also a divisor of with 
, such that 
and 
.
such that 
is prime, 
with 
and ?
be an acute triangle with orthocenter 
and circumcenter 
. Let 
and 
be points on the line segments 
and 
respectively such that 
is a parallelogram. Prove that 
.
that satisfy 
for all 
and 
satisfies the following recursion formulas: 
, 
and 
. Find 
and 
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 
.
be an acute triangle with 
the feet of the altitudes lying on 
respectively. One of the intersection points of the line 
and the circumcircle is 
The lines 
and 
meet at point 
Prove that 
cities, 
airline companies in a country. Between any two cities, there is exactly one -way flight connecting them which is operated by one of the two companies. A female mathematician plans a travel route, so that it starts and ends at the same city, passes through at least two other cities, and each city in the route is visited once. She finds out that wherever she starts and whatever route she chooses, she must take flights of both companies. Find the maximum value of .
be inscribed in the circumcircle 
and circumscribed about the incircle 
, with 
. The incircle touches the sides , 
, and at 
, , and , respectively. A line through 
, perpendicular to 
, intersects , , and at 
, 
, and 
, respectively. The line meets at 
(distinct from ). The circumcircle of triangle 
intersects at 
(distinct from ). Let 
be the midpoint of the arc 
of . The line cuts segments and 
at 
and 
, respectively, and the tangents to the circle 
at and intersect at 
. Prove that 
.
known by both players, Arnaldo picks a number 
but doesn't tell it to anyone. Bernaldo thens pick an arbitrary positive integer 
(not necessarily in ). Then Arnaldo tells the number of divisors of 
. Show that Bernaldo can choose in a way that he can find out the number 
chosen by Arnaldo.
such that for any vertex of the polygon, the reflection of across is also a vertex of the polygon
of the polygon such that the area of 
is maximum over all possible pairs of vertices. Wlog we may consider that 
and 
, since an afine transformation preserves the ratios between areas. Let 
be the symmetric of with respect to . Draw a rectangle with sides parallel to 
and circumscribed to the polygon, such that on each one of its sides there is at least one vertex of the polygon. The area of this rectangle is 
, where 
is the sidelength of 
, and 
are the distances from the sides of the rectangle respectively parallel to 
, and . This rectangle is the result of applying the initial afine transformation to a parallelogram since afine transformations preserve parallelism. Note that the area of the polygon is at least 
, ie the area of , plus at least the area of four triangles, one of which has vertices , and the vertex where the polygon touches the rectangle side parallel to , and the other three are analogously constructed on sides 
. Consider also the square whose sides are the perpendiculars to the diagonals 
and 
, through and 
, and through 
and , respectively. Clearly this square contains the polygon inside, otherwise the area of is not maximum, and the square has area 
.
and 
. From the first inequality we find that 
, and from the second one, 
, and when inserting the first one into the second one, we obtain 
, clearly false because of the AM-GM inequality. The conclusion follows, equality being reached simultaneously for the square and rectangle considered, and only if the original polygon is an octagon where, after the afine transformation, 
.
be a polygon that is convex and symmetric to some point . Prove that for some parallelogram 
satisfying 
we have ![\[\frac{|R|}{|P|}\leq \sqrt 2\]](http://latex.artofproblemsolving.com/9/c/8/9c8c175d6318a9c71a2e9a00783f12dcbc2dabc6.png)
and 
denote the area of the sets and , respectively.
, but it's hard to prove. is the best bound. Consider the regular hexagon.
be a polygon that is convex and symmetric to some point . Prove that for some parallelogram satisfying we have and denote the area of the sets and , respectively.
times the area of the polygon, and the area of either of the two parallelograms considered. Clearly, picking other choices for parallelograms probably improves the bound. I do not know however if a smart parallelogram choice that can be worked out in "competition time" can improve the bound significantly, so I guess the problem itself as it is, is a good IMO problem, but finding the best bound is a more time-consuming task. The bound seems pretty good, if I have some free time I'll try to kick it around and see if something comes up.
, but it's hard to prove. is the best bound. Consider the regular hexagon.
, denote 
as the reflection of through . Also, if 
is a support line of P, then 
is the other support line parallel to . and 
, denote 
as the parallelogram bounded by the four lines. Finally, let 
be the minimum value of all parallelograms which cover . and , and on , on . Then if is a support line parallel to , and is on , then 
. Now consider the value of 
for a point , traveling on a path from to inside . That value ranges from zero to greater than or equal to 
, so there must exist some point so that 
. and 
parallel to and 
, and points and 
on and respectively. If the ratios of the correspondingly parallel sides of 
to the sides of 
are and respectively, then 
, so 
. Also 
. (Take the sum of 
and the four triangles facing outward from the sides.)
.
and 
and prove at least one of them has area at most 
.
of such that triangle has the maximal area. Let and be reflections of and across , respectively, and let 
denote the parallelogram 
. Consider the lines through and parallel to 
, and the lines through and parallel to 
; these four lines form a parallelogram 
. Let 
be the minimal parallelogram containing whose sides are all parallel to sides of . An example is drawn below, where the boundary of is colored red and the boundary of is colored blue:![[asy]
size(7cm);
pair A = (1.16,4.24);
pair B = (-5.37,-0.8);
pair A1 = (-0.68,3.77);
pair A2 = (-4.38,1.45);
pair A3 = (-3.09,-3.92);
pair E = (-4.22,3.43);
pair F = (6.53,5.04);
pair G = (1.01,5.61);
pair H = (-7.1,-0.65);
draw(A--A1--A2--B--A3--(-A)--(-A1)--(-A2)--(-B)--(-A3)--cycle);
draw(E--F--(-E)--(-F)--cycle,red);
draw(G--H--(-G)--(-H)--cycle,blue);
draw(A--(-A));
draw(B--(-B));
draw(A--B--(-A)--(-B)--cycle);
draw(F--origin--E);
dot((-3.04,2.48));
dot((4.05,3.13));
label("$A$",A,N);
label("$B$",B,NW);
label("$C$",(-A),S);
label("$D$",(5.37,0.8), SE);
label("$E$",E,NW);
label("$F$",F,NE);
label("$E'$",0.5*E,S);
label("$F'$",0.5*F,S);
label("$G$",(-3.04,2.48),N);
label("$H$",(4.05,3.13),N);
label("$G'$",A2,N);
label("$H'$",(-A3),N);
label("$O$",origin,SE);
[/asy]](http://latex.artofproblemsolving.com/6/4/1/641ab75d38de67b523d017317cfa79d53225594b.png)
, and 
.
lies outside ; then either 
or 
, contradiction. Because is the midpoint of side , it follows that . in terms of 
. Suppose the boundary of touches polygon at points 
(and their reflection about ) as labeled on the diagram; because is convex, 
and 
(the measured angles represent the set of points inside or on the boundary of that angle). Let 
be intersections of 
with the boundary of , and let 
, 
. Then
Now we are almost done: observe that 
, so 
so at least one of 
and 
is less than or equal to .
of minimal area which contains . We shear/dilate the figure as a whole until is transformed to the unit square. Call the two heights of going through 
(vertical) and 
(horizontal)., 
, which is an angle 
away from , we know that the parallelogram induced by the lines perpendicular to , has to have area at least 
. So, 
. So, the foot of must lie on the exterior of the circle centered at the midpoint of and passing through (by polar coordinates). We get similar results for 
, so the feet from to any side of the polygon must lie outside the region shown:![[asy]
pair A,B,C,D; A=(1,0);B=(0,1);C=(-1,0);D=(0,-1);
draw(A--B--C--D--A,dotted); draw(A--C);draw(B--D);
label("$h_1$",(0,0.5),W);
label("$h_2$",(0.5,0),S);
draw(arc((0,0.5),0.5,0,180),red);
draw(arc((-0.5,0),0.5,90,270),red);
draw(arc((0,-0.5),0.5,180,360),red);
draw(arc((0.5,0),0.5,-90,90),red);
[/asy]](http://latex.artofproblemsolving.com/6/6/8/668d68b5cabad6f281a20f5a6f18fe0d262dc72f.png)
, are the diameters of these circles, if the foot of an altitude is on the perimeter of this region, the extended side touches one of the vertices of the inner square - so it lies completely outside of the square. Hence, every edge of lies outside of the square, so contains this square.![[asy]
pair A,B,C,D; A=(1,0);B=(0,1);C=(-1,0);D=(0,-1);
draw(A--B--C--D--A,dotted); draw(A--C);draw(B--D);
draw((0.7,0.7)--(0,0)--(-0.8,0.8),dashed);
draw((1,1)--(-1,1)--(-1,-1)--(1,-1)--(1,1));
draw((1,0.4)--(0.4,1));
draw((-1,0.6)--(-0.6,1));
label("$x$",(0.4,0.4),SE);
label("$y$",(-0.4,0.4),SW);
dot((0.9,0.5)); dot((-0.7,0.9));
draw((-1,0)--(-0.7,0.9)--(0,1)--(0.9,0.5)--(1,0));
label("$h_1$",(0,0.5),W);
label("$h_2$",(0.5,0),S);
draw(arc((0,0.5),0.5,0,180),red);
draw(arc((-0.5,0),0.5,90,270),red);
draw(arc((0,-0.5),0.5,180,360),red);
draw(arc((0.5,0),0.5,-90,90),red);
[/asy]](http://latex.artofproblemsolving.com/9/3/6/9366b739f80d7280544a91c0ba478e176dfbd40c.png)
in quadrant I which is the furthest from in the 
direction, and call its distance along that direction . Similarly, consider the distance to the furthest point along the 
direction 
. By minimality of , we should have 
. However, note that these vertices add at least the two triangles shown in the figure to . Taking into account symmetry, we have that ![$$[P]\ge\frac{1}{2}+\frac{\sqrt{2}}{2}\left(x+y-\frac{\sqrt{2}}{2}\right)\ge \frac{1}{2}+\frac{\sqrt{2}}{2}\left(1-\frac{\sqrt{2}}{2}\right)=\frac{\sqrt{2}}{2}$$](http://latex.artofproblemsolving.com/c/7/4/c7476ba52c057ca6370946a529b11a2e557b863f.png)
Hence, 
, as desired.
is a parallelogram that contains 
, is symmetric across , and has minimal area. It's clear that each side of 
must contain at least one vertex. If there is a side that contains exactly one vertex 
, then we perturb that side to be coincide with a side of incident to . It's easy to see that one of the two choices results in the smaller or same area. Therefore, we assume that each side of must coincide with a side of . is a square. As shown in the figure below, let 
and 
be a side of contained in 
(
are in this order). We claim that the midpoint 
of must lie in . Assume not; WLOG, let 
. We can see that pertubing the side to 
so that 
results in with a smaller area, contradiction.![[asy]
size(6cm);
defaultpen(fontsize(10pt));
pair A = (0,1);
pair B = (1,1);
pair C = (1,0);
pair D = (0,0);
pair W_1 = (0.6,1);
pair W_2 = (0.75,1);
pair W = (0.5,1);
pair A_1 = (0,0.7);
pair B_1 = extension(A_1,W_1,B,C);
pair C_1 = (1,1)-A_1;
pair D_1 = (1,1)-B_1;
filldraw(A_1--W_1--W_2--(1,0.9)--C_1--(1,1)-W_1--(1,1)-W_2--(0,0.1)--D--cycle,yellow+opacity(0.5),dashed);
draw(A--B--C--D--cycle,linewidth(1.5));
draw(A_1--B_1--C_1--D_1--cycle);
dot('$A$',A,NW);
dot('$B$',B,NE);
dot('$C$',C,SE);
dot('$D$',D,SW);
dot('$W_1$',W_1,dir(280));
dot('$W_2$',W_2,S);
dot('$W$',W,1.5*N);
dot("$A'$",A_1,dir(180));
dot("$D'$",D_1,dir(180));
dot("$B'$",B_1,E);
dot("$C'$",C_1,E);
label("\Large$\mathcal{P}$",(0.5,0.5));
[/asy]](http://latex.artofproblemsolving.com/c/0/3/c034a36d4a6c6b925c8ef41872ec818120abbc0f.png)
. Similarly, midpoint 
of 
, respectively lie on a side of 
. Now, we consider another parallelogram 
which is symmetric across , and whose each side subtend an angle of 
to the sides of , and with minimal area. Clearly, the sides of 
must pass through a vertex. Let 
be those vertices in the northwest, northeast, southeast, and southwest, respectively.![[asy]
size(6cm);
defaultpen(fontsize(10pt));
pair A = (0,1);
pair B = (1,1);
pair C = (1,0);
pair D = (0,0);
pair W = (A+B)/2;
pair X = (B+C)/2;
pair Y = (C+D)/2;
pair Z = (D+A)/2;
pair B_1 = (0.85,0.85);
pair A_1 = (0.25,0.85);
pair C_1 = (1,1)-A_1;
pair D_1 = (1,1)-B_1;
pair W_1 = extension(A_1,A_1+(1,1),B_1,B_1+(1,-1));
pair X_1 = extension(C_1,C_1+(1,1),B_1,B_1+(1,-1));
pair Y_1 = (1,1)-W_1;
pair Z_1 = (1,1)-X_1;
filldraw(W--B_1--X--C_1--Y--D_1--Z--A_1--cycle,yellow,dotted);
draw(A--B--C--D--cycle,linewidth(1.5));
draw(W_1--X_1--Y_1--Z_1--cycle);
dot('$A$',A,NW);
dot('$B$',B,NE);
dot('$C$',C,SE);
dot('$D$',D,SW);
dot('$W$',W,dir(75));
dot('$X$',X,dir(10));
dot('$Y$',Y,S);
dot('$Z$',Z,dir(180));
dot('$A_1$',A_1,NW);
dot('$B_1$',B_1,NE);
dot('$C_1$',C_1,SE);
dot('$D_1$',D_1,SW);
label("\Large$\mathcal{P}$",(0.5,0.5));
[/asy]](http://latex.artofproblemsolving.com/3/0/a/30a6d366ea951e980e7790cccb1e124c819c1b97.png)
, and let the length of the sides of that contains 
are 
respectively; therefore 
by minimality. Then, we can bound the area of as![\begin{align*}
[\mathcal{P}] &\geq [WXYZ] + 2([A_1WZ] + [B_1WX]) \\
&= 2 + 2\left(\frac 12 \cdot \sqrt{2}\cdot \left(b-\frac{\sqrt 2}{2}\right)
+ \frac 12 \cdot \sqrt{2}\cdot \left(a-\frac{\sqrt 2}{2}\right)\right) \\
&= \sqrt{2}(a+b) \\
&\geq 2\sqrt{2}
\end{align*}](http://latex.artofproblemsolving.com/f/4/f/f4f2d1eb2ac1772caef26f3779666489e4e38502.png)
or already satisfies the condition.
symmetric about with interior . For any point 
, let 
be the line tangent to at , and let 
be the symmetric point about . Perturb by an infintesmal amount so that has no inflection points, or that the rate of change of the direction of is never 
. Note that 
. For any points 
, let 
be the parallelogram bounded by the lines 
. Note that ![\[\mathcal{R}(A,B) = \mathcal{R}(\pm A,\pm B).\]](http://latex.artofproblemsolving.com/4/a/9/4a96a970fca89b05abe1b68593f3a969a7fe310a.png)
We suppose that the problem is false, so we have ![\[[\mathcal{R}(A,B)]> \sqrt{2}\cdot [\mathcal{P}]\]](http://latex.artofproblemsolving.com/2/a/2/2a2c7fec996b004c0c3a7d5ce2b77720b0b1bde9.png)
for all .![$(A,B)\mapsto [\mathcal{R}(A,B)]$](http://latex.artofproblemsolving.com/c/1/6/c1681c038eed4c3523b03b9226eaa1c2c6d1a2ab.png)
is a continuous function from the compact set 
to 
, so there exists some pair 
for which ![$[\mathcal{R}(A,B)]$](http://latex.artofproblemsolving.com/a/5/f/a5f3a712d77610e62a10e452169313f26c291ea6.png)
is minimized. We have the following crucial claim.
and 
.
such that 
. Indeed, by compactness, we may pick such that 
is maximized, and it is easy to see that if 
is not perpendicular to 
, then there is some direction we can slide along to increase . be the -axis, with the origin. Let 
be the curve in the upper half plane. We know 
exists since as varies from 
to in the upper half plane, the slope of varies monotonically from 
to 
, so we can integrate to find , and there won't be any issues since is never hit besides at the boundary.
with 
and 
with 
, we may assume that 
and 
for some 
. We first assume that 
(i.e. 
).
vary in some small open neighborhood of , and abuse notation by letting 
and 
. Let be the point on 
such that 
, and let be the point on such that 
. Finally, let 
. Note that ![\[[\mathcal{R}(A,B)] = 4\cdot[OPTQ].\]](http://latex.artofproblemsolving.com/0/e/9/0e9d9416876fdedefa89b450785c7d9ea551535b.png)
It is not hard to check that ![\[P=\left(\frac{x_2f'(x_2)-f(x_2)}{f'(x_2)-f'(x_1)},\,\,\,f'(x_1)\cdot\frac{x_2f'(x_2)-f(x_2)}{f'(x_2)-f'(x_1)}\right)\]](http://latex.artofproblemsolving.com/0/8/b/08baa0f94eb6f8be73a45e1bf3f6106491b36fff.png)
and ![\[Q=\left(\frac{x_1f'(x_1)-f(x_1)}{f'(x_1)-f'(x_2)},\,\,\,f'(x_2)\cdot\frac{x_1f'(x_1)-f(x_1)}{f'(x_1)-f'(x_2)}\right),\]](http://latex.artofproblemsolving.com/5/d/4/5d4533f3262df85b3fbd430bd6e155d773042643.png)
and thus that ![\[[OPTQ]=\left|\frac{[x_1f'(x_1)-f(x_1)]\cdot[x_2f'(x_2)-f(x_2)]}{[f'(x_1)-f'(x_2)]^2}\right|.\]](http://latex.artofproblemsolving.com/f/b/6/fb61c7d750959508cb51ed0d078e3cb480324de7.png)
Clearly the value of ![$[OPTQ]$](http://latex.artofproblemsolving.com/1/6/0/1604f2587b369ec9826c0961071cef1e53d9f998.png)
is continuous, and nonzero at , so we may select our neighborhood small enough such that the absolute value imparts a consistent sign over the neighborhood. Since is a local maximum, we must have that ![\[\frac{\partial}{\partial x_1}[OPTQ] = \frac{\partial}{\partial x_2}[OPTQ] = 0.\]](http://latex.artofproblemsolving.com/8/d/8/8d8f8c911a667b86761269d1d6dc37b947c063b0.png)
Supposing WLOG that the sign imparted by the absolute value is positive, we see that ![\begin{align*} \frac{\partial}{\partial x_1}[OPTQ] &= [x_2f'(x_2)-f(x_2)]\cdot\frac{x_1f''(x_1)[f'(x_2)-f'(x_1)] - [x_1f'(x_1)-f(x_1)]\cdot(-f''(x_1))}{[f'(x_1)-f'(x_2)]^2} \\ &= [x_2f'(x_2)-f(x_2)]\cdot\frac{f''(x_1)\cdot[x_1f'(x_2)-f(x_1)]}{[f'(x_1)-f'(x_2)]^2}. \end{align*}](http://latex.artofproblemsolving.com/b/3/2/b32dbb18b733dab34550ac8c3825f355d91846cd.png)
Since is nonzero, we see that 
is nonzero, and furthermore 
is nonzero since we assumed that has no inflection points. Therefore, we have ![\[f'(x_2)=f(x_1)/x_1,\]](http://latex.artofproblemsolving.com/1/4/4/144f9c9fabf050da44854f802e0b7a6448f09172.png)
which says exactly that . We may derive the other relation in a similar manner.
, we may do a similar proof, where we now only vary in a neighborhood of , and a similar calculation yields that 
, and thus 
by Rolle's theorem. This completes the proof of the claim. 
. The above claim implies that 
is a parallelogram, and that ![\[[\mathcal{R}(A_m,B_m)] = 4\cdot[OA_mTB_m].\]](http://latex.artofproblemsolving.com/5/3/7/537e48c7901e387a4261348e0d6b1f2c7c0098d3.png)
Take an affine transformation so that is a unit square, and let 
, where is the line through parallel to 
. Note that and are on the same arc bounded by and 
, so WLOG that they are both above 
. Let be the unique point above on such that 
. Furthermore, note that is tangent to 
and 
at and , so is above . is convex, so its upper half contains the convex hull of 
, which has area ![\[\frac{1}{2}y\frac{1}{\sqrt{2}}\cdot 2+\frac{1}{2} + \frac{1}{2}\sqrt{2}\left(h-\frac{1}{\sqrt{2}}\right) = \frac{y+h}{\sqrt{2}},\]](http://latex.artofproblemsolving.com/e/0/3/e031e0ff53d30eb03deb12954faa23094c3b4e4c.png)
so ![\[[\mathcal{P}]\ge \sqrt{2}\cdot(y+h).\]](http://latex.artofproblemsolving.com/f/b/9/fb948b0fec94b3d745fff7688f4218b089feb44a.png)
We have ![\[4=[\mathcal{R}(A_m,B_m)]> \sqrt{2}\cdot [\mathcal{P}] = 2(y+h),\]](http://latex.artofproblemsolving.com/2/6/2/26237a961151769f9ac1cbb4af3f38fe6f67ec61.png)
so 
. Now, ![\[[\mathcal{R}(H,Y)]\le 4yh,\]](http://latex.artofproblemsolving.com/c/a/c/cac01b3ac4fbcb4788dad9668de0efec9d92974f.png)
so we also have ![\[4yh>2(y+h),\]](http://latex.artofproblemsolving.com/4/7/7/4777d5d27afd95943ae8887e52a898a945fead2c.png)
or 
. Thus, by AM-HM ![\[\frac{y+h}{2}\ge \frac{2yh}{y+h}>1,\]](http://latex.artofproblemsolving.com/1/5/a/15a07812338f742805d1d7531bb465a0d5ad1cc1.png)
which contradicts . This is the desired contradiction, so the proof is complete.
