设 $n$ 是正整数，$X$ 是有限集合，映射 $f : X \rightarrow X$ 满足 $f^{(n)}(x)=x$，对任意 $x \in X$，其中 $f^{1}(x)=f(x), f^{(i)}(x)=f\left(f^{(i-1)}(x)\right),i\geqslant 2$．记 $m_j$ 为集合 $\left\{x \in X | f^{{j}}(x)=x\right\}$ 的元素个数．对于任意整数 $k$，证明：
（1）$\displaystyle \dfrac{1}{n} \sum\limits_{j=1}^{n} m_{j} \sin \dfrac{2 j k \pi}{n}=0$；
（2）$\displaystyle \dfrac{1}{n} \sum\limits_{j=1}^{n} m_{j} \cos \dfrac{2 j k \pi}{n}$ 是非负整数．
（1）$\displaystyle \dfrac{1}{n} \sum\limits_{j=1}^{n} m_{j} \sin \dfrac{2 j k \pi}{n}=0$；
（2）$\displaystyle \dfrac{1}{n} \sum\limits_{j=1}^{n} m_{j} \cos \dfrac{2 j k \pi}{n}$ 是非负整数．
【难度】
【出处】
2017第16届CGMO试题
【标注】
【答案】
略
【解析】
以 $X$ 中的元素为顶点，按如下方式构造有向图 $G$：对于 $x,y \in X$，当且仅当 $f(x)= y$ 时，连一条从 $x$ 指向 $y$ 的有向边．注意到，对于 $f$ 的不动点 $x$，图 $G$ 中有一条从 $x$ 指向自身的环边，称之为长度为 $1$ 的轨道．由条件 $f^{(n)}(x)= x$，对任意 $x\in X$，可知 $f$ 是双射．这样，删去 $f$ 的所有不动点及对应的环边 之后，剩下的图中每个点的出度和入度都是 $1$．由图论中熟知的结论可得，剩 下的图可以分拆成若干个不相交的有向圈的并．我们把每个这样的有向圈称 之为一个轨道．对于一个长度为 $l$ 的轨道 $L$，对轨道上的任何顶点 $x$，易知 $ f^{(j)}(x)= x$ 的充分必要条件是 $l| j$．特别地，$l$ 是 $ n $ 的因数，且 $ L $ 中的顶点是 $ f^{(j)} $ 的不动点的充分必要条件是 $ l| j$．
设图 $G$ 中共有 $p$ 个轨道（包括那些长度为 $1$ 的轨道），长度分别为 $l_1,\cdots,l_p$．由前述，对正整数 $j$，有 $\displaystyle m
_j=\sum\limits_{1\leqslant t\leqslant p,l_t|j}l_t$．
利用这些关系式，通过适当的交换求和次序，可得
$\dfrac{1}{n}\sum_{j=1}^nm_je^{\frac{2jk\pi i}{n}}=\dfrac{1}{n}\sum_{j=1}^ne^{\frac{2jk\pi i}{n}}\sum_{l_t|j}l_t=\dfrac{1}{n}\sum_{t=1}^pl_t\sum_{1\leqslant j\leqslant n,l_t|j}e^{\frac{2jk\pi i}{n}}=\dfrac{1}{n}\sum_{t=1}^pl_t\sum_{q=1}^{n/l_t}e^{\frac{2kq\pi i}{n/l_t}}=\dfrac{1}{n}\sum_{\frac{n}{(n,k)}|l_t}l_t\cdot\dfrac{n}{l_t}=\sum_{\frac{n}{(n,k)}|l_t}1 ① $
其中倒数第二个等式用到了熟知的结果
$\sum_{q=1}^{n/l_t}e^{\frac{2kq\pi i}{n/l_t}}=\begin{cases}
\dfrac{n}{l_t},如果 \dfrac{n}{(n,k)}|l_t\\
0,其他情形\\
\end{cases} $
分别考虑 ① 式的虚部和实部，即得到原题中所要证明的两个结论．
设图 $G$ 中共有 $p$ 个轨道（包括那些长度为 $1$ 的轨道），长度分别为 $l_1,\cdots,l_p$．由前述，对正整数 $j$，有 $\displaystyle m
_j=\sum\limits_{1\leqslant t\leqslant p,l_t|j}l_t$．
利用这些关系式，通过适当的交换求和次序，可得
$\dfrac{1}{n}\sum_{j=1}^nm_je^{\frac{2jk\pi i}{n}}=\dfrac{1}{n}\sum_{j=1}^ne^{\frac{2jk\pi i}{n}}\sum_{l_t|j}l_t=\dfrac{1}{n}\sum_{t=1}^pl_t\sum_{1\leqslant j\leqslant n,l_t|j}e^{\frac{2jk\pi i}{n}}=\dfrac{1}{n}\sum_{t=1}^pl_t\sum_{q=1}^{n/l_t}e^{\frac{2kq\pi i}{n/l_t}}=\dfrac{1}{n}\sum_{\frac{n}{(n,k)}|l_t}l_t\cdot\dfrac{n}{l_t}=\sum_{\frac{n}{(n,k)}|l_t}1 ① $
其中倒数第二个等式用到了熟知的结果
$\sum_{q=1}^{n/l_t}e^{\frac{2kq\pi i}{n/l_t}}=\begin{cases}
\dfrac{n}{l_t},如果 \dfrac{n}{(n,k)}|l_t\\
0,其他情形\\
\end{cases} $
分别考虑 ① 式的虚部和实部，即得到原题中所要证明的两个结论．
答案
解析
备注
