Let {a_1, a_2, a_3, a_4, a_5}={2,4,1,3,5}

who has a good idea

Can someone check this as it feels too short. First of all, is is obvious that $K$ is divisible by $p$, as given a sequence $\left(a_1,\ a_2,\ ...\ a_p\right)$, we can shift it along any amount from $1$ to $p-1$ spaces to get a new valid sequence, for example $\left(a_2,\ a_3,\ a_4,\ ...\ a_p,\ a_1\right)$. Now given any sequence $\left(a_1,\ a_2,\ a_3,\ ...\ a_p\right)$, we can get another valid sequence $\left(ka_1,\ ka_2,\ ka_3,\ ...\ ka_p\right)$, where $k$ is an integer between $2$ and $p-1$, and all values are taken modulo $p$. We can do this because any permutation of $1,2,3,\ ...\ p-1,p$ is a complete residue modulo $p$ and so multiplying each one by a number coprime to $p$ will also give a complete residue, and it is obvious that our new sequence still satisfies the conditions. So for each starting sequence, we can scale it up in $p-1$ different ways, so $K$ is divisible by $p-1$. Also note that as the number $p$ does not move via scaling, we cannot accidentally double count by first reaching a sequence via shifting, and then via scaling.

chnlvsx wrote: Let {a_1, a_2, a_3, a_4, a_5}={2,4,1,3,5} You only give only one permutation which works. The problem ask more than that. Kaskade wrote: Can someone check this as it feels too short. First of all, is is obvious that $K$ is divisible by $p$, as given a sequence $\left(a_1,\ a_2,\ ...\ a_p\right)$, we can shift it along any amount from $1$ to $p-1$ spaces to get a new valid sequence, for example $\left(a_2,\ a_3,\ a_4,\ ...\ a_p,\ a_1\right)$. Now given any sequence $\left(a_1,\ a_2,\ a_3,\ ...\ a_p\right)$, we can get another valid sequence $\left(ka_1,\ ka_2,\ ka_3,\ ...\ ka_p\right)$, where $k$ is an integer between $2$ and $p-1$, and all values are taken modulo $p$. We can do this because any permutation of $1,2,3,\ ...\ p-1,p$ is a complete residue modulo $p$ and so multiplying each one by a number coprime to $p$ will also give a complete residue, and it is obvious that our new sequence still satisfies the conditions. So for each starting sequence, we can scale it up in $p-1$ different ways, so $K$ is divisible by $p-1$. Also note that as the number $p$ does not move via scaling, we cannot accidentally double count by first reaching a sequence via shifting, and then via scaling. The problem asks to prove that $p^2\mid K+p$. But it seems like you prove that $p(p-1)\mid K$. Those two are not equivalent.

MarkBcc168 wrote: The problem asks to prove that $p^2\mid K+p$. But it seems like you prove that $p(p-1)\mid K$. Those two are not equivalent. I agree. He indeed tried to prove $p(p-1)\mid K$ instead of $p^2\mid K+p$

MarkBcc168 wrote: The problem asks to prove that $p^2\mid K+p$. But it seems like you prove that $p(p-1)\mid K$. Those two are not equivalent. Thanks, I understand my error. However this also leads to the question, is my conclusion correct and if so, can we prove a stronger result?

Similar to this. https://artofproblemsolving.com/community/c6h589039p3487572

@Kaskade You said "where $k$ is an integer between $2$ and $p-1$", but $(p-1)-2+1=p-2$. So shouldn't it be $p(p-2)|K$?

WolfusA wrote: @Kaskade You said "where $k$ is an integer between $2$ and $p-1$", but $(p-1)-2+1=p-2$. So shouldn't it be $p(p-2)|K$? No, you must also count the one with $k=1$ (which is your initial one). Or to put it another way: You get $p-2$ new ones from each old one, giving a total of multiplying by $p-1$.

Note that we can consider every terms in modulo $p$. We will say that a permutation $a_1,a_2,...,a_p$ is AP-like iff there exists $d\in \{ 1,2,...,p-1\}$ that $a_i=a_1+(i-1)d$ for all $i$. It's easy to see that there're total of $p(p-1)$ AP-like permutations. Now, for each permutation $a_1,a_2,...,a_p$, we define $i$-dilated permutation to be $$a_1+i,a_2+i,...,a_p+i$$for each $i=0,1,2,...,p-1$ (not hard to see that it's still other permutation.) And define $j$-rotated permutation to be $$a_{j+1},a_{j+2},...,a_{j+p}$$for each $j=0,1,2,...,p-1$ (indices also considered in modulo $p$.) For convenient, we say that a permutation is good if it satisfy the condition in the problem. It's not hard to see that for any good permutation $\mathcal{P}$ that is not AP-like, the permutation obtained by $i$-dilated and then $j$-rotated is also good permutation, call this permutation $\mathcal{P}_{i,j}$, for all $i,j\in \{ 0,1,2,...,p-1\}$. Moreover, there not exists distinct pairs $(i_1,j_1),(i_2,j_2)$ that $\mathcal{P}_{i_1,j_1}=\mathcal{P}_{i_2,j_2}$. Hence, we can partition collection of non-AP-like good permutation into some sets, each contained exactly $p^2$ such permutations, so that for any $\mathcal{P},\mathcal{Q}$ in the same group, one can find $i,j$ that $\mathcal{P}_{i,j} =\mathcal{Q}$ (this can be done by verify that for all $(i_1,j_1),(i_2,j_2)$, there exists $(i_3,j_3)$ that $(P_{i_1,j_1})_{i_3,j_3}=P_{i_2,j_2}$.) So, we conclude that the number of non-AP-like good permutations is divisibly by $p^2$. And it's easy to check that all AP-like permutations are good permutations, this gives $$K\equiv p(p-1)\pmod{p^2}\implies p^2\mid K+p.$$

Another possible method is that WLOG we assume $a_p=p$. Let $L$ be the number of permutations $(a_1, a_2, \ldots, a_{p-1})$ of $\{ 1, 2, \ldots, p-1\}$ such that $a_1a_2+a_2a_3+\ldots + a_{p-2}a_{p-1}$is divisible by $p$ and $L'$ be the number of the rest permutations. We need to prove $p\mid L+1$ which is equivalent to $p\mid L'$. So it suffices to prove that $$\sum_{(a_1, a_2, \ldots, a_{p-1}) is permutation} ( a_1a_2+a_2a_3+\ldots + a_{p-2}a_{p-1})^{p-1}\equiv 0 \pmod p$$. This is where I stuck when doing this problem recently and I'm asking for help.