IMC 2022 · Day 2 · P6

Hint:

We show such a permutation.

Let $x_i \equiv i^{-1} \pmod p$ for $i = 1, 2, \cdots, p-1$. Then $$\sum_{i=1}^{p-2} x_i x_{i+1} \equiv \sum_{i=1}^{p-2} \frac{1}{i} \cdot \frac{1}{i+1} \equiv \sum_{i=1}^{p-2} \left( \frac{1}{i} - \frac{1}{i+1} \right) \equiv 1 - \frac{1}{p-1} \equiv \frac{p-2}{p-1} \equiv 2 \pmod p$$

We begin by noting that the identity permutation yields the value $$1 \cdot 2 + 2 \cdot 3 + \dots + (p-2)(p-1) = 2 \cdot \binom{p}{3} \equiv 0 \pmod p$$ as soon as $p > 3$. The idea now is to perturb that permutation to obtain the desired value 2.

One thing we can do is to replace $(i, i+1, i+2, i+3)$ by $(i, i+2, i+1, i+3)$. Indeed, this will decrease the sum by 3. So if $p \equiv 2 \pmod 3$, we can just take the permutation $(1, 3, 2, 4, 6, 5, 7, \dots, p-4, p-2, p-3, p-1)$ i.e. exchanging $3k - 1$ and $3k$ whenever $k = 1, 2, \dots, \frac{p-2}{3}$. This means we decrease the sum $\frac{p-2}{3}$ times by 3, leading to a remaining sum of $-(p-2) \equiv 2 \pmod p$.

If $p \equiv 1 \pmod 3$, this strategy does not work immediately. Instead, we can change $(1, 2, 3, 4, 5)$ to $(1, 4, 3, 2, 5)$ resulting in a decrement of the sum by 8. If we then exchange $3k$ and $3k + 1$ for $k = 2, 3, \dots, \frac{p-7}{3}$ as before, we get another $\frac{p-10}{3}$ times a decrement by 3, leading to a remaining sum of $-8 - \frac{p-10}{3} \cdot 3 \equiv 2 \pmod p$.

Of course this only works if $p \ge 13$. It thus remains to consider the cases $p = 3$ and $p = 7$ by hand. For $p = 3$, we just take $(1, 2)$ and for $p = 7$ we can take $(1, 4, 5, 2, 3, 6)$.