BMO Short List

The answer is in the affirmative. Letting $\equiv$ denote congruence modulo $p^n$ throughout the argument, we will show that there exists a permutation $a_1, a_2, \dots, a_N$ of the numbers in $U$ such that $\sum_{k=1}^N a_k a_{k+1} \equiv p^{n-1}$.

Let $m = p^{n-1}-1$, so $N = p^{n-1}(p-1) = (m+1)(p-1)$, and write $U = \{u_1, u_2, \dots, u_N\}$, where $u_k = k+\lfloor k/(p-1) \rfloor$, $k = 1, 2, \dots, N$, and $\lfloor t \rfloor$ denotes the largest integer (strictly) less than the real number $t$.

That the $u_k$ are pairwise distinct and they all lie in $U$ follows from the fact that every $k$ in the range $1, 2, \dots, N$ is uniquely expressible in the form $k = (p-1)j + i$ for some $j$ in the range $0, 1, \dots, m$ and some $i$ in the range $1, 2, \dots, p-1$. Thus, $u_k = u_{(p-1)j+i} = pj + i$, so the $u_k$ are indeed pairwise distinct and they all lie in $U$.

For $k$ in the range $1, 2, \dots, N-1$, notice that $u_{k+1} - u_k = 1$, unless $k$ is divisible by $p-1$, in which case $u_{k+1} - u_k = 2$. Setting $u_{N+1} = u_1$, it is readily checked that $u_{N+1} - u_N = 2 - p^n \equiv 2$, so $u_{k+1} - u_k \equiv 2$ for all $k$ divisible by $p-1$.

Letting now $a_k$ be the multiplicative inverse of $u_k$ modulo $p^n$, i.e., $a_k$ is the unique member of $U$ satisfying $a_k u_k \equiv 1$, we show that the $a_k$ form the desired permutation of $U$.

To begin with, notice that $a_k a_{k+1} \equiv a_k - a_{k+1}$, unless $k$ is divisible by $p-1$, in which case $a_k a_{k+1} \equiv \frac{1}{2}(a_k - a_{k+1})$. This is easily established by multiplying both sides of each congruence by $u_k u_{k+1}$, and noticing that $(a_k - a_{k+1})u_k u_{k+1} \equiv u_{k+1} - u_k \equiv 1 \text{ or } 2$.

We are now in a position to evaluate the sum $S = \sum_{k=1}^N a_k a_{k+1}$ modulo $p^n$. Write
$$S = \sum_{k=1}^{N} a_k a_{k+1} = \sum_{j=0}^{m} \sum_{i=1}^{p-1} a_{(p-1)j+i} a_{(p-1)j+i+1},$$
and consider the inner sum for a fixed $j$ in the range $0, 1, \dots, m$:
$$\begin{align*} \sum_{i=1}^{p-1} a_{(p-1)j+i} a_{(p-1)j+i+1} &= \sum_{i=1}^{p-2} a_{(p-1)j+i} a_{(p-1)j+i+1} + a_{(p-1)j(j+1)} a_{(p-1)(j+1)+1} \\ &= \sum_{i=1}^{p-2} (a_{(p-1)j+i} - a_{(p-1)j+i+1}) + \frac{1}{2} (a_{(p-1)j(j+1)} - a_{(p-1)(j+1)+1}) \\ &= a_{(p-1)j+1} - a_{(p-1)(j+1)} + \frac{1}{2} (a_{(p-1)j(j+1)} - a_{(p-1)(j+1)+1}) \\ &= a_{(p-1)j+1} - \frac{1}{2} a_{(p-1)j(j+1)} - \frac{1}{2} a_{(p-1)(j+1)+1}. \end{align*}$$

Hence
$$\begin{align*} S &\equiv \sum_{j=0}^{m} a_{(p-1)j+1} - \frac{1}{2} \sum_{j=0}^{m} a_{(p-1)(j+1)} - \frac{1}{2} \sum_{j=0}^{m} a_{(p-1)(j+1)+1} \\ &\equiv \left( a_1 + \sum_{j=1}^{m} a_{(p-1)j+1} \right) - \frac{1}{2} \sum_{j=1}^{m+1} a_{(p-1)j} - \frac{1}{2} \left( \sum_{j=1}^{m} a_{(p-1)j+1} + a_{N+1} \right) \\ &\equiv \frac{1}{2} \sum_{j=1}^{m+1} a_{(p-1)j+1} - \frac{1}{2} \sum_{j=1}^{m+1} a_{(p-1)j}. \end{align*}$$
Since $u_{(p-1)j+1} = pj + 1$, the $a_{(p-1)j+1}$ form a permutation of the $pj + 1$, therefore $\sum_{j=1}^{m+1} a_{(p-1)j+1} = \sum_{j=1}^{m+1} (pj + 1)$. Similarly, $u_{(p-1)j} = pj - 1$, so the $a_{(p-1)j+1}$ form a permutation of the $pj - 1$, and hence $\sum_{j=1}^{m+1} a_{(p-1)j} = \sum_{j=1}^{m+1} (pj - 1)$. Consequently,
$$S \equiv \frac{1}{2} \sum_{j=1}^{m+1} ((pj + 1) - (pj - 1)) \equiv m + 1 \equiv p^{n-1},$$
as stated in the first paragraph. This completes the solution.