Proposed by Tejawsi Navilarekallu. It had only one complete solve at the camp, by Deepesh Singhal, contestant IND 6 for 2016.

Let $n/d$ be the order of $\sigma$ as a group element of $S_n$. Without loss of generality, $n/d$ is a prime, since otherwise we can replace $\sigma$ by a power of $\sigma$ (and a $k$ would still exist). Then $d$ is an integer and $\gcd(k,n^2) = nd$. We claim $\sigma$ is $d$ disjoint cycles of length $n/d$. Because applying $\sigma$ $n/d$ times is the first time we get the identity permutation back, each cycle length divides $n/d$. Furthermore each time we apply $\sigma$, shifting the sequence up by $k$, the location of each ordered pair $(x_i, x_{i+1})$ changes location, and none of them return to the same position before applying the permutation $n/d$ times when all of them do. If a cycle length in $\sigma$ had length $m < n/d$, then applying $\sigma$ $m$ times would result in all occurrences of at least one number $a$ returning to the original position, which means $(a,a)$ is in its original position, contradicting $m < n/d$. We now know the cycle structure of $\sigma$. Since we can permute 1 to $n$ in the original sequence as we please, we may assume WLOG that $k = nd$ and $\sigma(x) \equiv x + d \pmod{n}$. Let $z_i$ be the residue of $x_{i+1} - x_i$ mod $n$ for each $i$, with indices mod $n^2$. We have $z_i = z_{i+d}$ by applying $\sigma$ to the sequence repeatedly. From the $n$-good conditions we also know that each residue occurs $n$ times among $z_1, z_2, \ldots, z_{n^2}$, and by looking at applications of $\sigma$ we can strengthen this to say that $z_1, z_2, \ldots, z_{nd}$ contains each residue $d$ times. Then we have \[ z_1 + z_2 + \cdots + z_{nd} \equiv d(1+2+\cdots+n)\pmod{n}, \]and \[ z_1 + z_2 + \cdots + z_{nd} \equiv x_{nd+1} - x_1 \equiv d \pmod{n}. \]So we conclude that \[ d(1+2+\cdots+n) \equiv d \pmod{n}, \]where $d < n$ is a divisor of $n$. If $n$ is odd, then the left side is 0 mod $n$, so the above condition fails. If $n$ is even, then the above is satisfied when $d$ is odd. Since we specified that $n/d$ was prime above, we have $n/d = 2$, meaning $n$ is 2 times an odd number as desired.

bobthesmartypants wrote:

Can someone explain more about this please,why we have this identy?

We have the following structural claim about the permutation $\sigma$. Claim: All cycles in the complete cycle decomposition of $\sigma$ have the same length. Equivalently, every element of $[n]$ has the same order under the action of $\sigma$. Proof: Suppose $i\in[n]$ has order $\ell$. Then, $(\sigma^r(i),\sigma^r(i))\ne(i,i)$ for $1\le r\le \ell-1$, and $(\sigma^\ell(i),\sigma^\ell(i))=(i,i)$. Thus, if $j$ is the unique index such that $(i,i)=(x_j,x_{j+1})$, then $j+\ell k\equiv j\pmod{n^2}$ and $j+rk\not\equiv j\pmod{n^2}$. This implies that $\ell$ is the order of $k$ in the additive group $\mathbb{Z}/n^2\mathbb{Z}$, which doesn't depend on the choice of $i$, so each element has the same order, as desired. $\blacksquare$ Let $p=n/\ell$. Note that the problem remains the same under any relabeling of $[n]$, so WLOG, we may assume that \[\sigma = \prod_{i=0}^{p-1}(i,i+p,i+2p,\ldots,i+(\ell-1)p).\]Thus, $x_{k+j}=(x_j+p\pmod{n})$. Note that the lists \begin{align*} &(x_0,x_1),\ldots,(x_{k-1},x_k) \\ &(x_k,x_{k+1}),\ldots,(x_{2k-1},x_{2k}) \\ &\vdots \\ &(x_{(\ell-1)k},x_{(\ell-1)k+1}),\ldots,x_{(\ell-1)k+k-1},x_{\ell k}) \end{align*}list out all pairs $(x_g,x_{g+1})$ exactly $r:=\ell k/n^2$ times. For each of these lists of pairs, the list formed by the difference of each pair is the same mod $n$, so in fact the list of differences \[x_1-x_0,\ldots,x_k-x_{k+1}\]contains each residue from $0$ to $n-1$ mod $n$ exactly $(\ell k/n^2)\cdot(n/\ell)=k/n$ times. Summing these differences, we learn that \[x_1-x_{k+1}\equiv \frac{k}{n}\cdot\frac{n(n-1)}{2}\pmod{n},\]or that \[n\left|\frac{n}{\ell}+\frac{k}{n}\cdot\frac{n(n-1)}{2}\right. .\]If $n$ is odd, then $n\mid\frac{n(n-1)}{2}$, so $n\mid n/\ell$, or $\ell=1$, or $\sigma=\mathrm{id}$, which isn't allowed. Therefore, $n$ is even. Then, $\frac{n(n-1)}{2}\equiv\frac{n}{2}\pmod{n}$, so \[\frac{n}{\ell}+\frac{k}{2}\equiv 0\pmod{n}.\]Recall that $k$ is a multiple of $n$, so the only way this can work without $\ell=1$ is if $\ell=2$, and $k$ is an odd multiple of $n$. Then, we have $\ell k=rn^2$, so $2(\mathrm{odd})n=rn^2$, so $rn\equiv 2\pmod{4}$. Since $n$ is even, this implies $n\equiv 2\pmod{4}$, as desired.

We call a group of elements of $\{x_i\}$ a family if, for any $x_i, x_j$ in the family, we have $i \equiv j \pmod{k}$. Let $s = \gcd(k, n^2)$. Note that each family contains elements from exactly one cycle of $\sigma$, that each family contains exactly $\frac{n^2}{s}$ elements, and that there are exactly $k$ distinct families. Additionally, note that there are exactly $n^2$ distinct elements in $\{1, \ldots, n\} \times \{1, \ldots, n\}$. As the pairs $(x_i, x_{i + 1})$ are all distinct, it follows by Pigeonhole that for any $1 \leq i, j \leq n$, there exists $i$ such that $(x_i, x_{i + 1}) \equiv (i, j)$. In particular, this implies that each element of $\{1, \ldots, n\}$ appears exactly $n$ times in $\{x_i\}$. This also implies that, for each cycle of $\sigma$, there is a family whose elements are the same as those of that cycle. Claim: We have $k \mid n^2$. Proof: Consider a cycle $\mathcal{C}$ of $\sigma$, and let $\mathcal{F}$ be a family containing only the elements of $\mathcal{C}$. Let $x_i \in \mathcal{F}$. Noting that $i + k \cdot \frac{n^2}{s} \equiv i \pmod{n^2}$, we find that $x_{i + k \cdot \frac{n^2}{s}} = \sigma^{n^2/s}(x_i) = x_i$. This implies that $c \mid \frac{n^2}{s}$. Now, as the $\mathcal F$ contains $\frac{n^2}{s}$ elements, it follows that each element of $\mathcal{C}$ appears $\frac{n^2}{cs}$ times in $\mathcal F$. As each element of $\mathcal{C}$ must appear exactly $n$ times in $\{x_i\}$, it follows that there are $\frac{n}{\frac{n^2}{cs}} = \frac{cs}{n}$ families containing only the elements of $\mathcal{C}$. Summing over all cycles $\mathcal{C}$, we find that there are exactly \begin{align*} \sum_{\mathcal{C}} \frac{cs}{n} &= \frac{s}{n} \sum_{\mathcal{C}} c \\ &= \frac{s}{n} \cdot n \\ &= s \end{align*}families (where the second equality is because each element of $\{1, \ldots, n\}$ is in exactly one cycle $\mathcal{C}$). However, a stated above there are exactly $k$ cycles. This implies that $s = \gcd(k, n^2) = k$, implying the claimed $k \mid n^2$. $\blacksquare$ Now, for any cycle $\mathcal{C}$, there must exist $i$ for which $x_i$ and $x_{i + 1}$ are both elements of $\mathcal{C}$: if not, for any two (not necessarily distinct) elements $a, b$ of $\mathcal{C}$, we have $(x_i, x_{i + 1}) \neq (a, b)$ for each $i$, contradiction. Letting $c$ be the size of $\mathcal{C}$, we find that $x_{i + kc} = \sigma^c(x_i) = x_i$ and $x_{i + kc + 1} = \sigma^c(x_{i + 1}) = x_{i + 1}$, implying that $(x_i, x_{i + 1}) = (x_{i + kc}, x_{i + kc + 1})$, implying that $i \equiv i + kc \pmod{n^2}$, or that $kc \equiv 0 \pmod{n^2}$. Hence, we have $\frac{n^2}{k} \mid c$. However, recall that $c \mid \frac{n^2}{s} = \frac{n^2}{k}$, implying that $c = \frac{n^2}{k}$. Thus, each cycle of $\sigma$ has length $\frac{n^2}{k}$. Note now that $\frac{n^2}{k} \mid n$, implying that $n \mid k \mid n^2$; hence, we may write $k = nr$, for some $r \mid n$. This implies that $\sigma$ has exactly $r$ cycles, each with length $c = \frac{n}{r}$. WLOG, let these cycles be $\mathcal{C}_t = tc + 1 \to tc + 2 \to \cdots \to tc + \frac{n}{r}$. Now, as each element of $\{1, \ldots, n\} \times \{1, \ldots, n\}$ appears exactly once in the set of pairs $(x_i, x_{i + 1})$, it follows that as $i$ ranges between $1$ and $n^2$, $x_{i + 1} - x_i$ hits each modulo $c$ residue exactly $\frac{n^2}{c} = k$ times. Noting that $x_{i + k + 1} - x_{i + k} \equiv x_{i + 1} - x_i \pmod{c}$, it follows that each modulo $c$ residue is hit exactly $\frac{k}{c} = r^2$ times by $x_{i + 1} - x_i$ as $i$ ranges between $1$ and $k$. Let $j \equiv x_{k + 1} - x_k \pmod{c}$. The sequence $\{ x_{i + 1} - x_i \pmod{c} \}_{i = 1}^{k - 1}$ then contains $j$ exactly $r^2 - 1$ times, and every other modulo $c$ residue exactly $r$ times. We now evaluate $x_k \pmod{c}$ in two different ways. On one hand, we have $x_{k + 1} - x_k \equiv j \pmod{c}$, or $x_k \equiv (x_1 + 1) - j \pmod{c}$. On the other hand, we have \begin{align*} x_k - x_1 &\equiv \sum_{i = 1}^{k - 1} (x_{i + 1} - x_i) \pmod{c} \\ x_k - x_1 &\equiv \left(r^2\sum_{i = 0}^{c - 1} i\right) - j \pmod{c} \\ x_k - x_1 &\equiv \frac{1}{2}r^2(c)(c - 1) - j \pmod{c}\\ x_k &\equiv \frac{1}{2}r^2(c)(c - 1) - j + x_1 \pmod{c}. \end{align*}Therefore, \begin{align*} \frac{1}{2}r^2(c)(c - 1) - j + x_1 &\equiv (x_1 + 1) - j \pmod{c} \\ \frac{1}{2}r^2c(c - 1) &\equiv 1 \pmod{c} \\ r^2c(c - 1) &\equiv 2 \pmod{c} \\ 2 &\equiv 0 \pmod{c}. \end{align*}This implies that $\frac{n}{r} \mid 2$. In the case that $\frac{n}{r} = 1$, we find that $r = n$, or that $\sigma$ contains $n$ cycles, each with length $1$, implying that $\sigma$ is the trivial permutation -- a contradiction. Hence, $c = \frac{n}{r} = 2$. We now get \begin{align*} \frac{1}{2}r^2(2)(1) &\equiv 1 \pmod{2} \\ r^2 &\equiv 1 \pmod{2}, \end{align*}so $r$ is odd. Thus, $n = 2r \equiv 2 \pmod{4}$, as desired. $\Box$

Consider a cycle $(a_1,a_2,\dots,a_m)$ of $\sigma$. Because the sequence $(x_i)$ is good, there exists $i$ such that $(x_i,x_{i+1}) = (a_1,a_2)$. Then we have \[(x_{i+k},x_{i+1+k}) = (a_2,a_3), \dots, (x_{i+mk},x_{i+1+mk}) = (a_1,a_2).\]Because the map $i \to (x_i,x_{i+1})$ is a bijection, we see that $n^2\mid km$. Summing this over all cycles of $\sigma$, we get $n^2\mid kn \implies n\mid k$. Denote $k=\ell n$, then clearly every cycle of $\sigma$ has length $m=\frac{n}{\gcd(n, \ell)}$ (say, by following the orbit of $(a,a)$ for $a\in[n]$). Therefore, by relabeling the labels $1,2,\dots,n$, one can WLOG assume $\sigma(a) = a+\frac{n}{m} = a + \gcd(n,\ell)$. This means that $x_{i+1}-x_i = x_{i+k+1}-x_{i+k}$. Because every difference $x_{i+1}-x_i$ appears $n$ times, it appears $\ell \cdot \gcd(n,\ell)$ times among \[x_2-x_1, x_3-x_2,\dots,x_{k+2} - x_{k+1}.\]Summing everything up, we get \[\frac{n(n-1)}{2} \cdot \ell \cdot \gcd(n,\ell) \equiv \gcd(n,\ell) \pmod{n}\]which is equivalent to \[\frac{n}{\gcd(n,\ell)}\ \bigg|\ (\frac{\ell n(n-1)}{2} - 1)\]By nontriviality of $\sigma$ we have $\ell \neq n$. This forces $\frac{l(n-1)}{2}$ to be non-integer, so $l$ is odd and $n$ is even. If $n$ is divisible by 4, then the left hand side is also divisible by 4, while the right hand side is clearly not, a contradiction. Thus, $n\equiv 2\pmod{4}$.