USA Team Selection Test

Let $n$ be a positive integer. Consider sequences $a_0, a_1, \ldots, a_n$ for which $a_i \in \{1, 2, \ldots , n\}$ for all $i$ and $a_n = a_0$.

### Part (a)
Suppose $n$ is odd. We need to find the number of such sequences if $a_i - a_{i-1} \not\equiv i \pmod{n}$ for all $i = 1, 2, \ldots, n$.

Using the principle of inclusion-exclusion, we start by considering the number of ways to choose $k$ of the conditions to be disregarded. There are $\binom{n}{k}$ ways to choose $k$ conditions. Each condition synchronizes two neighboring entries in the sequence, resulting in $n-k$ groups of entries that move together. There are $n^{n-k}$ possibilities for these groups.

For $k = n$, we must have $1 + 2 + \dots + n = \frac{n(n+1)}{2} \equiv 0 \pmod{n}$, which is true for odd $n$. There are $n$ possibilities in this case.

Thus, the number of sequences is given by:
$$\sum_{k=0}^{n} (-1)^k \binom{n}{k} n^{n-k} - (n-1).$$

Using the binomial theorem, this simplifies to:
$$(n-1)^n - (n-1).$$

### Part (b)
Suppose $n$ is an odd prime. We need to find the number of such sequences if $a_i - a_{i-1} \not\equiv i, 2i \pmod{n}$ for all $i = 1, 2, \ldots, n$.

We extend the previous method by choosing $k$ places where we disregard the condition, but now we have two possibilities for each place. The condition for $i = n$ counts as one condition, so we need two terms for each $k$ to distinguish whether $i = n$ is involved or not.

For $k < n$, the sum is:
$$\sum_{k=0}^{n-1} \left( (-1)^k \binom{n-1}{k} 2^k n^{n-k} + (-1)^k \binom{n-1}{k-1} 2^{k-1} n^{n-k} \right).$$

This simplifies to:
$$n(n-2)^{n-1} - (n-2)^{n-1} = (n-1)(n-2)^{n-1}.$$

For $k = n$, we need to find the number of ways to choose $\epsilon_i \in \{1, 2\}$ such that $\sum_{i=1}^{n} \epsilon_i i \equiv 0 \pmod{n}$. Since $n$ is odd, this reduces to finding subsets $S$ of $\{1, 2, \ldots, n\}$ with $\sum_{x \in S} x \equiv 0 \pmod{n}$. This is true if $S$ contains all or none of the elements. For other sets, we consider shifts of $S$ by adding $i$ to each entry of $S$. Since $n$ is prime, the sequence of shifted sets has period $n$, and we get each residue mod $n$ exactly once.

Thus, there are $2 + \frac{2^n - 2}{n}$ such sets. Dividing by two (since $\epsilon_n$ is the same in both cases), we get:
$$\frac{2 + \frac{2^n - 2}{n}}{2} = 1 + \frac{2^{n-1} - 1}{n}.$$

Therefore, the number of sequences is:
$$(n-1)(n-2)^{n-1} - \left( 1 + \frac{2^{n-1} - 1}{n} \right).$$

The answer is:
$$\boxed{(n-1)(n-2)^{n-1} - \frac{2^{n-1} - 1}{n} - 1}.$$