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.
less than 2024 for which 
and 
are relatively prime for all integers 
.
so that the sum of its edges' lengths is minumum.
+1 w
such that, for all 
,
Thank you.
such that any set of ponts in a Cartesian plan, all of them with integer coordinates, contains two poitns such that the square of its mutual distance is a multiple of 
.
be non-negative real numbers. Prove that![\[\sum_{i=1}^n \frac{\displaystyle a_i^2 \left( \sum_{j=1}^n a_j - a_i \right)^2}{\displaystyle \sum_{j=1}^n a_j^2 - a_i^2} \geq \left(\sum_{i=1}^n a_i\right)^2 - \sum_{i=1}^n a_i^2.\]](http://latex.artofproblemsolving.com/b/1/6/b16f7db4a2f1bb30df4f6534bc6fa18b0fd6b01b.png)
Assume all denominators are non-zero.
such that for any 
real numbers 
satisfying![\[\sum_{i=1}^{2024} a_i = 0,\quad\sum_{i=1}^{2024} a_i^2 = 1,\]](http://latex.artofproblemsolving.com/a/7/5/a7599a2e36d7adf5c0f06bf84b8a5d3af8272584.png)
there exists a non-empty subset 
of 
for which![\[\sum_{i\in I} a_i \leq \lambda \cdot \min\{|I|, 2024 - |I|\}.\]](http://latex.artofproblemsolving.com/2/9/b/29b27625abeb620645b885ad0dca696ac6ad880e.png)
Proposed by Tianqin Li, High School Affiliated to Renmin University of China
be the incenter of 
. The incircle tangents to 
, 
at 
, 
, respectively. Let 
intersect 
at 
. 
and 
intersect again at 
. Let 
be the midpoint of the arc of 
. 
intersects again at 
. Let 
be the orthocenter of 
.
and 
lies on .
+1 w
such that for every pair of distinct positive integers 
, 
is a divisor of 
.
is divisible by for every positive integer . that is not a polynomial in (i.e., there does not exist a polynomial ![\(P(X) \in \mathbb{R}[X]\)](http://latex.artofproblemsolving.com/9/8/4/984bd826ad67d4445e27fd211182f8e3d2a13d5f.png)
such that 
for all 
) and satisfies the given condition?
be a real number.[list]
;
. [/list]
, let be a moving point inside the triangle such that 
. 
, 
intersect 
at , respectively, where 
is the circumcenter of 
. The circle with diameter 
meet the circumcircle of 
at another point .
.
,then prove the following![\[
a\mid c, b\mid c \implies lcm(a,b)\mid c.
\]](http://latex.artofproblemsolving.com/2/7/a/27a4f2847b3aa9791d71736c0ddd61cfb67e579d.png)
And also prove that![\[
c\mid a,c\mid b \implies c\mid gcd(a,b)
\]](http://latex.artofproblemsolving.com/2/6/4/2644ac4b07062dfca3a456011ecacaf96fbd2059.png)
And by the help of God I finish this question.
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 
, and 
.
be a 
-element subset of 
. Define 
, and 
.
, define 
as the set obtained by adding 
to each element of 
.
be the number of elements in , and set 
.
denotes the sum of elements in the set 
, then we have![\[
S(U' + k) - S(U') = k \cdot n(U') = k m.
\]](http://latex.artofproblemsolving.com/4/0/7/407a6ff056309ce2b3c6f6eea4ae8e7d0eae5c9f.png)
, the set 
contains all residues modulo .
.
, the value 
is divisible by .
, there is a unique such that this condition is satisfied.
with 
, except when 
or 
, there are 
such sets. shifts, exactly one satisfies the condition, giving![\[
\frac{\binom{2p}{p} - 2}{p}
\]](http://latex.artofproblemsolving.com/b/5/6/b56003d3c72654d8e4604d0be7f799139387067f.png)
sets. and satisfy the condition, so we add 2.![\[
\boxed{ \frac{\binom{2p}{p} - 2}{p} + 2 }.
\]](http://latex.artofproblemsolving.com/5/f/7/5f75b75d075639c65caec3d516ec9eaf784b5c16.png)
non-negative real numbers. Prove that![\[\frac{abc}{(a+b+c)^3}+\frac{bcd}{(b+c+d)^3}+\frac{cda}{(c+d+a)^3}+\frac{dab}{(d+a+b)^3} \leqslant \frac{(a+b+c+d)^2}{27(a^2+b^2+c^2+d^2)}.\]](http://latex.artofproblemsolving.com/a/4/8/a484de0a1592d96b931cb50838bc0ef2c8dfb038.png)
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
.
and 
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 
of 
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)
of![\[ P(x,y)=(1+y)^2(1+xy)^2\cdots(1+x^{p-1}y)^2. \]](http://latex.artofproblemsolving.com/c/c/f/ccfdba223a71aa22f1517114750804475d2c0473.png)
Letting ![\[ \frac{(1+y)^{2p}+(p-1)((1+y)(1+\omega y)\cdots(1+\omega^{p-1} y))^2}{p}=\frac{(1+y)^{2p}+(p-1)(1+y^p)^2}{p} \]](http://latex.artofproblemsolving.com/3/b/3/3b3bcd74052093355ac85a6c50872a8b896e26cc.png)
which is easily found to be 