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 the medial triangle of an acute-angle triangle 
. Suppose the line through 
perpendicular to 
meet 
at 
. Define 
analogously. Let 
. Similarly define 
and 
. Suppose the circle with diameter 
meet the -altitude at 
, where lies inside . Define 
and 
similarly. Let 
be the circumcenter of , and let 
be the circle with diameter 
, which meets 
at 
. Similarly define 
and 
.
are collinear.
lie on a circle centered at .
are coaxial. is perpendicular to the radical axis of .
be the set of all positive integers. Find all functions 
such that for any positive integers 
and 
, the following two conditions hold:
, and
, 
, and 
are equal.
be a triangle with 
. The 
-excircle touches side 
and line at 
and 
, respectively. The 
-excircle touches side at 
. Let lines 
and 
meet at 
. Prove that 
.
be three diameters of the circumcircle of an acute triangle . Let be an arbitrary point in the interior of , and let 
be the orthogonal projection of on 
, respectively. Let 
be the point such that is the midpoint of 
, let 
be the point such that is the midpoint of 
, and similarly let 
be the point such that is the midpoint of 
. Prove that triangle 
is similar to triangle .
of positive integers such that 
.
players. Every player played every other player once, with no draws. In addition, each player had a numerical rating before the tournament began, with no two players having equal ratings. It turns out there were exactly 
games in which the lower-rated player beat the higher-rated player. Prove that there is some player who won no less than 
and no more than 
games.
, 
, and 
be positive integers. Prove that ![\[ \sum_{i = 1}^n \min\left(\left\lfloor \frac{x}{i} \right\rfloor, m \right) = \sum_{i = 1}^m \min\left(\left\lfloor \frac{x}{i} \right\rfloor, n \right). \]](http://latex.artofproblemsolving.com/b/7/a/b7aebfe11f646d604d2e8cb9d5bd70ec796949e8.png)
of points in the plane is balanced if, for any two different points and in , there is a point in such that 
. We say that is centre-free if for any three different points , and in , there is no points in such that 
.
, there exists a balanced set consisting of points. for which there exists a balanced centre-free set consisting of points.
such that
are all powers of 
. be an integer and let 
be the complete graph on vertices. Each edge of is colored either red, green, or blue. Let denote the number of triangles in with all edges of the same color, and let denote the number of triangles in with all edges of different colors. Prove![\[ B\le 2A+\frac{n(n-1)}{3}.\]](http://latex.artofproblemsolving.com/6/5/9/659d0199c3d685d43f1ced3704dfa59b02b586b3.png)
(The complete graph on vertices is the graph on vertices with 
edges, with exactly one edge joining every pair of vertices. A triangle consists of the set of 
edges between 
of these vertices.)
such that the equation ![\[x^{2}-(a^{2}+b^{2}+c^{2}+d^{2}+1)x+ab+bc+cd+da=0 \]](http://latex.artofproblemsolving.com/9/0/4/904d1b23d5c744118a7d68df1e2e94bddac8c1cd.png)
has an integer solution. Prove that the other solution is integer too and both solutions are perfect squares.
be a triangle such that![\[ \left( \cot \dfrac{A}{2} \right)^2 + \left( 2\cot \dfrac{B}{2} \right)^2 + \left( 3\cot \dfrac{C}{2} \right)^2 = \left( \dfrac{6s}{7r} \right)^2, \]](http://latex.artofproblemsolving.com/6/9/b/69b1964be5f92eb44a36b0b8604bf473fe27e210.png)
and 
denote its semiperimeter and its inradius, respectively. Prove that triangle is similar to a triangle 
whose side lengths are all positive integers with no common divisors and determine these integers.
be an acute-angled triangle with circumference 
. Let the angle bisectors of 
and 
intersect again at 
and . Let 
be the intersection point of these angle bisectors. Let 
and 
be the respective reflections of and in and . Prove that the center of the circle passing through , , lies on the altitude of triangle from ., there is exactly one card in the deck that has written on it. Now two players draw disjoint sets and of 
cards each from this deck. We would like to define a rule that declares one of them a winner. This rule should satisfy the following conditions:
cards: if the cards are laid down in increasing order face down and we are told which card belongs to which player, but not what numbers are written on them, we can still decide the winner.
and 
, and 
for all 
, then beats .
from the deck, beats and beats then also beats . and such that beats according to one rule, but beats according to the other.
, let 
be the maximal number for an -gon, and for convenience set 
. Suppose the -gon has vertices 
, 
, ..., 
. Certainly, any optimal configuration contains at least one pair of crossing diagonals, say 
and 
. To any such configuration we can add the diagonals 
, 
, 
and 
if they do not already appear without creating any new crossings. Moreover, doing so makes clear that the problem decomposes into four smaller versions of the same problem, with , 
, 
and 
vertices. It follows immediately that![\[
f(n) = 6 + \max_{\substack{i, j, k \\ 1 < i < j < k \leq n}}( f(i) + f(j - i + 1) + f(k - j + 1) + f(n + 2 - k)).
\]](http://latex.artofproblemsolving.com/9/9/2/9928c1e79742876d8d65aff0734f2d5b88d50a56.png)
.
.
for example. If the pentagon is 
, we can draw 
in that order. This yields 
diagonals. In your formula, 
. 
is the last diagonal drawn, and 
is the only one crossing it, we can induct on the two polygons 
and 
, after which we are essentially done. 
. Base cases are obvious. Now, assume we have diagonals drawn on points 
. WLOG add point 
after and before . Then we can draw diagonals 
and then 
in that order. is the maximum, draw two n-gons side by side, each with diagonals that never cross. At best, we can get 
in each, super-imposing them gives is the best -- if any side has more, then we would have to draw a diagonal with two intersections.
. 
and 
cases are trivial.Now consider and 
.By considering the last drawn diagonal and by induction hypotesis(strong induction) applied on polygon the last diagonal divides the and of course adding for the last diagonal and the diagonal that is intersected by it we easily obtain: .
subsets such that no diagonals from the same subset intersect each other.It is done by greedy algorithm.Let the first diagonal drawn be colored blue.Now for every next diagonal drawn if it intersects a blue diagonal we color it red.Otherwise we color it blue.Now we easily see that no blue diagonals or red diagonals intersect each other so we proved that our subsets exist.Now number of diagonals in both subsets is 
so the maximum number is 
.Then we just give an example which is not hard.
. Let the polygon be 
. Now, go with 
and then 
for 
through 
. The only diagonals that can cross are 
and 
, the second of which comes after. On the other hand, the only diagonal that can ever cross is . Hence, this construction works. is the largest possible value. Let the answer for an -gon be , and observe that 
, 
. We use induction. Now look at the last drawn diagonal, and let it divide the polygon into an -gon and a -gon, where 
. Now see that there can be at most one diagonal that crosses the diagonal, and that the maximal number of diagonals completely within the -gon and the -gon sum to 
. Hence, it is clear that ![\[ f(n) \le f(a) + f(b) + 2 = 2(a+b-6) + 2 = 2(n-4) + 2 = 2(n-3) \]](http://latex.artofproblemsolving.com/8/9/7/897c7f127490a2070aa8c1ce47f4c2c1e46ecb7b.png)
, so our induction is complete and the answer is , as desired.
diagonals for general . Let the polygon be 
.
diagonals 
for 
, where indices are cyclic. Then, construct 
diagonals 
for 
, in that order.
be the last diagonal that was drawn. Then, intersects at most one other diagonal. All other diagonals must be contained in a 
-gon or 
-gon that partitions the -gon into, where 
. Thus, by the inductive hypothesis, the number of diagonals 
as needed.
.
-gon is . As a construction, in polygon 
, draw 
for 
and for 
, where indices are modulo .
. Let the final diagonal drawn in a -gon be . Note that intersects at most 
other diagonal by the problem condition. Furthermore, suppose that splits the -gon into an 
-gon and a 
-gon such that 
and 
. The total number of diagonals is hence![\[(2(a+1)-6)+(2(b+1)-6)+2=2a+2b-6=2k-6,\]](http://latex.artofproblemsolving.com/d/a/5/da5cbf33ba463e9cec4c4a5abcf94ce80e7a5e51.png)
into the general formula yields 
.
. The answer is diagonals. We proceed by using strong induction. The base cases and can be checked by hand.
be the diagonal that we draw last. There is at most one more diagonal that intersects . divides the points into 
and 
points (the two partitions are disjoint, except that they both share the common points of ), then we get that the maximum number of diagonals is,![\[ \le (2p-6) + (2q-6) + 2= 2p + 2q -10 = 2(p+q-2) -6. \]](http://latex.artofproblemsolving.com/a/0/7/a0702a76fa24ec52a65ba06a74bf00555353faa9.png)
in the first step are due to counting the two diagonals and 
.
-gon is 
. We will prove this using induction.
-side, this is obviously true.
sided polygon and a 
sided polygon. Note that 
.-sided polygon and the -sided polygon) is
.(we add two, because we count the last diagonal and the diagonal that intersects the last diagonal)
so we are done.
gon. Let 
denote the maximum number of diagonals Peter can draw for a gon. We proceed via induction.
since that is the maximum number of total diagonals we can draw in a quadrilateral (and you can draw both without any issue). Now, consider a gon for 
. Assume that for all 
we have that 
. Then, we simply consider the last diagonal drawn in the gon. This separates the gon into two polygons with 
and 
vertices each such that 
. Then,![\[d(n) = 2 + d(a+2)+d(b+2)= 2+ 2(a-1)+2(b-1)=2(a+b-1) = 2((a+b+2)-3)=2(n-3)\]](http://latex.artofproblemsolving.com/1/8/c/18c9ec46f708e456064e0313ca012066e8a9cb2e.png)
(Here the leading +2 is due to the last drawn diagonal and the one and only diagonal with intersects it (if there are two or more we are not able to draw the last diagonal)). Thus, the induction is complete.
gon is![\[d(2011)=2(2011-3)=2(2008)=4016\]](http://latex.artofproblemsolving.com/d/0/2/d029f5ac2b1f01dda1dd1b971502a5ca0088540f.png)
diagonals.
for any -gon. We can prove this bound and constructability through strong induction.-gon satisfies the inductive hypothesis given that 3-, 4-, 
, 
-gons all hold. Note that the last diagonal drawn divides the -gon into an -gon and a 
-gon. Also, this final diagonal must only intersect with at most one other diagonal, so our maximum bound is![\[(2m-6) + (2(k+2-m)-6) + 2 = 2k - 6,\]](http://latex.artofproblemsolving.com/8/0/2/8028640f8667299d53255d27735fbd2cda29ef2d.png)
(in order) and setting as the final diagonal and 
as the only diagonal crossing . We are left with a -gon that we can start constructing by drawing edges from , so we indeed have 
diagonals. 
-gon the greatest number of diagonals that can be drawn is . Base cases 
work.-gon into a 
-gon and a 
-gon where 
We also know that since most one diagonal intersects the last diagonal, at most one diagonal goes between the and gons. Thus, the maximal diagonals is 
diagonals is achievable for -gon. There exists a vertex, 
, on the -gon such that the number of diagonals going through it is at most (can be easily shown by contradiction). Let the neighbors of be 
Now to construct our -gon, insert a new vertex, beween and 
Finally draw the edges 
then 
This -gon will have 
edges, ad desired. \qed
but if you consider 
intersections, the answer appears to be 
...
. In a cylic fashion starting with , draw for 
in that order. Now from 
for 
in that order. This gives 
. gon into an gon and 
gon obviously. Then, we have a maximum of 
.
We proceed with induction on 
The base cases, are trivial. Now suppose that the proposition holds for all 
for some positive integer 
Then consider a 
-gon. Note that the last diagonal drawn intersects with at most one other diagonal. If this last diagonal separates the polygon into an -gon and a 
-gon, then by the inductive hypothesis we have at most 
Thus the bound is proven. For the construction, just consider construct diagonals of the form 
for 
and then diagonals of the form for 
Thus the induction is complete, so is indeed the answer.
yields 
yields 
work. Now, draw a diagonal through the 
gon. Then this gives us a new maximum of 
.
.
.
.