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.
with 
, points 
are such that 
and 
and 
, and 
and 
, as shown on the picture. Suppose that 
is a right angle. Prove that the points 
are collinear.
be positive reals. Prove that![\[ \frac{(a-b)(a-c)}{2a^2 + (b+c)^2} + \frac{(b-c)(b-a)}{2b^2 + (c+a)^2} + \frac{(c-a)(c-b)}{2c^2 + (a+b)^2} \geq 0. \]](http://latex.artofproblemsolving.com/6/9/3/6937791380a8642edca3e773dc72dbf3f0e0f206.png)
are positive real numbers such that 
, prove that ![\[ (1+a)(1+b)(1+c) \geq 8 (1-a)(1-b)(1-c) . \]](http://latex.artofproblemsolving.com/0/b/e/0bedd9ed8362ac5202845f8a4d0d24519423e9b4.png)
. Prove that![\[
\sum_{\text{cyc}} \frac{x^3}{y^2 + z^2} \geq \frac{x + y + z}{2}
\]](http://latex.artofproblemsolving.com/9/0/3/903220c471bdd3028dda2fcb13874a4bcf752872.png)
without using the Rearrangement Inequality or Chebyshev's Inequality.
be an acute angled triangle.And altitudes 
and 
intersects at point 
.Let 
be a point on ray such that 
.Circumcircle of 
intersects line 
at 
and 
so prove that 
,![\[\frac{1}{a+\frac{1}{b}+1}+\frac{1}{b+\frac{1}{c}+1}+\frac{1}{c+\frac{1}{a}+1}\ge \frac{3}{\sqrt[3]{abc}+\frac{1}{\sqrt[3]{abc}}+1}. \]](http://latex.artofproblemsolving.com/4/3/1/431b0ed375e037ee3d19e48a2bb4099f12f87784.png)
Proposed by David Stoner
such that![\[ x f(x + xy) = x f(x) + f \left( x^2 \right) f(y) \quad \forall x,y \in \mathbb{R}.\]](http://latex.artofproblemsolving.com/b/0/f/b0f1a1d3b9de5d23f1b5a2e9be3b88d8bd575883.png)
be a perfect square then is it true that it must be of the form
is not divisible by 
for any positive integer 
.
, s.t :
formed by using the digits 
once each such that the number 
is divisible by 
for 
.
such that
be an acute triangle with circumcircle 
. Let 
be the midpoint of 
and let 
be the midpoint of 
. Let 
be the foot of the altitude from 
and let 
be the centroid of the triangle . Let 
be a circle through and that is tangent to the circle at a point 
. Prove that the points 
and 
are collinear.
be a non-cyclic quadrilateral. Let 
and 
be the circumcentre and the circumradius of the triangle 
. Define 
and 
in a similar way. Prove that![\[\frac{1}{O_1A_1^2-r_1^2}+\frac{1}{O_2A_2^2-r_2^2}+\frac{1}{O_3A_3^2-r_3^2}+\frac{1}{O_4A_4^2-r_4^2}=0.\]](http://latex.artofproblemsolving.com/f/f/5/ff575c3012e0b86c5aeeec32aae5268a4dad74d2.png)
; now, consider 
; do the similar thing for N. There are 
ways to choose some 
; in particular, summing over all possible k simplifies to 
; but since we also need to add set M and N, there are 
many ways as our final answer. 
This generating function describes the subsets, where the exponent of 
is the sum of the elements and the exponent of 
is the size. Therefore, we want the sum of the coefficients of 
for positive integers .
can be obtained by taking![\[
\frac{1}{p}\sum_{k=0}^{p-1}F(e^{\frac{ik\pi}{p}}x,y)
\]](http://latex.artofproblemsolving.com/6/3/7/63702db9b6e1eb30f1ee8432a61a855a3ffa6527.png)
and we want the sum of the terms with exponent 
when evaluated at 
. We write![\[
(1+xy)(1+x^2y)\dots (1+x^{2p}y) =
y^{2p}\left(-\frac1y-x\right)\left(-\frac1y-x^2\right)\left(-\frac1y-x^3\right)\dots \left(-\frac1y-x^{2p}\right)
\]](http://latex.artofproblemsolving.com/8/b/8/8b85cd51b7d0bf328ec08413b372f5987c01b367.png)
Let 
be a monic polynomial in 
with roots 
for 
. When 
is a 
root of unity, 
Then, we find that 
Plugging in , we calculate that![\begin{align*}
[y^p]\frac{1}{p}\sum_{k=0}^{p-1}F(e^{\frac{ik\pi}{p}},y) &= [y^p]\frac{y^{2p}}{p}P_{e^\frac{ik\pi}{p}}\left(-\frac1y\right)\\
&= [y^p]\frac{y^{2p}}{p}\left((p-1)\left(\frac{-1}{y^p}-1\right)^2+\left(1+\frac{1}{y}\right)^{2p}\right)\\
&= [y^p]\frac{1}{p}\left((p-1)(y^p+1)^2 + (y+1)^{2p}\right)\\
&= \boxed{\frac{1}{p}\left(2(p-1)+\binom{2p}{p}\right)}
\end{align*}](http://latex.artofproblemsolving.com/d/6/4/d640fd0e3948d6a87a9d1939c9796da2f2b398c7.png)
be the generating function![\[A(x,y) = (1+yx)(1+yx^2)\cdots(1+yx^{2p})\]](http://latex.artofproblemsolving.com/b/d/f/bdf5cfe2bc04baf7120b03bb18c52730d186d298.png)
We apply the roots of unity filter on to get![\[\frac{A(1,y)+A(w,y)+\cdots+A(w^{p-1},y)}{p} = \frac{(1+y)^{2p}+(p-1)(1+yw)\cdots(1+yw^{2p})}{p}\]](http://latex.artofproblemsolving.com/b/9/0/b903e0b56df1f816fba4596940a00ea9c79958e0.png)
We call this function on , 
. Note that![\[(1+w)(1+w^2)\cdots(1+w^{p}) = 2\]](http://latex.artofproblemsolving.com/6/8/f/68f575ac21f319726af7523c916ec5030805d087.png)
Then, we apply the roots of unity filter on to get
But, we need to subtract 
because it counts the empty set and the set with size 
. This gives us![\[\boxed{\frac{\binom{2p}{p}+2p-2}{p}}\]](http://latex.artofproblemsolving.com/a/a/a/aaa2ab1d061116b992fd28c87995fa96d6e0c1ae.png)
be the gen func representing sums of subsets and their number of elements. Note that the answer is equal to ![\[\frac{1}{p^2}\left(\sum_{k=1}^p \sum_{k=1}^p F\left(e^{2\pi ij/p},e^{2\pi i k/p}\right)\right)-2\]](http://latex.artofproblemsolving.com/f/9/0/f903b605f56e1e273b57b145db1c5487b9967e0c.png)
by roots of unity filter, with the 
coming from the empty set and 
being included in this count. We thus compute this!!!
, then the sequence 
contains each residue modulo 
twice. Thus 
contains each residue twice. herefore, ![\[\sum_{k=1}^{p}F\left(e^{2\pi ij/p},e^{2\pi i k/p}\right)=p\prod_{k=1}^p \left(1+e^{2\pi i k/p}\right)^2=4p\]](http://latex.artofproblemsolving.com/4/c/7/4c759021b9297fefe18507982a97525826566ddb.png)
As ![\[\prod_{k=1}^p \left(1+e^{2\pi i k/p}\right)^2=\prod_{k=1}^p \left(-1-e^{2\pi i k/p}\right)^2=P(-1)^2=4\]](http://latex.artofproblemsolving.com/c/9/5/c95e2e8afe5907de7c9b3662c0cbe1c60f8c0a5a.png)
in 
.
, then ![\[\sum_{k=1}^{p}F\left(1,e^{2\pi i k/p}\right)=p\sum_{k=1}^{p}F\left(1+e^{2\pi i k/p}\right)^{2p}\]](http://latex.artofproblemsolving.com/5/2/0/52024dcfda263149c0075c91ced7c0a2a0d2bcd8.png)
By roots of unity filter on 
, we get that the above sum is 
and subtraction is ![\[p\left(2+\binom{2p}{p}\right)+4p(p-1)=p\binom{2p}{p}+4p^2-2p\]](http://latex.artofproblemsolving.com/a/4/e/a4e02317bd4fced962dbea9b5b3827533939c211.png)
implying a final answer of ![\[\frac{p\binom{2p}{p}+4p^2-2p}{p^2}-2=\frac{\binom{2p}{p}-2}{p}+2.\]](http://latex.artofproblemsolving.com/9/a/e/9aeebc397d6079b6d99eb4bcd17e36a026494d9c.png)
, where the coefficient 
of 
represents the number of subsets 
where the sum of the elements of is 
, while 
. By considering how many numbers we extract from each individual residue class, it is not hard to find that
We will use a double roots of unity filter to add all coefficients where 
, then subtract to account for the cases when 
. Let 
. We want to evaluate 
. When 
, ![$f(\omega^r, \omega^s) = \left[\prod_{n = 0}^{p - 1} (1 + \omega^n) \right]^2 = 2^2 = 4$](http://latex.artofproblemsolving.com/5/6/a/56a8f587a16aeb65531a587c4bc5fdfe87932fc6.png)
. All cases belonging to the latter yield a total of 
. On the other hand, when 
, we have 
. Using the binomial theorem, only the terms when the exponent of is divisible by are left behind, and we obtain ![$p \left[\binom{2p}{p} + 2 \right]$](http://latex.artofproblemsolving.com/7/0/5/705721ab0d12b9a41156dd3b7ce25b987d396bdb.png)
. Our final answer is![$$\frac{4p(p - 1) + p \left[\binom{2p}{p} + 2 \right]}{p^2} - 2 = \frac{\binom{2p}{p} - 2}{p} + 2.$$](http://latex.artofproblemsolving.com/5/d/9/5d95834d490288f96883adc477d9da869f33e637.png)
in![\[(1 + xy)(1 + x^2y)\dots(1 + x^{2p}y)\text{.}\]](http://latex.artofproblemsolving.com/9/5/c/95ca0cd879ee7def26093ea4dcd1e8cd3fc61079.png)
First fix . Now let be a primitive -th root of unity, we want the coefficient of in![\[\frac{P(1) + P(\omega) + \dots + P(\omega^{p - 1})}{p} = \frac{(1 + y)^{2p} + (p - 1)(1 + y^p)^2}{p}\]](http://latex.artofproblemsolving.com/d/0/1/d010d9d006c116ec6ee71b5eb4b87d13c9183e61.png)
so the answer is![\[\frac1p\left(\binom{2p}{p} - 2\right) + 2\text{.}\]](http://latex.artofproblemsolving.com/e/d/5/ed5aff0e6db852986173ae9c8850c34ccb245c90.png)
Clearly, we want the sum of the coefficients of the terms with of degree divisible by and having degree 
Let 
Then by Roots of Unity Filter we have 
However, for 
clearly the set 
is a permutation of 
so 
Hence, our sum equals 
Now, we simply extract the coefficient of from here, and this is just 
be the 
-binomial coefficient and ![$\textstyle [n]_q=1+q+\dots+q^{n-1}=\frac{1-q^n}{1-q}$](http://latex.artofproblemsolving.com/f/1/0/f105d25482cfa1f59a3dcc2ea1f503175225de5a.png)
. Then it is well-known that![\[\sum_{\substack{S\subseteq\{1,2,\dots,2p\}\\|S|=p}}q^{\sum S}=q^{p(2p+1)}\binom{2p}{p}_q.\]](http://latex.artofproblemsolving.com/c/6/1/c61c578e66e3da00179d1b9ada52854bd5ca76e5.png)
be a primitive th root of unity. Then we have![\[\binom{2p}{p}_q=\frac{[2p]_q[2p-1]_q\dots[p+1]_q}{[p]_q[p-1]_q\dots[1]_q}=(1+q^p)\frac{[2p-1]_q\dots[p+1]_q}{[p-1]_q\dots[1]_q}.\]](http://latex.artofproblemsolving.com/e/a/a/eaa23fd616fea729c628c01118cc80df074b0d65.png)
As we let 
, then the product cancels out, so we have 
.
, since 
and all other powers are primitive th roots of unity.
![\[P(x,y)=\prod_{n=1}^{2p}(x+y^n).\]](http://latex.artofproblemsolving.com/b/d/e/bdee663a78305829162c0c6d124e719b7ae96de5.png)
Note that if a subset 
has 
elements that sum to 
, the set 
will show up in the expansion of 
as 
.
. By roots of unity filter it suffices to find the coefficient 
of 
in the expansion of 
. But note that 
is equal to 
if 
and is equal to 
otherwise. Thus ![\[Q(x)=\frac{(x+1)^{2p}+(p-1)(x^p+1)^2}p,\]](http://latex.artofproblemsolving.com/6/6/c/66caef73f88bd8ac0015fda7ff95527d52a4a372.png)
from which extracting yields ![\[c_p=\boxed{\frac{\binom{2p}p+2(p-1)}p},\]](http://latex.artofproblemsolving.com/3/9/1/391193b5a2f254265d086497c0fbce28d93362a1.png)
which is our answer. 
where counts the number of elements we dont use and counts the exponent. We want to be a multiple of , and to be . To extract the first condition, take ROUF with a primitive th root . We get 
. Its obvious by binomial expansion that the answer from here is 
and then subtract 2.
it follows that we are just looking for the exponent of 
and so it is 
.
for some 
where is some primitive -th root of unity.
Thus, to finish, we divide by and . This gives 
be an odd prime number. How many 
of 
are there, the sum of whose elements is divisible by 
.
different from 
denote 
.
form a group of 
)
at the polynomial
.
as a representant system for 
,
)
and 
define 
and similar for a subset 
.
or 
,
subsets 
such that both 
and 
are trivial, so call these subsets trival from now on too.
and 
otherwise.
goes through all possible residue classes, that also the sum of the elements of 
goes through all of them, so there is exactly one sum that is divisible by 
subsets of the desired order 
such subsets.
)
)!
,
will refer to the set having 
elements and sum of elements 
to find the answer.
and substract 2, since there are two terms for 
:
.
(
is not 
,
(every 
will be written twice as 
)
choices for 
we get 
.
,
.
,
.
.
if 
and 
if 
.
,
.
![\[ \prod_{k=1}^{2p} (x - w^k) = (x^p - 1)^2 = x^{2p} - 2x^p + 1. \]](http://latex.artofproblemsolving.com/5/1/4/514ceb2104b6145851a3884b2b6807282dcc339f.png)
![\[ t(w) = \sum_{1 \leq j_1 < j_2 < \ldots < j_p \leq 2p} w^{j_1}w^{j_2} \ldots w^{j_p}. \]](http://latex.artofproblemsolving.com/4/9/1/4916f7bd648286d8c29e84876f25b422eb5618a8.png)
.
,
represents the number of sub-sets 
of 
such that 
,![\[ (a_0 - 2) + a_1w + \ldots + a_{p-1}w^{p-1} = 0. \]](http://latex.artofproblemsolving.com/4/7/7/477e6bb023ed7cfb7114a984eb26efad7335d973.png)
![$\mathbb{Q}[X]$](http://latex.artofproblemsolving.com/f/3/d/f3dc4b61f66a97c235268da5643f5bebbc69c9bd.png)
is 
,![\[ a_0 - 2 = a_1 = a_2 = \ldots = a_{p-1}. \]](http://latex.artofproblemsolving.com/1/6/c/16c0afd9a753f9e9b4fcf134daca0f2aa2659877.png)
,![\[ a_0 = \frac 1p \left\{\binom {2p}{p} - 2 \right \} + 2. \]](http://latex.artofproblemsolving.com/0/a/6/0a61ad8cfe65a9a2e50d89a566bbbf1b8b9ade1a.png)
.
.
,
Here, we need to think in two dimensions - that is, we need to have a generating function such that it gives us information on both how many elements participate in the sum and how much their sum is. To do this, we consider the two-variable function
and we are tasked with finding the sum of the coefficients in front of 
for any natural 
)
)
should have 
.
We remember that the roots of unity filter provides us with a function for which 
and 
otherwise, and that function is
where 
is the 
t
)
where 
and 
.
which we obtain from the identity
Here comes another roots of unity filter which, upon applying on the sum, solves the second case and we get that
The above means that only terms where 
survive:
or, for the sake of our solution (so subtracting 2 at the end), we obtain that the answer is
We wish to find ![$$\sum_{k \ge 0} [x^py^{pk}]P(x,y).$$](http://latex.artofproblemsolving.com/0/7/5/075992ef68147284cd8e772af4504b693333d3d4.png)
By the roots of unity filter, we can filter out all terms of 
except for the ones with 
Hence, the answer is![\begin{align*}
[x^p]\frac{(1+x)^{2p}+(p-1)(x^p+1)^2}{p} &= \frac{\tbinom{2p}{p}+2p-2}{p} \\
&= \boxed{\frac{\tbinom{2p}{p}-2}{p}+2}.
\end{align*}](http://latex.artofproblemsolving.com/5/8/e/58e325b35b645496ba0ee7735263fc0cf2a6a438.png)
