A path to combinatorics: proving that there are at least 2 people who have same number of people between them "An even number of persons are seated around a table. After a break, they are again seated around the same table, not necessarily in the same places. Prove that at least two persons have the same number of persons between them as before the break."
I don't think I have a proof, but I just want to get the feedback on my approach/idea. I have not looked at the solution on the book. Thank you in advance!!


 A: I agree with a comment that you wrongly understood the problem, which in reality asks if there is a pair of persons such that there is exactly same number of people between them before and after the break.
The problem is essentially about the permutation which sends $i\mapsto\sigma(i)$. We would like to prove that there are at least two indicies $i,j$, such that
$$
j-i=\sigma(j)-\sigma(i)\iff \sigma(i)-i=\sigma(j)-j.
$$
To avoid the problem with sign we may count the difference always in the same direction (say counterclockwise): $\delta(i)=(\sigma(i)-i)\pmod{2n}$. With this definition $\delta(i)$ can take the values $0,1,\dots 2n-1$.
Assume that there are no two persons that have the same number of people before and after the break: $$\forall i\ne j:\; \delta(i)\ne\delta(j).\tag1$$ This means that $\delta(i)$ takes all values from $0$ to $2n-1$, so that:
$$
\sum_{i=1}^{2n}\delta(i)=\sum_{k=0}^{2n-1}k=n(2n-1)\equiv n\pmod {2n}.\tag2
$$
But on the other hand since $\sigma(i)$ is the same set as $i$ it should be
$$
\sum_{i=1}^{2n}\delta(i)\equiv0\pmod {2n}.\tag3
$$
Since (2) and (3) cannot hold simultaneously the assumption (1) was wrong.
