IMO ShortList 2001, combinatorics problem 2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

orl

3647 posts

orl

#1 h Sep 30, 2004, 5:23 PM • 7 Y

Y by Adventure10, mathematicsy, megarnie, TFIRSTMGMEDALIST, Mango247, NicoN9, cubres

Let $n$ be an odd integer greater than 1 and let $c_1, c_2, \ldots, c_n$ be integers. For each permutation $a = (a_1, a_2, \ldots, a_n)$ of $\{1,2,\ldots,n\}$ , define $S(a) = \sum_{i=1}^n c_i a_i$ . Prove that there exist permutations $a \neq b$ of $\{1,2,\ldots,n\}$ such that $n!$ is a divisor of $S(a)-S(b)$ .

Attachments:

This post has been edited 2 times. Last edited by orl, Oct 25, 2004, 12:13 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

orl

3647 posts

orl

#2 h Sep 30, 2004, 5:24 PM • 3 Y

Y by Adventure10, Mango247, cubres

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Yimin Ge

253 posts

Yimin Ge

#3 h Jun 26, 2006, 8:19 PM • 21 Y

Y by iarnab_kundu, Akababa, B.J.W.T, Polynom_Efendi, XbenX, OlympusHero, Math_Is_Fun_101, Quidditch, TFIRSTMGMEDALIST, Mehrshad, Aopamy, Crazy4Hitman, Adventure10, Mango247, sabkx, cubres, and 5 other users

Ah...at last I solved an IMO-Combinatorics problem.

We consider all $n!$ Permutations $a$ of ${1,\ldots,n}$ and the corresponding $S(a)$ modulo $n!$ . If two of them are congruent $\mod{ n!}$ , then we are done.
So let's suppose that all $n!$ permutations are in different residues. Sum up over $S(a)$ and we have
$\sum_{a}S(a)\equiv 0+1+\ldots+n!-1 \equiv \frac{(n!-1)n!}2\mod {n!}$
But on the other hand, we have
$\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)$
Since $n$ is odd, we have $2\mid n+1$ , thus $\sum_a S(a)\equiv 0 \mod{n!}$ ,
so we have
$\frac{(n!-1)n!}2\equiv 0\mod{n!}$
which is a contradiction since $n!$ is even.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Zhero

2043 posts

Zhero

#4 h Jul 17, 2010, 7:27 PM • 4 Y

Y by Mehrshad, Adventure10, Mango247, cubres

Suppose for the sake of contradiction that for all permutations $a$ and $b$ of $\{1,2, \ldots, n\}$ , we have that $S(a) \neq S(b) \pmod{n!}$ . There are $n!$ permutations of $\{1,2, \ldots, n\}$ and $n!$ residue classes modulo $n!$ , so for every integer $m$ with $0 \leq m < n!$ , there is a unique permutation $a$ of $\{1,2,\ldots,n\}$ such that $S(a) \equiv m \pmod{n!}$ .

Let $k = \frac{(n+1)(c_1 + c_2 + \cdots + c_n)}{2}$ . We can find some permutation $a = (a_1, a_2, \ldots, a_n)$ such that $S(a) \equiv c_1 a_1 + c_2 a_2 + \cdots + c_n a_n \equiv k \pmod{n!}$ . But the permutation $a' = (n+1-a_1, n+1-a_2, \ldots, n+1-a_n)$ also satisfies $S(a) \equiv (n+1)(c_1 + c_2 + \cdots + c_n) - (c_1 a_1 + c_2 a_2 + \cdots + c_n a_n) \equiv 2k - k \equiv k \pmod{n!}$ .
Hence, $a'$ and $a$ must be the same permutation, which is absurd.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AnonymousBunny

339 posts

AnonymousBunny

#5 h Jul 20, 2014, 2:34 PM • 3 Y

Y by Adventure10, Mango247, cubres

Let $\mathcal{P}_1, \mathcal{P}_2, \cdots , \mathcal{P}_{n!}$ denote the $n!$ permutations of $(1, 2, \cdots , n).$ We shall take the indices modulo $n!,$ meaning that $\mathcal{P}_x = \mathcal{P}_{x \pmod{n!}}.$ Also, let $\mathcal{D}_{n,x}$ denote the $x$ th digit of $\mathcal{P}_n.$ 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!},$
implying that $\mathcal{P}_i$ is bijective modulo $n!,$ or in other words, $(S(\mathcal{P}_1), S(\mathcal{P}_2), \cdots , S(\mathcal{P}_{n!}))$ is equivalent to $(1, 2, \cdots , n!)$ modulo $n!$ in some order. We then have
$\displaystyle \sum_{i=1}^{n!} S(\mathcal{P}_i) \equiv \displaystyle \sum_{i=1}^{n!} i \equiv \dfrac{n!(n!+1)}{2} \pmod{n!}.$
But we also have
$\begin{align*} \displaystyle \sum_{i=1}^{n} S(\mathcal{P}_i) & \equiv \displaystyle \sum_{i=1}^{n} \left( \displaystyle \sum_{j=1}^{n} c_j \mathcal{D}_{i,j} \right) \\ & \equiv (n-1)! \displaystyle \sum_{j=1}^{n} c_j \left( \displaystyle \sum_{k=1}^{n} \mathcal{D}_{j,k} \right) \\ & \equiv \dfrac{n(n+1)}{2} (n-1)! \cdot \left( \displaystyle \sum_{j=1}^{n} c_i \right) \\ & \equiv 0 \pmod{n!},\end{align*}$
implying $\dfrac{n!(n!+1)}{2} \equiv 0 \pmod{n!} \implies 2 \mid n!+1,$ contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AMN300

563 posts

AMN300

#6 h Dec 26, 2015, 5:54 AM • 3 Y

Y by Adventure10, Mango247, cubres

Wow, this problem is really nice. Unfortunately my solution seems to be pretty similar compared to previous ones in the thread

FTSOC $S(1), S(2), \cdots, S(n!)$ are all distinct residues $\pmod{n!}$ . Let's consider $S=\sum_{j=1}^{n!} \sum_{i=1}^{n} c_ia_i$ in two different ways. First, summing over $S(1), \cdots, S(n!)$ we have $S=1!+2!+\cdots+(n!-1) \equiv \frac{n!(n!-1)}{2} \pmod{n!}$ , which isn't $0 \pmod{n!}$ . Considering $S$ a different way, observe that there are $(n-1)!$ times where $c_i$ has coefficient $1, 2, \cdots, n$ , $1 \le i \le n$ . Summing up over the $c$ 's, we have $S=(n-1)! \frac{n(n+1)}{2} \sum_{i=1}^{n} c_i \equiv 0 \pmod{n!}$ . This is our contradiction and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Takeya.O

769 posts

Takeya.O

#7 h Aug 23, 2016, 12:06 PM • 4 Y

Y by mathematiculperson, Adventure10, Mango247, cubres

I apologize to everyone for my solution being similar to above solution.

Let $S_{n}$ be set of all permutation of $(1,\dots ,n)$ .We suppose that there is no $a\neq b$ which satisfy $S(a)\equiv S(b)\mod{n!}$ .Then $\{S(a)\}_{a\in S_{n}}{}$ is $\{0,1,\dots ,n!-1\}$ in $\mod{n!}$ .We calculate $\sum_{a\in S_{n}}{}S(a)$ in $2$ ways.

First
$\sum_{a\in S_{n}}{}S(a)\equiv \sum_{k=0}^{n!-1}k\equiv \frac{(n!-1)(n!)}{2}\mod{n!}$ .

Second
The number of permutations which $a_i=k(1\le i,k\le n)$ is $(n-1)!$ .Thus
$\sum_{a\in S_{n}}{}S(a)\equiv \sum_{i=1}^{n}c_{i}\cdot (n-1)!\cdot (1+\dots +n)$
$\equiv n!\frac{n+1}{2}\sum_{i=1}^{n}c_{i}\equiv 0\mod{n!}$ .

From First and Second,
$\frac{(n!-1)(n!)}{2}\equiv 0\mod{n!}\Leftrightarrow \frac{n!}{2}\equiv 0\mod{n!}$ which is absurd.Therefore ∃ $a\neq b$ s.t. $n! | S(a)-S(b)$ . $\blacksquare$

This post has been edited 9 times. Last edited by Takeya.O, Aug 23, 2016, 1:09 PM
Reason: Latex miss

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ayan.nmath

643 posts

ayan.nmath

#8 h Jun 24, 2018, 3:24 PM • 2 Y

Y by Adventure10, cubres

ISL 2001 C2 wrote:

Let $n$ be an odd integer greater than 1 and let $c_1, c_2, \ldots, c_n$ be integers. For each permutation $a = (a_1, a_2, \ldots, a_n)$ of $\{1,2,\ldots,n\}$ , define $S(a) = \sum_{i=1}^n c_i a_i$ . Prove that there exist permutations $a \neq b$ of $\{1,2,\ldots,n\}$ such that $n!$ is a divisor of $S(a)-S(b)$ .

Solution.

Let $\mathcal{P}$ be the set of all permutations of $\{1,2,3,\ldots,n\}.$ Assume for the sake of contradiction that there doesn't exist such $a\ne b.$ Consider the multiset $T=\{S(\pi)\mid \pi\in\mathcal P\},$ because of our assumption and $|T|=n!$ , when we take $T$ modulo $n!$ we get the complete set of residues modulo $n!~.$ Let $X=(x_1,x_2,x_3,\ldots,x_n)$ be the permutation such that
$S(X)\equiv \left(\frac{n+1}{2}\right)\left(\sum_{i=1}^{n}c_i\right)\pmod{n!}$ Define $\overline{X}=(n+1-x_1,n+1-x_2,\ldots,n+1-x_n),$ note that $X\ne \overline{X}$ and that $\overline{X}$ is a valid permutation.
Now,
$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!}$ Which is a contradiction to our assumption. And we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#9 h Apr 28, 2019, 4:48 AM • 4 Y

Y by shivprateek, Adventure10, Mango247, cubres

Suppose for sake of contradiction that this didn't happen. Then, all the $S(\sigma)\pmod{n!}$ are different for all $\sigma\in S_n$ . Choose $\sigma$ uniformly at random. By linearity of expectation, we have
$\mathbb{E} S(\sigma)=c_i\frac{n+1}{2},$ so
$\sum_{\sigma\in S_n}S(\sigma)=\frac{(n+1)!}{2}\sum_{i=1}^n c_i\equiv 0\pmod{n!}$ since $\frac{n+1}{2}\in\mathbb{Z}$ . By the hypothesis, we have
$\sum_{\sigma\in S_n}S(\sigma)\equiv\sum_{k=0}^{n!-1}k\equiv\frac{n!(n!-1)}{2}\pmod{n!},$ which isn't divisible by $n!$ since $n!-1$ is odd (this is why we need $n>1$ ), This is a contradiction, as desired. $\blacksquare$

This post has been edited 1 time. Last edited by yayups, Apr 28, 2019, 4:49 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#10 h Sep 5, 2019, 1:01 AM • 1 Y

Y by Adventure10

Assume FTSOC that all the $S(\pi)$ 's are distinct mod $n!$ for all $\pi \in S_n$ . Then
$\sum_{\pi \in S_n} S(\pi) \equiv 0+\cdots+(n!-1) = \frac{(n!-1)(n!)}{2} \not \equiv 0 \pmod{n!}$ since $n!$ is even for $n>1$ .

Treat the permutations and $\{c_i\}$ as vectors in $\mathbb{F}_{n!}^n$ . Note that the vector sum of all the permutations is
$((n-1)!\cdot (1+\cdots+n))(1,\ldots,1) = \frac{n!(n+1)}{2}(1,\ldots,1).$ Then
$\begin{align*} \sum_{\pi \in S_n} S(\pi) &= \sum_{\pi \in S_n} \vec{c}\cdot \pi \\ &= \vec{c} \cdot \sum_{\pi \in S_n} \pi \\ &= \vec{c} \cdot \frac{n!(n+1)}{2} (1,\ldots,1) \\ &= \frac{n!(n+1)}{2} \left(\sum c_i \right) \equiv 0 \pmod{n!} \end{align*}$ since $n$ is odd. Contradiction!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

aops29

452 posts

aops29

#11 h Dec 8, 2019, 5:59 PM • 3 Y

Y by AlastorMoody, Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AlastorMoody

2125 posts

AlastorMoody

#12 h Dec 29, 2019, 3:18 PM • 1 Y

Y by Adventure10

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

popcorn1

1098 posts

popcorn1

#13 h Oct 7, 2020, 8:18 PM • 2 Y

Y by Mango247, Mango247

For storage.

Suppose not. Then let $\mathcal{P}$ be the set of all permutations $a$ . Now for all permutations, their residues are distinct modulo $n!$ . Hence
$\begin{align*} 0 + 1 + \dots + (n! - 1) &\equiv \sum_{a\in\mathcal{P}} S(a) \\ &\equiv \frac{n(n+1)}{2}\cdot(n-1)!\cdot\sum_{i=1}^n c_i \end{align*}$ by looking at the amount of times $1$ , $2$ , $\dots$ , $n$ appears in the $i$ th slot. But $\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$ and $n$ is odd, so the RHS is congruent to $0$ modulo $n!$ . Hence we have $\frac{(n!-1)(n!)}{2} \equiv 0 \mod{n!}$ . But $n!$ is even, so this is equivalent to $-\frac{n!}{2}$ , which is clearly nonzero modulo $n!$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HrishiP

1346 posts

HrishiP

#15 h Dec 23, 2020, 1:23 PM

Y by

For the sake of contradiction assume this is not the case, which implies that $S(a)$ takes on every residue modulo $n!$ as it ranges over all permutations. Letting $P$ be the set of all permutations, we have that
$\begin{align*} \sum_{k \in P} S(k) &\equiv 0+1+2+\cdots + (n!-1)\\ &\equiv \frac{(n!-1)(n!)}{2} \pmod{n!}. \end{align*}$
If we compute
$\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*}$ So, $\sum_k S(k) \equiv 0 \mod{n!}.$ Thus we can deduce that
$\frac{(n!-1)(n!)}{2} \equiv 0 \pmod{n!},$ which is a contradiction since $n!$ is even. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AwesomeYRY

579 posts

AwesomeYRY

#16 h Jun 15, 2021, 4:52 AM

Y by

AFTSOC that all $S(a)\neq S(b)$ , then the set of $S(p)$ is the residues from $0,1,\ldots, n!-1$ . Let $P$ be the set of all permutations, then
$\sum_{p\in P} S(p) \equiv \frac{(n!-1)(n!)}{2} \not\equiv 0 \pmod{n!}$ 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!}$ a contradiction, so we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ryanbear

1055 posts

ryanbear

#54 h May 20, 2024, 6:02 AM

Y by

for this to be false the values of $S(a)$ have to be from $0$ to $n!-1$ mod $n!$
but then when you sum it you get that it is not $0$ mod $n!$ from the mods, but from the $c$ s, it is $0$ mod $n!$ , so there is a contradition
so that means that this statement is true

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

de-Kirschbaum

192 posts

de-Kirschbaum

#55 h Jul 22, 2024, 2:45 AM

Y by

Let us put the permutations as $\sigma_1,\ldots,\sigma_{n!}$ . Then if no two $S(\sigma_i) \equiv S(\sigma_j) \mod{n!}$ , we have that $S(\sigma_1),\ldots,S(\sigma_{n!})$ form a complete residue system of $n!$ , that means
$\sum_{i=1}^{n!} S(\sigma_i) \equiv \frac{n!(n!-1)}{2} \mod {n!}$ but on the other hand we could also evaluate $\sum_{i=1}^{n!} S(\sigma_i) \equiv \frac{n!(n+1)}{2}(c_1+\ldots+c_n) \equiv 0 \mod{n!}$ as $n+1$ is even. Thus since $\gcd(n!-1,n!)=1$ , we must have $\frac{n!}{2} \equiv 0 \mod{n!}$ which is absurd as $3 \leq \frac{n!}{2}<n!$ .

This post has been edited 2 times. Last edited by de-Kirschbaum, Aug 16, 2024, 2:28 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bjump

999 posts

bjump

#56 h Aug 15, 2024, 12:41 AM

Y by

Suppose FTSOC there does not exist two permutations $a$ , and $b$ such that $S(a)- S(b) \equiv 0 \pmod{n!}$ . Observe that $\sum_{a \in \text{perms}} S(a) = \frac{n!}{2}(n+1)(c_1+c_2 + \cdots + c_n)$ However as $n+1$ is even this is divisible by $n!$ . Now notice that since all $n!$ different $S(a)$ 's have a distinct remainder modulo $n!$ then $\sum_{a \in \text{perms}} S(a) \equiv \frac{n!(n!-1)}{2} \equiv -\frac{n!}{2} \pmod{n!}$ which is not divisible by $n!$ , which contradicts the divisibility from earlier meaning we can conclude.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RedFireTruck

4220 posts

RedFireTruck

#57 h Sep 13, 2024, 4:11 AM

Y by

It suffices that $S$ over all $n!$ permutations taking on values $0$ , $1$ , $\dots$ , $n!-1$ in $\pmod{n!}$ is impossible.

Let $C$ be the sum of all $c_i$ . The sum of $S(a)$ over all permutations $a$ is then equal to $C\frac{n(n+1)}2(n-1)!=C\frac{(n+1)!}2$ . The sum of $0$ , $1$ , $\dots$ , $n!-1$ is $\frac{(n!-1)n!}{2}$ . Since $n$ is odd, $n!|\frac{(n+1)!}2$ but since $n!-1$ is odd, $n!\not|\frac{(n!-1)n!}2$ , which means our original statement is proven, as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AshAuktober

985 posts

AshAuktober

#58 h Oct 2, 2024, 8:33 AM

Y by

Assume that all the $S(a)$ are distinct $\pmod{n!}$ .

Then they must cover all residues $\pmod{n!}$ .
Now,consider $\mathcal{S} = \sum_{a \in [n]} S(a)$ .

Note that $\mathcal{S} \equiv 1 + \dots + n! \equiv \frac{(n!)(n!+1)}{2} \equiv \frac{n!}{2} \pmod{n!}.$

But we can also write $\mathcal{S}$ as $\sum_{i = 1}^n\sum_{a \in [n]} \sum c_ia_i$ $\equiv (n-1)!c_i \sum_{i = 1}^n i$ $\equiv 0 \pmod{n!},$ contradiction. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

numbertheory97

42 posts

numbertheory97

#59 h Oct 4, 2024, 2:12 AM

Y by

Suppose to the contrary that all $n!$ values of $S(a)$ are distinct mod $n!$ . Summing $S$ over all permutations, we have $\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),$ which is divisible by $n!$ since $n$ is odd. But by assumption $\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!},$ a contradiction. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1252 posts

ezpotd

#60 h Oct 16, 2024, 3:29 AM

Y by

If this were not true, all the permutations would have distinct $S$ values mod $n!$ , implying that their total sum mod $n!$ would be $\frac 12 n! (n! - 1 ) \equiv \frac 12 n! \mod n!$ , but we also have $\sum S(p) = (n - 1)! n(n + 1) \frac 12 (\sum c_i) = n! (\frac{n + 1}{2}) \sum c_i \equiv 0 \mod n!$ where the sum is over all permutations $p$ , which is a contradiction.

This post has been edited 1 time. Last edited by ezpotd, Oct 16, 2024, 3:29 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

538 posts

Maximilian113

#61 h Nov 28, 2024, 7:47 PM

Y by

For the sake of a contradiction, suppose otherwise. Then each $S(k)$ has a different residue mod $n!,$ so the sum of all the $S_i$ is $\frac{n!(n!-1)}{2} \pmod {n!}.$ However, we can also count this as $(n-1)!\left( \sum^n_{i=1} c_i \right) \left( \sum^n_{i=1} a_i \right) = \frac{(n+1)!}{2} \sum^n_{i=1} c_i \pmod {n!}.$ However, note that since $(n+1)$ is even, $n!$ divides $\frac{(n+1)!}{2}.$ However, $n!-1$ is odd so $n!$ cannot possibly divide $\frac{n!(n!-1)}{2},$ a contradiction. QED

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Anshu_Singh_Anahu

69 posts

Anshu_Singh_Anahu

#62 h Dec 1, 2024, 4:35 PM

Y by

Contradiction and double counting finsihed

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lpieleanu

2899 posts

lpieleanu

#63 h Dec 5, 2024, 1:27 PM • 1 Y

Y by KevinYang2.71

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eg4334

629 posts

eg4334

#64 h Dec 9, 2024, 12:56 AM

Y by

Assume the contrary, thus the $S(a)$ must biject to residues mod $n!$ , namely $\{1, 2, \dots, n!\}$ . Adding up all $S(a)$ gives $\frac{n(n+1)}{2} (\sum c_i) (n-1)!$ but this is also equal to $\frac{n!(n!+1)}{2}$ mod $n!$ . The left side is clearly zero mod $n!$ but the right side is not because $n!+1$ is odd, done.

This post has been edited 2 times. Last edited by eg4334, Dec 9, 2024, 3:24 AM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexanderhamilton124

388 posts

alexanderhamilton124

#65 h Jan 15, 2025, 6:53 PM

Y by

Suppose, FTSOC, there doesn't. That means all the permutations form a complete residue system $\mod{n!}$ . Summing up all the permutations, we see that:
$c_1((n - 1)! + (n - 1)! \cdot 2 + ... + (n - 1)! \cdot n) + ... + c_n((n - 1)! + (n - 1)! \cdot 2 + ... + (n - 1)! \equiv \frac{n!(n! + 1)}{2} \mod{n!}$ That means $\frac{n!(n! + 1)}{2} \equiv 0\mod{n!}$ , a clear contradiction as $n!$ is even, so we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

NerdyNashville

6 posts

NerdyNashville

#66 h Mar 2, 2025, 8:01 AM

Y by

\Well, my solution is similar to others. Let, for the sake of contradiction, no such $a, b$ exist for which:
$S(a) \equiv S(b) \mod n!$ Thus, all $n!$ permutations will have different residue modulo $n!$ . Now,
$\sum S(n)_a \equiv 0 + 1 + 2 + \dots + (n! - 1) \equiv \frac{(n! - 1)n!}{2} \mod n!$ 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!$ as $n$ is odd.

So,
$\frac{n!}{2} \equiv 0 \mod n!$ which is a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

NicoN9

113 posts

NicoN9

#67 h Apr 3, 2025, 5:34 AM

Y by

Outline:

Assume for a contradiction, and let $a_1,\dots, a_{n!}$ be permutations. Then consider $n!$ permutation to get $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$ On the other hand, each of $S(a_i)$ are distinct $\pmod {n!}$ , so $S(a_1)+\dots S(a_{n!}) \equiv \frac{1}{2} n!(n!+1)\pmod {n!}.$ Now we have $\frac{1}{2}(n+1)!\sum c_i \equiv \frac{1}{2} n!(n!+1)\pmod{n!}.$ which is a contradiction since LHS is zero but RHS is nonzero.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

gladIasked

647 posts

gladIasked

#68 h Apr 14, 2025, 1:41 AM

Y by

There are clearly $n!$ permutations of $\{1, 2, \dots, n\}$ . If two of these permutations have $S(a)$ congruent modulo $n!$ , then we're done. Now, assume for the sake of contradiction that these permutations are all not congruent modulo $n!$ . Then, we must have one permutation corresponding to every residue modulo $n!$ . Summing $S(a)$ over all permutations gives us $0+1+2+\dots+(n!-1)\equiv \frac{n!}2\pmod {n!}$ .

On the other hand, each number from $1$ to $n$ appears in a given position exactly $(n-1)!$ times; if we sum over each position, we obtain $\sum^{n}_{i=1}c_i(n-1)!(1+2+\dots+n)\equiv 0\pmod {n!}$ , a contradiction. Therefore, there must exist two permutations $S(a)$ congruent modulo $n!$ . $\blacksquare$

This post has been edited 1 time. Last edited by gladIasked, Apr 14, 2025, 1:41 AM

Z K Y