show that all $n+1$ cyclic shifts of an augmented Dyck path are distinct 
Define an augmented Dyck path from $(-1,-1)$ to $(2n,0)$ to be a path where the first step is an up step (corresponding to the vector $(1,1)$) and every other step is either an upstep or a down step down step (corresponding to the vector $(1,-1)$) and the path never goes below the x-axis. Let $X_n$ be the set of all paths from $(-1,-1)$ to $(2n,0)$ where the first step is an up step and every other step is either an upstep or a downstep. To each augmented Dyck path, associate a word $w_n$ consisting of the letters $U$ for an upstep in the corresponding part of the path and $D$ for a downstep in the corresponding part and let $W_n$ be the set of these words. Define the kth cyclic shift of an element in $w\in W_n$, say $w_1\cdots w_{2n+1}$, where $w_k = U$, to be $w_k \cdots w_{2n+1}w_1\cdots w_{k-1}$. Prove that all $n+1$ cyclic shifts of any element of $W_n$ are distinct.


Source: this is inspired by problem #16 of the 2001 HMMT Guts Round.

Choose $k > 0$ to be minimal such that cyclically shifting by $k$ places fixes a word $w\in X_n$. We claim that $k=2n+1,$ which shows that all $n+1$ cyclic shifts beginning with a distinct U are distinct. Consider the equivalence relation on $[2n+1] := \{1,\cdots, 2n+1\}$ given by $i~j$ iff $i\equiv j+kx\mod 2n+1$ for some $x\in \mathbb{Z}$. For each equivalence class under $~$, all of the letters in those positions must be the same. We now find the shortest period $d$ of the word w, which is defined to be the smallest $c$ so that $w_{i+c} = w_i$ for all i, where we take indices modulo $n$ so that $w_{i+n}=w_i$ for all $i$ and we just define $w_1,\cdots, w_n$ as a base case. One can show using the division algorithm that if $j$ is a period for w, then $d | j.$ By assumption, both $k$ and $2n+1$ are periods of $w $ (rotating by k and fixing w is equivalent to w having a period of k), so $d | k,2n+1.$ Now we just need to show that $d = \gcd(k,2n+1)$. To see why, we can write $d = ak+(2n+1)b$ for some integers a and b and then using the fact that $k$ and $2n+1$ are periods of w, we see that $w_{i+d} = w_i$ for all i. Now if an element $j$ belongs to the equivalence class of the element i, then by definition, $j-i$ is a period of $w$ (since $w_{a+i} \equiv w_{a+j}$ for all indices a), and so $d | j-i,$ which implies that $i \equiv j\mod d.$ Now the number of solutions $j\in \{1,\cdots, 2n+1\}$ to $j\equiv i\mod d$ is precisely $(2n+1)/d.$ To see why this holds, it suffices to show that all solutions are given by $i + ad$ for $a\in \{0,1,\cdots, (2n+1)/d - 1\}.$ For a solution j, write $j= i+dt.$ Then if $t\equiv a\mod (2n+1)/d,$ we have $dt\equiv da\mod (2n+1),$ so $j\equiv i+da\mod 2n+1.$ Finally, all the solutions $i+ad$ for $a\in \{0,1,\cdots, (2n+1)/d-1\}$ are distinct since if $i+a_1 d \equiv i+a_2 d\mod 2n+1,$ then $d(a_1-a_2) \equiv 0\mod (2n+1)\Rightarrow a_1 - a_2\equiv 0\mod (2n+1)/d\Rightarrow a_1 = a_2$ as $a_1,a_2\in \{0,1,\cdots, (2n+1)/d-1\}$. Hence the claim that the cardinality of the equivalence class is $(2n+1)/\gcd(2n+1,k)$ indeed holds.

But I'm not sure how to show $k$ must equal $2n+1$ in this case. Of course, it would be enough to show that $m = 1$. The latter would follow if one knew that $m$ must divide both the number of upsteps and the number of down steps in $P_w$, but that doesn't seem obvious to me.


If we slant the graph of the augmented Dyck path down by slope $-\frac{1}{2n+1}$, it starts and ends at the same $y$-coordinate, and in between is always above that $y$-coordinate. So after any cyclic shift, a similar slant downward will expose the unique global minimum as the shifted position of the original start of the augmented Dyck path.
More formally:
Define the function $\delta: \{\mathrm U,\mathrm D\} \to \mathbb{R}$ with $\delta(\mathrm U) = +1$ and $\delta(\mathrm D) = -1$. To every word $w_1\ldots w_{2n+1}$ containing only letters U and D, associate the sequence $(s_0, \ldots, s_{2n+1})$ defined by
$$ s_j = \sum_{i=1}^j \left(\delta(w_i) - \frac{1}{2n+1}\right) $$
If the word corresponds to an augmented Dyck path:
$s_0 = s_{2n+1} = 0$. Since $w_1 = \mathrm U$, $s_1 = \frac{2n}{2n+1}$. The constraint that the path doesn't go below the $x$-axis after the first step from $(-1,-1)$ to $(0,0)$ means that $\sum_{i=2}^j \delta(w_i) \geq 0$ for every $j$. Therefore when $2 \leq j \leq 2n$, $s_j \geq s_1 - \frac{j-1}{2n+1} > 0$. The minimum value of the sequence is $0$, attained only at $s_0$ and $s_{2n+1}$.
Since $s_0 = s_{2n+1}$, we can extend this sequence to an infinite repeating sequence with period $2n+1$.
The $k$-th cyclic shift of an augmented Dyck path then has associated sequence $(t_0, \ldots)$ with terms defined by
$$ t_j = \sum_{i=1}^j \left(\delta(w_{k+i-1}) - \frac{1}{2n+1}\right) =
 s_{k+j-1} - s_{k-1} $$
The minimum value of $t_j$ is $-s_{k-1}$, attained only when $k+j-1 \equiv 0 \pmod{2n+1}$. Since each value of $k$ puts the minimum value in a different position $j$, two different cyclic shifts must have different sequences $(t_j)$ and therefore different shifted words.
