AoPS Academy
+2 w
and 
be positive integers with 
. There are cupcakes of different flavors arranged around a circle and people who like cupcakes. Each person assigns a nonnegative real number score to each cupcake, depending on how much they like the cupcake. Suppose that for each person 
, it is possible to partition the circle of cupcakes into groups of consecutive cupcakes so that the sum of 's scores of the cupcakes in each group is at least 
. Prove that it is possible to distribute the cupcakes to the people so that each person receives cupcakes of total score at least with respect to .
be the orthocenter of acute triangle 
, let 
be the foot of the altitude from 
to 
, and let be the reflection of across 
. Suppose that the circumcircle of triangle 
intersects line at two distinct points 
and 
. Prove that is the midpoint of 
.
+1 w
be a positive integer, and let 
be nonnegative integers such that 
Prove that![\[
\sum_{i=0}^n i\binom{a_i}{2}\le\frac{1}{2}\binom{a_0+a_1+\dots+a_n}{2}.
\]](http://latex.artofproblemsolving.com/c/4/9/c49d0ccfef69402d05dc44d721172498c605cf7e.png)
Note: 
for all nonnegative integers 
.
balls split into groups of 
Then, after multiplying both sides by 
the left hand side counts the 
groups before the 
group times the pairs of balls, so you can basically send the pair of the -th and 
-th balls in the group of to the -th ball in any of the previous groups and the -th ball of the group. There are 
ways to do this, which is why there is a on the LHS, and basically this creates 
different pairs of balls, so the inequality holds. I barely finished this writeup before time ended but I hope it gets full points.
right?
or 
.
works
Equality holds when 
for 
and 
.
We proceed with induction on 
for all nonnegative integers 
of nonnegative integers satisfying 
for some 
where 
Then, it follows that if we have some 
of non-negative integers satisfying 
then we will have 
It suffices to show that the desired inequality will then hold for the 
-
for any nonnegative integer 
satisfying 
It is easy to show that 
is nonnegative for all nonnegative integers 
and we also know that 
because all of 
are nonnegative. Therefore, it suffices to prove that 
This easily follows from the fact that 
for all 
concluding the inductive step.
,
gives 
.
and 
.![$b=\frac{1}{4}*[(\sum_{i=0}^{n+1}{a_i})^2-\sum_{i=0}^{n+1}{a_i}-(\sum_{i=0}^{n}{a_i})^2+\sum_{i=0}^{n}{a_i}]=\frac{1}{4}[a_{n+1}*(2\sum_{i=0}^{n}{a_i}+a_{n+1})-a_{n+1}]=\frac{a_{n+1}}{2}[\frac{2\sum_{i=0}^{n}{a_i}+a_{n+1}-1}{2}]=\frac{a_{n+1}}{2}[\sum_{i=0}^{n}{a_i}+(\frac{a_{n+1}-1}{2})]$](http://latex.artofproblemsolving.com/7/c/e/7ce63357487ed02032f83131a48b6f2643a7ec93.png)
.![$a=\frac{a_{n+1}}{2}[(n+1)(a_{n+1}-1)]$](http://latex.artofproblemsolving.com/e/a/f/eaf8b279580b810f23ba6c7df45df7b434d4a980.png)
.
.
for 
with the equality case when 
when its actually 
Let 
and introduce a new term 
We have that 
and since 
is nonnegative we have
and since 
Then, we have
Then, divide by 
is there an 
case when the induction looks like this or nah
rooms, with the 
Then 
calculates the number of ways to choose two people from the same room 
and then picking one of them to move either 
rooms down. Then, if the number of the person who went down is 
we find the person in the new room he went to with the same number 
So the end result is this matched person and the person from the intial room who did not move. It is clear that each end result from the process is unique.
counts the number of ways to choose 
and also 
,
condition properly.
which is already more than what we needed thus we are done, equality holds when 
and 
.
![\[ 2n \binom{a_n}{2} \le \binom{a_0 + a_1 + \dots + a_n}{2} - \binom{a_0 + a_1 + \dots + a_{n-1}}{2}. \]](http://latex.artofproblemsolving.com/f/0/6/f06a1f32893b335ec9495fc70e161a02716d9f1e.png)
Rearranging the terms around, that's equivalent to proving 
However, the last line is obvious because 
,
.
and 
for 
![\[ \sum_{i = 0}^n i \binom{a_i}{2} \le \dfrac{\sum_{i = 0}^n i}{(n + 1)^2} \sum_{i = 0}^n \binom{a_i}{2} = \dfrac{n}{2(n + 1)} \sum_{i = 0} \binom{a_i}{2} \le \dfrac{1}{2} \sum_{i = 0}^n \binom{a_i}{2} \le \dfrac{1}{2} \binom{ \sum_{i = 0}^n a_i }{2}\]](http://latex.artofproblemsolving.com/a/5/d/a5d9a1e9ee714c88e4fefc01b02666bac24bb87b.png)
so the inequality becomes ![\[ \sum_{i=0}^n 2ia_i(a_i - 1) \le \left( \sum a_i \right)^2 - \sum a_i. \]](http://latex.artofproblemsolving.com/5/2/f/52f3ca3706e6b9bfd83811f052d7815ac6a9e3af.png)
Now notice that ![\[ a_ia_j \ge a_j^2 \]](http://latex.artofproblemsolving.com/e/8/a/e8abf3ee9377c2cebf58a42a045deec359bb0eaf.png)
for 
.
is 
,
terms where 
is precisely ![\[ \sum_{i = 0}^n -ia_i \le \sum a_i^2 - a_i. \]](http://latex.artofproblemsolving.com/a/5/6/a5668c227a06ec4600cdab63c2895bfe5c762325.png)
![\[ \ln \left( \frac{27abc}{(a+b+c)^3} \right) \le \frac{(a-b)^2+(b-c)^2+(c-a)^2}{3}. \]](http://latex.artofproblemsolving.com/d/e/2/de244e2a3c44720d4f7b27b216af6b3971aad8b2.png)
One wonders: How does one possibly solve this inequality??!?!?!?!? It is simple, dear friend. Notice that ![\[ \ln \left( \frac{27abc}{(a+b+c)^3} \right) \le 0 \le \frac{(a-b)^2+(b-c)^2+(c-a)^2}{3}. \]](http://latex.artofproblemsolving.com/2/7/e/27e4982e412a393bfdc77ad2d21385fddc99073e.png)
![\[ \sum_{i = 0}^n -ia_i \le 0 \le \sum a_i^2 - a_i. \]](http://latex.artofproblemsolving.com/b/c/7/bc77864bb989345a5acdb16656fea1e465d354f3.png)
Through the miracle work of CMJ 1226 we are done.