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 real numbers, such that 
and 
. Determine the value of 
.
, determine the smallest integer 
, such that it is possible to place numbers 
around a circle so that the sum of every consecutive numbers takes one of at most values.
, , be real numbers such that and 
. Prove that 
Let , , be real numbers such that and 
. Prove that 
be a positive integer such that divides the sum![\[
1 + \sum_{i=1}^{n-1} i^{n-1}.
\]](http://latex.artofproblemsolving.com/e/2/d/e2daf7800da3f984cd761ed1fecf10083444db25.png)
Prove that is square-free.
. 
amount of people stand on coordinates 
where 
. Every person got a water cup and two people are considered to be neighbour if the distance between them is 
. At the first minute, the person standing on coordinates 
got litres of water, and the other 
people's water cup is empty. Every minute, two neighbouring people are chosen that does not have the same amount of water in their water cups, and they equalize the amount of water in their water cups. will not have more than 
litres of water.
be an integer. You have two 
boards. Each board contains the numbers to inclusive, one number per square, arbitrarily arranged on each board. A move consists of exchanging two rows or two columns on the first board (no moves can be made on the second board). Show that it is possible to make a sequence of moves such that for all 
and 
, the number that is in the 
row and 
column of the first board is different from the number that is in the row and column of the second board.
be a convex pentagon such that![\[ \angle BAC = \angle CAD = \angle DAE\qquad \text{and}\qquad \angle ABC = \angle ACD = \angle ADE.
\]](http://latex.artofproblemsolving.com/d/3/d/d3d9a82f4318190298a8f008d417a364e03f1fca.png)
The diagonals 
and 
meet at 
. Prove that the line 
bisects the side 
.
, with 
, 
is the incenter, 
is the intersection of 
-excircle and 
. Point 
lies on the external angle bisector of 
such that and lieas on the same side of the line 
and 
. Point 
lies on such that 
. Circle 
is tangent to 
and 
at 
, circle 
is tangent to and 
at 
and both circles pass through the inside of triangle . if 
is the Midpoint od the arc , which does not contain , prove that lies on the radical axis of and .
be a sequence of positive real numbers, and 
be a positive integer, such that![\[a_n = \max \{ a_k + a_{n-k} \mid 1 \leq k \leq n-1 \} \ \textrm{ for all } \ n > s.\]](http://latex.artofproblemsolving.com/f/1/2/f12c9c5e0f154549118a33a2f359329333f432a7.png)
and 
, such that![\[a_n = a_{\ell} + a_{n - \ell} \ \textrm{ for all } \ n \geq N.\]](http://latex.artofproblemsolving.com/b/0/b/b0b2bd4507621302eeee27ae50ed9c0afd72c6ef.png)
and on a given circle meet at point . Let be a point on segment and let 
meet the circle again at . The line through 
parallel to intersects at 
. Prove that 
is parallel to if and only if 
.
, 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.
.
.
Where 
,
,
.![\[\sum_{i=1}^{n}\frac{1}{1+x_{i}}\cdot \sum_{i=1}^{n}x_{i}\leq \sum_{i=1}^{n}\frac{x_{i}^{k+1}}{1+x_{i}}\cdot \sum_{i=1}^{n}\frac{1}{x_{i}^{k}}\]](http://latex.artofproblemsolving.com/2/6/4/264d110e2a40c7f787c650aa8b8dc30af5d28263.png)
yields 
yields 
work. Now, draw a diagonal through the 
gon and an 
gon. Then this gives us a new maximum of 
.
.
.
.