[/quote]
,
?
be a prime number and 
an integer polynomial of degree 
such that 
and 
is congruent to 
or 
modulo 
.
.
such that 
is an integer for all 
,
are all the positive divisors of 
be three positive reals such that 
.![\[ \frac { x^5-x^2 }{x^5+y^2+z^2} + \frac {y^5-y^2}{x^2+y^5+z^2} + \frac {z^5-z^2}{x^2+y^2+z^5} \geq 0 . \]](http://latex.artofproblemsolving.com/a/1/4/a14adf0f1e35df57c734c7df701d5a67da22dc3c.png)
where 
are lengths of parallel sides and 
are other two sides.
be a cyclic quadrilateral. Let 
,
,
be the feet of the perpendiculars from 
to the lines 
,
,
,
if and only if the bisectors of 
and 
are concurrent with 
.
.
be the feet of the altitudes from 
to 
to 
and 
as the reflections of 
be the circumcircle of 
.
with 
with 
is the circumcenter of 
can be inscribed within a circle.
be a triangle. A circle passing through 
intersect at 
,
and 
intersect at 
.
if and only if 
.
and 
be points on segment 
denote the circle passing through 
denote the circle passing through 
.
)
.
spheres centered at 
and 
and 
,
points 
outside of 
as the number of sets 
such that the midpoint of 
lies entirely inside of 
and 
.
.
has circumcenter 
.
and 
intersect at 
,
and 
intersect at 
and 
and 
intersect at 
.
are similar(with vertices in that order), than 
be the feet of the altitudes from 
respectively. Let 
be the projections of 
.
.
Y by Adventure10, mathematicsy, megarnie, TFIRSTMGMEDALIST, Mango247, NicoN9, cubres
Let 
be an odd integer greater than 1 and let 
be integers. For each permutation 
of 
, define 
. Prove that there exist permutations 
of such that 
is a divisor of 
.
be an odd integer greater than 1 and let 
be integers. For each permutation 
of 
, define 
. Prove that there exist permutations 
of such that 
is a divisor of 
.Attachments:
This post has been edited 2 times. Last edited by orl, Oct 25, 2004, 12:13 AM
of 
and the corresponding 
modulo 
,![\[ \sum_{a}S(a)\equiv 0+1+\ldots+n!-1 \equiv \frac{(n!-1)n!}2\mod {n!} \]](http://latex.artofproblemsolving.com/4/f/f/4ff723c518de8b12ff039aba57e5b81a0840f3b7.png)
![\[ \sum_{a}S(a)=\sum_{i=1}^nc_i( (n-1)!\cdot (1+2+\ldots+n)) = \sum_{i=1}^nc_i( n! \cdot \frac{n+1}2) \]](http://latex.artofproblemsolving.com/f/5/f/f5fcfd37fcbc20bed31ca16eafaf262703b2c5bb.png)
,
,![\[ \frac{(n!-1)n!}2\equiv 0\mod{n!} \]](http://latex.artofproblemsolving.com/b/5/a/b5ab025f0f806cb0c74136f4f656121f963be534.png)
of 
,
.
with 
,
.
.
.
also satisfies 
.
and 
denote the 
We shall take the indices modulo 
meaning that 
Also, let 
denote the 
t
Suppose the problem statement isn't true. Then,![\[S(\mathcal{P}_x) \equiv S(\mathcal{P}_y) \pmod{n!} \iff x \equiv y \pmod{n!},\]](http://latex.artofproblemsolving.com/9/e/6/9e6e7a00eb44cdf8f1b4d801c8e333e9640d9cf3.png)
is bijective modulo 
is equivalent to 
modulo ![\[\displaystyle \sum_{i=1}^{n!} S(\mathcal{P}_i) \equiv \displaystyle \sum_{i=1}^{n!} i \equiv \dfrac{n!(n!+1)}{2} \pmod{n!}.\]](http://latex.artofproblemsolving.com/6/e/9/6e9398551f5b17010ed019a26cc60505ab1d4750.png)
contradiction. 
are all distinct residues 
.
in two different ways. First, summing over 
we have 
,
.
a different way, observe that there are 
times where 
has coefficient 
,
.
'
.
be set of all permutation of 
.
which satisfy 
.
is 
i
.
in 
.
is 
.
which is absurd.Therefore 
.
be the set of all permutations of 
Assume for the sake of contradiction that there doesn't exist such 
Consider the multiset 
because of our assumption and 
, when we take 
Let 
be the permutation such that![\[S(X)\equiv \left(\frac{n+1}{2}\right)\left(\sum_{i=1}^{n}c_i\right)\pmod{n!}\]](http://latex.artofproblemsolving.com/2/e/f/2ef621f4aa0d6445f06acf3e3b977aa3e407fc7b.png)
Define 
note that 
and that 
is a valid permutation.![\[S(\overline{X})=\sum_{i=1}^n c_i(n+1-x_i)=(n+1)\sum_{i=1}^n c_i-S(X)\equiv (n+1)\sum_{i=1}^n c_i- \left(\frac{n+1}{2}\right)\left(\sum_{i=1}^{n}c_i\right)\pmod{n!}\equiv S(X)\pmod{n!}\]](http://latex.artofproblemsolving.com/2/5/f/25fbce40a747c8aaacbd0080aedae840d7e27694.png)
Which is a contradiction to our assumption. And we are done. 
are different for all 
.
uniformly at random. By linearity of expectation, we have![\[\mathbb{E} S(\sigma)=c_i\frac{n+1}{2},\]](http://latex.artofproblemsolving.com/5/0/3/503e38e6afcd82d470d19dcd4179f30f1edaf248.png)
so![\[\sum_{\sigma\in S_n}S(\sigma)=\frac{(n+1)!}{2}\sum_{i=1}^n c_i\equiv 0\pmod{n!}\]](http://latex.artofproblemsolving.com/6/f/f/6ffe823149a8735e5213facfc85465a30ce897cf.png)
since 
.![\[\sum_{\sigma\in S_n}S(\sigma)\equiv\sum_{k=0}^{n!-1}k\equiv\frac{n!(n!-1)}{2}\pmod{n!},\]](http://latex.artofproblemsolving.com/d/5/5/d552c6c1b6b0fcb81a8b39b43ba5ede918c6de77.png)
which isn't divisible by 
is odd (this is why we need 
)
'
.![\[ \sum_{\pi \in S_n} S(\pi) \equiv 0+\cdots+(n!-1) = \frac{(n!-1)(n!)}{2} \not \equiv 0 \pmod{n!} \]](http://latex.artofproblemsolving.com/1/0/6/106185fe7db2f891068f116c5bca36ea20eeee81.png)
since 
as vectors in 
.![\[ ((n-1)!\cdot (1+\cdots+n))(1,\ldots,1) = \frac{n!(n+1)}{2}(1,\ldots,1).\]](http://latex.artofproblemsolving.com/1/b/6/1b6c1ac166b148f094948073c27127026d738d48.png)
Then
since 
takes distinct values as 
ranges over all permutations of ![\([n]\)](http://latex.artofproblemsolving.com/e/4/4/e44a40997d314324703bbb0aafb373c8f1e532e4.png)
.
But that would mean![\[\frac{n!}{2} \equiv 0 \pmod{n!}\]](http://latex.artofproblemsolving.com/c/c/2/cc23f893acd842f4d6a31a6f59a1ffd6fcfd856b.png)
which is a contradiction.
Counting 
fixing 
Which is a contradiction 
by looking at the amount of times 
,
t![\[\frac{n(n+1)}{2}\cdot(n-1)!\cdot\sum_{i=1}^n c_i = \frac{n+1}{2}\cdot n!\cdot \sum_{i=1}^n c_i\]](http://latex.artofproblemsolving.com/2/0/e/20e1fe46a503469d209dc4017d1355195d8dd9b4.png)
and 
modulo 
.
,
![\begin{align*}
\sum_k S(k) &= \sum^n_{j=1} c_j \times (n-1)! \times (1+2+3+\cdots+n)\\
&= \sum_{j=1}^n c_j\left[(n!)\left(\frac{n+1}{2}\right)\right].
\end{align*}](http://latex.artofproblemsolving.com/8/9/5/89541cb0a69b56aeada5a657c4ab5ee6921a03ef.png)
So, 
Thus we can deduce that
which is a contradiction since 
,
is the residues from 
.![\[\sum_{p\in P} S(p) \equiv \frac{(n!-1)(n!)}{2} \not\equiv 0 \pmod{n!}\]](http://latex.artofproblemsolving.com/5/f/8/5f8630757a57eb1b6857e1024fef34739d3aa2f6.png)
however,![\[\sum_{p\in P} S(p) = n!\cdot \frac{1+2+\cdots n}{n}\cdot \sum c_i = n!\cdot \frac{n+1}{2}\sum c_i \equiv 0 \pmod{n!}\]](http://latex.artofproblemsolving.com/3/c/1/3c1bb03471a306e61122162f98dc27d7d8c14069.png)
a contradiction, so we are done. 
However it is not hard to show that this sum is 
.
,
form a complete residue system of 
but on the other hand we could also evaluate 
as 
is even. Thus since 
,
which is absurd as 
.
.
However as 
which is not divisible by 
.
.
but since 
,
![$\mathcal{S} = \sum_{a \in [n]} S(a)$](http://latex.artofproblemsolving.com/e/2/1/e2164ce79690811e2c13b9bd09463ffc711daa47.png)
.
as ![$$\sum_{i = 1}^n\sum_{a \in [n]} \sum c_ia_i$$](http://latex.artofproblemsolving.com/7/c/5/7c53931ef2622db9ea6ecb931c9eb9487f097562.png)
contradiction. 
![\[\sum_{a \colon [n] \rightarrow [n]} S(a) = \sum_{i = 1}^n ((n - 1)!(1 + 2 + \dots + n)c_i) = \frac{n + 1}{2} \cdot n! \cdot (c_1 + c_2 + \dots + c_n),\]](http://latex.artofproblemsolving.com/4/5/5/4556465dfcc8ca3f10f842b6201c92c70083912b.png)
which is divisible by ![\[\sum_{a \colon [n] \rightarrow [n]} S(a) \equiv 0 + 1 + \dots + (n! - 1) = \frac{n!(n! - 1)}{2} \equiv \frac{n!}{2} \pmod{n!},\]](http://latex.artofproblemsolving.com/0/d/1/0d18f416fd0e947314bcceeca64bda05dc610134.png)
a contradiction. 
,
where the sum is over all permutations 
,
has a different residue mod 
is 
However, we can also count this as 
However, note that since 
is even, 
However, 
a contradiction. QED
such that 
This means that 
must have different residues modulo 
Since there are 
If we let 
it then follows by summing over all permutations that
where all of the congruences are taken modulo 
.
but this is also equal to 
mod 
is odd, done.
That means 
,
exist for which:![\[
S(a) \equiv S(b) \mod n!
\]](http://latex.artofproblemsolving.com/2/4/e/24e1e059ee6b893f608d7ea8ad941b798fb52bee.png)
Thus, all ![\[
\sum S(n)_a \equiv 0 + 1 + 2 + \dots + (n! - 1) \equiv \frac{(n! - 1)n!}{2} \mod n!
\]](http://latex.artofproblemsolving.com/9/d/b/9db41bc772a245bba3fe22378c761ab3c6661d70.png)
Also,![\[
\sum S(n)_a \equiv \sum_{i=1}^{n} c_i(1 + 2 + 3 + \dots + n)(n-1)! \equiv \sum_{i=1}^{n} c_i \frac{n!(n+1)}{2} \equiv 0 \mod n!
\]](http://latex.artofproblemsolving.com/4/3/a/43a0d1f593be21da04e6b27c515076c09114e7b9.png)
as ![\[
\frac{n!}{2} \equiv 0 \mod n!
\]](http://latex.artofproblemsolving.com/f/7/f/f7f8ce1695551856aeb9ea9b6246e0e2ebb314e3.png)
which is a contradiction.
be permutations. Then consider ![\[
S(a_1)+\dots S(a_{n!}) = \sum_{i=0}^n c_i(1+\dots+n)(n-1)!=\frac{1}{2}(n+1)!\sum c_i
\]](http://latex.artofproblemsolving.com/8/9/9/899b3b3aab75a75e32e1b4cfce863799ea4025d8.png)
On the other hand, each of 
,![\[
S(a_1)+\dots S(a_{n!}) \equiv \frac{1}{2} n!(n!+1)\pmod {n!}.
\]](http://latex.artofproblemsolving.com/7/c/3/7c33346997ce51c5f667e1195fbb7493b50494b3.png)
Now we have![\[
\frac{1}{2}(n+1)!\sum c_i
\equiv \frac{1}{2} n!(n!+1)\pmod{n!}.
\]](http://latex.artofproblemsolving.com/b/5/6/b568b856e292f75c8271fecb370d3ede2be79064.png)
which is a contradiction since LHS is zero but RHS is nonzero.
