Kanada 2014

Let $S$ be the set of all sequences $(b_1,b_2,\dots ,b_p)$ of numbers from the set $\{0,1,2,\dots ,p-1\}$ such that $b_1+b_2+\cdots +b_p$ is not divisible by $p$. We show that $|S|=p^p-p^{p-1}$. For let $b_1,b_2,\dots ,b_{p-1}$ be an arbitrary sequence of numbers chosen from $\{0,1,2,\dots ,p-1\}$. There are exactly $p-1$ choices for $b_p$ such that $b_1+b_2+\cdots +b_{p-1}+b_p\not\equiv 0(\mathrm{mod}p)$, and therefore $|S|=p^{p-1}(p-1)=p^p-p^{p-1}$.

Now it will be shown that the number of good sequences in $S$ is $\frac{1}{p}|S|$. For a sequence $B=(b_1,b_2,\dots ,b_p)$ in $S$, define the sequence $B_k=(a_1,a_2,\dots ,a_p)$ by $$a_i=b_i-b_1+k\mathrm{mod}p$$ for $1\le i\le p$. Now note that $B$ in $S$ implies that $$a_1+a_2+\cdots +a_p\equiv (b_1+b_2+\cdots +b_p)-p{b}_1+pk\equiv (b_1+b_2+\cdots +b_p)\not\equiv 0(\mathrm{mod}p)$$ and therefore $B_k$ is in $S$ for all non-negative $k$. Now note that $B_k$ has first element $k$ for all $0\le k\le p-1$ and therefore the sequences $B_0,B_1,\dots ,B_{p-1}$ are distinct.

Now define the cycle of $B$ as the set $\{B_0,B_1,\dots ,B_{p-1}\}$. Note that $B$ is in its own cycle since $B=B_k$ where $k=b_1$. Now note that since every sequence in $S$ is in exactly one cycle, $S$ is the disjoint union of cycles. Now it will be shown that exactly one sequence per cycle is good. Consider an arbitrary cycle $B_0,B_1,\dots ,B_{p-1}$, and let $B_0=(b_1,b_2,\dots ,b_p)$ where $b_0=0$, and note that $B_k=(b_1+k,b_2+k,\dots ,b_p+k)$ mod $p$. Let $u=b_1+b_2+\cdots +b_p$, and $v=b_1{b}_2+b_2{b}_3+\cdots +b_p{b}_1$ and note that $(b_1+k)(b_2+k)+(b_2+k)(b_3+k)+\cdots +(b_p+k)(b_1+k)=u+2kv(\mathrm{mod}p)$ for all $0\le k\le p-1$. Since $2v$ is not divisible by $p$, there is exactly one value of $k$ with $0\le k\le p-1$ such that $p$ divides $u+2kv$ and it is exactly for this value of $k$ that $B_k$ is good. This shows that exactly one sequence per cycle is good and therefore that the number of good sequences in $S$ is $\frac{1}{p}|S|$, which is $p^{p-1}-p^{p-2}$.