Form an equivalence relation on permutations as follows: $\sigma \sim \pi$ if and only if there is some $d$ such that for all $i$, $\pi(i) - \sigma(i) \equiv d \pmod{p}$. For any $i < p$ and any permutation $\pi$, the equivalence class of $\pi$ contains $p$ members, exactly one of which has the property that the sum of its first $i$ elements is divisible by $p$. Moreover, for every permutation $\pi$ we have $p \mid \pi(1) + \ldots + \pi(p)$. Thus, the expectation of $f(\pi)$ is precisely $\frac{1}{p} \cdot (p - 1) + 1$.

I don't understand two things about this problem. 1. Why this was treated as combinatorics? It's number theory, it's as clear as day. 2. Why only two teams solved that problem? It's way easier than other problems (not that all other problems are hard ) and answer is obvious from the very beginning. And it's not even original. Such methods are very well known.

JBL wrote: Form an equivalence relation on permutations as follows: $\sigma \sim \pi$ if and only if there is some $d$ such that for all $i$, $\pi(i) - \sigma(i) \equiv d \pmod{p}$. For any $i < p$ and any permutation $\pi$, the equivalence class of $\pi$ contains $p$ members, exactly one of which has the property that the sum of its first $i$ elements is divisible by $p$. Moreover, for every permutation $\pi$ we have $p \mid \pi(1) + \ldots + \pi(p)$. Thus, the expectation of $f(\pi)$ is precisely $\frac{1}{p} \cdot (p - 1) + 1$. Hi JBL! sorry but can u explain your solution more wisely and clearly, I couldn;t get it :S thanks beforehead

Swistak wrote: I don't understand two things about this problem. 1. Why this was treated as combinatorics? It's number theory, it's as clear as day. 2. Why only two teams solved that problem? It's way easier than other problems (not that all other problems are hard ) and answer is obvious from the very beginning. And it's not even original. Such methods are very well known. It might because you are so smart

zaurimeshveliani wrote: Hi JBL! sorry but can u explain your solution more wisely and clearly, I couldn;t get it :S thanks beforehead Let us take an example; say $p = 7$. Take any permutation $4,1,3,2,6,7,5$. Now consider the $7$ permutations related to this one, which is obtained by just adding $1$ modulo $7$. These are $$4,1,3,2,6,7,5$$$$5,2,4,3,7,1,6$$$$6,3,5,4,1,2,7$$$$\vdots$$$$3,7,2,1,5,6,4$$ Now consider the partial sums of these. The claim is that for each $1 \leq i < p$, exactly one of these permutations satisfies $p \mid \pi(1) + \cdots + \pi(i)$. Furthermore $p \mid \pi(1) + \cdots + \pi(p) $ is always true, obviously. Therefore for each such $p$ permutations related to each other, we have in all $(p-1) + p = 2p-1$ partial sums that are multiples of $p$. The average value is thus $$ \frac{2p-1}{p} = 2 - \frac{1}{p}$$as required.