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.
such that
is an integer.
be a triangle with 
, and let 
be the foot of the altitude from 
. Let 
be a point in the interior of the segment 
. Let 
be the point on the segment 
such that 
. Similarly, let 
be the point on the segment 
such that 
. Let 
be the point of intersection of 
and 
.
.
be a point on segment 
. Let 
be a fixed circle passing through , and let 
be a variable point on . Let 
be the intersection of the tangent to the circumcircle of 
at 
and the tangent to the circumcircle of 
at 
. Show that as varies, lies on a fixed line.
, 
, with 
, 
. Prove that there exists 
such that for every 
![\[
f_n(x) = \frac{x}{1 + nx}, \quad \text{if and only if } f(x) = \frac{x}{1 + x}, \quad \forall x \geq 0.
\]](http://latex.artofproblemsolving.com/0/f/c/0fc36d9264eb7e103128c489aeae521a859c1fd4.png)
(For and , the notation 
represents 
. ), let 
be the sum of the remainders when is divided by 
. For example, 
. Find all positive integers such that 
.
be the set of all positive integers. Find all functions 
such that 
and 
have the same number of 
's in their binary representations, for any 
.
is called beautiful if, for every integer 
, the base-
representation of contains the consecutive digits 
, 
, , 
(in this order, from left to right). Determine whether the set of all beautiful integers is finite.
that are relatively prime be called intertwined if among any two divisors of greater than , there exists a divisor of 
and among any two divisors of greater than , there exists a divisor of . For example, pair 
is intertwined.
for which there exists an intertwined pair such that the product 
is equal to the product of the first prime numbers. such that the product is the product of 
distinct prime numbers. such that the number of divisors of is greater than .
and 
have a common tangent that meets in 
and in 
. The two circles intersect at and 
where is closer to 
than . Line 
meets circle a second time in 
. Prove that 
bisects angle 
.
be real numbers satisfying 
and 
Prove that 
Let be real numbers satisfying 
and 
Prove that 
be a positive integer. Call a rearrangement 
of nice if for every 
, we have that 
is not divisible by . is odd, prove that there is no nice arrangement of . is even, find a nice arrangement of .
are non-negative real numbers and 
Prove that
be real numbers satisfying![\[
x_1 + x_2 + \cdots + x_6 = 6,
\]](http://latex.artofproblemsolving.com/6/2/2/622a329112ce9613a5c389b4c9078cd43c1c3f05.png)
![\[
x_1^2 + x_2^2 + \cdots + x_6^2 = 18.
\]](http://latex.artofproblemsolving.com/8/f/a/8fa3f74ba7c3587576116a7bdbb4e9f88d389133.png)
Find the maximum possible value of the product![\[
x_1 x_2 x_3 x_4 x_5 x_6.
\]](http://latex.artofproblemsolving.com/3/b/4/3b48315e2775b4ac3913d7c9b02dbc81daed8d15.png)
.
different from 
and 
denote 
,
.
form a group of 
sets where all the residues appear. (The set 
)
at the polynomial
. and 
as a representant system for 
, since not more is necessary (so all identities concerning or must be seen 
).
and 
define 
and similar for a subset 
. trivial iff 
or 
, similar for again.
subsets 
such that both 
and 
are trivial, so call these subsets trival from now on too. a 'translation': is nontrivial define 
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 
. sets each, all sets of the same class having same number of elements.
subsets of the desired order and of them are trivial, we get that there are 
such subsets.
)
)!
, the -th factor refering to whether is present in the set or not.
will refer to the set having 
elements and sum of elements , so we need to compute the sum of coefficients of 
of 
to find the answer.
and substract 2, since there are two terms for 
:
. we use Multisection formula that says us that it equals
(
is th root of unity).
is not , 
(every 
will be written twice as 
). This equals 
(
is the polynomial with roots ). Since there are 
choices for , choices for 
we get 
.
, 
. To evaluate 
, note that it equals times the coefficients of 
in the polynomial 
by the same multisection formula, so it equals 
.
.
is a th root of unity then 
if 
and 
if 
. By using this result, we can prove the Multisection Formula (which holds also for polynomials of more variables) :
, then 
. Particularly
be the p-th root of unity.![\[ \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)
. Besides, if we write 
, then 
represents the number of sub-sets 
of 
such that 
, and we can write :![\[ (a_0 - 2) + a_1w + \ldots + a_{p-1}w^{p-1} = 0. \]](http://latex.artofproblemsolving.com/4/7/7/477e6bb023ed7cfb7114a984eb26efad7335d973.png)
on ![$\mathbb{Q}[X]$](http://latex.artofproblemsolving.com/f/3/d/f3dc4b61f66a97c235268da5643f5bebbc69c9bd.png)
is 
, it follows that :![\[ a_0 - 2 = a_1 = a_2 = \ldots = a_{p-1}. \]](http://latex.artofproblemsolving.com/1/6/c/16c0afd9a753f9e9b4fcf134daca0f2aa2659877.png)
, we conclude immediately that :![\[ a_0 = \frac 1p \left\{\binom {2p}{p} - 2 \right \} + 2. \]](http://latex.artofproblemsolving.com/0/a/6/0a61ad8cfe65a9a2e50d89a566bbbf1b8b9ade1a.png)
the equality hold for 
or 
or any
are there, the sum of whose elements is divisible by 
.
.
,
;
;
ways to choose some 
;
;
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 
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 
.![\[
(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 
.
is a 
root of unity, 
Then, we find that 
Plugging in ![\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 ![\[\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 
.![\[(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 
But, we need to subtract 
.![\[\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!!!
,
contains each residue modulo 
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 
.
,![\[\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 
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)
,
of 
represents the number of subsets 
where the sum of the elements of 
is 
,
.
We will use a double roots of unity filter to add all coefficients 
,
.
.
.
,![$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)
.
.
,
.
is divisible by ![$p \left[\binom{2p}{p} + 2 \right]$](http://latex.artofproblemsolving.com/7/0/5/705721ab0d12b9a41156dd3b7ce25b987d396bdb.png)
.![$$\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 ![\[\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 
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 
be the 
-![$\textstyle [n]_q=1+q+\dots+q^{n-1}=\frac{1-q^n}{1-q}$](http://latex.artofproblemsolving.com/f/1/0/f105d25482cfa1f59a3dcc2ea1f503175225de5a.png)
.![\[\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)
![\[\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 
,
.
,
and all other powers are primitive 
![\[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 
,
will show up in the expansion of 
.
.
of 
.
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 ![\[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 
.
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)
and then subtract 2.
it follows that we are just looking for the exponent of 
and so it is 
.
for some 
where 
Thus, to finish, we divide by 
