设 $n$ 为正整数，$S$ 为 $\{1,2,\cdots ,n\}$ 中所有与 $n$ 互素的数构成的集合。记 ${{S}_{1}}=S\bigcap \left( 0,\frac{n}{3} \right]$，${{S}_{2}}=S\bigcap \left( \frac{n}{3},\frac{2n}{3} \right]$，${{S}_{3}}=S\bigcap \left( \frac{2n}{3},n \right]$ 。若集合 $S$ 的元素个数为3的倍数，证明：集合 ${{S}_{1}}$、${{S}_{2}}$、${{S}_{3}}$ 的元素个数相等。
【难度】
【出处】
2014第13届CGMO试题
【标注】
【答案】
略
【解析】
用 $\left| X \right|$ 表示有限集合 $X$ 的元素个数。
对每个正整数 $n$，定义 $A(n)$ 为所有与 $n$ 互素的整数构成的集合，并对每个整数 $k$，定义 ${{A}_{k}}(n)=A(n)\bigcap \left( \frac{k-1}{3}n,\frac{k}{3}n \right]$ 。则对任意整数 $x$ 均有 $(x,n)=1\Leftrightarrow (x+n,n)=1$
$x\in {{A}_{k}}(n)\Leftrightarrow x+n\in {{A}_{k+3}}(n)$，$\left| {{A}_{k}}(n) \right|=\left| {{A}_{k+3}}(n) \right|$
若正整数 $n$ 满足题目的结论，即 $\left|{{A}_{1}}(n) \right|=\left| {{A}_{2}}(n) \right|=\left| {{A}_{3}}(n) \right|$
这等价于对所有的整数 $k$，$\left| {{A}_{k}}(n)\right|$ 均相等，将满足这一性质的正整数 $n$ 称为“平衡的”。
先证明一个引理。
引理 若正整数 $n$ 为平衡的，则对任意素数 $p$，乘积 $pn$ 也为平衡的。
此时，由定义知对所有的整数 $k$，$\left|{{A}_{k}}(n) \right|$ 均相等，令其为 $m$
下面分两种情形考虑。
（1）若 $p\left| n \right.$，则 $(x,pn)=1\Leftrightarrow (x,n)=1$ 。从而，$A(pn)=A(n)$ 。
则 $\begin{align}
&{{A}_{1}}(pn)=A(pn)\bigcap \left( 0,\frac{1}{3}pn \right] \\
& =A(n)\bigcap\left( 0,\frac{p}{3}n \right] \\
&={{A}_{1}}(n)\bigcup {{A}_{2}}(n)\bigcup \cdots \bigcup {{A}_{p}}(n)
\end{align}$
$\begin{align}
&{{A}_{2}}(pn)=A(pn)\bigcap \left( \frac{1}{3}pn,\frac{2}{3}pn \right] \\
& =A(n)\bigcap\left( \frac{p}{3}n,\frac{2p}{3}n \right] \\
&={{A}_{p+1}}(n)\bigcup {{A}_{p+2}}(n)\bigcup \cdots \bigcup {{A}_{2p}}(n)
\end{align}$
$\begin{align}
&{{A}_{3}}(pn)=A(pn)\bigcap \left( \frac{2}{3}pn,pn \right] \\
& =A(n)\bigcap\left( \frac{2p}{3}n,\frac{3p}{3}n \right] \\
&={{A}_{2p+1}}(n)\bigcup {{A}_{2p+2}}(n)\bigcup \cdots \bigcup{{A}_{3p}}(n)
\end{align}$
故 $\left| {{A}_{1}}(pn) \right|=\left| {{A}_{2}}(pn)\right|=\left| {{A}_{3}}(pn) \right|=pm$，即 $pn$ 为平衡的。
（2）若 $pn$，则 $(x,pn)=1\Leftrightarrow(x,n)=1$，且 $(x,p)=1$
于是，$A(pn)=A(n)-B(n)$，其中
$B(n)=\left\{ x\left| x\in A(n),p\left| x \right. \right.\right\}=\left\{ x\left| x=py,y\in A(n) \right. \right\}$
由（1）中讨论，知 $A(n)$ 在区间 $\left( 0,\frac{1}{3}pn \right]$，$\left(\frac{1}{3}pn,\frac{2}{3}pn \right]$，$\left(\frac{2}{3}pn,pn \right]$ 上各有 $pm$ 个点。
集合 $B(n)$ 中的元素 $x=py\in \left(0,\frac{1}{3}pn \right]$ 对应 $A(n)$ 中的元素 $y\in \left( 0,\frac{1}{3}n \right]$，这样的数有 $\left|{{A}_{1}}(n) \right|=m$ 个。
于是，集合 $B(n)$ 在该区间中恰有 $m$ 个点。
同理，$B(n)$ 在另外两个区间中也恰有 $m$ 个点。
由于 $B(n)$ 为 $A(n)$ 的子集，故 $A(pn)=A(n)-B(n)$ 在三个区间上的点数均为 $pm-m$，即 $\left| {{A}_{1}}(pn) \right|=\left| {{A}_{2}}(pn) \right|=\left|{{A}_{3}}(pn) \right|=pm-m=(p-1)m$
所以，$pn$ 为平衡的。
从而，平衡数的任意素数倍均为平衡的。
反复使用引理，平衡数的任意正整数倍均为平衡的。
先假设 $S$ 的元素个数为3的倍数，将 $n$ 分解为 $n=p_{1}^{{{a}_{1}}}p_{2}^{{{a}_{2}}}\cdots p_{k}^{{{a}_{k}}}$
其中，${{p}_{1}},{{p}_{2}},\cdots ,{{p}_{k}}$ 为互不相同的素数，为正整数 ${{a}_{1}},{{a}_{2}},\cdots ,{{a}_{k}}$ 为正整数。
由 $3\left| \left| S \right|=\varphi (n)=({{p}_{1}}-1)\cdots({{p}_{k}}-1)p_{1}^{{{a}_{1}}-1}\cdots p_{k}^{{{a}_{k}}-1} \right.$ 得到 $n$ 为9的倍数或 $n$ 含有 $3k+1$ 型素因子 $p$ 。
简单验算知9和素数 $p=3k+1$ 均为平衡的。从而，正整数 $n$ 为平衡的。
对每个正整数 $n$，定义 $A(n)$ 为所有与 $n$ 互素的整数构成的集合，并对每个整数 $k$，定义 ${{A}_{k}}(n)=A(n)\bigcap \left( \frac{k-1}{3}n,\frac{k}{3}n \right]$ 。则对任意整数 $x$ 均有 $(x,n)=1\Leftrightarrow (x+n,n)=1$
$x\in {{A}_{k}}(n)\Leftrightarrow x+n\in {{A}_{k+3}}(n)$，$\left| {{A}_{k}}(n) \right|=\left| {{A}_{k+3}}(n) \right|$
若正整数 $n$ 满足题目的结论，即 $\left|{{A}_{1}}(n) \right|=\left| {{A}_{2}}(n) \right|=\left| {{A}_{3}}(n) \right|$
这等价于对所有的整数 $k$，$\left| {{A}_{k}}(n)\right|$ 均相等，将满足这一性质的正整数 $n$ 称为“平衡的”。
先证明一个引理。
引理 若正整数 $n$ 为平衡的，则对任意素数 $p$，乘积 $pn$ 也为平衡的。
此时，由定义知对所有的整数 $k$，$\left|{{A}_{k}}(n) \right|$ 均相等，令其为 $m$
下面分两种情形考虑。
（1）若 $p\left| n \right.$，则 $(x,pn)=1\Leftrightarrow (x,n)=1$ 。从而，$A(pn)=A(n)$ 。
则 $\begin{align}
&{{A}_{1}}(pn)=A(pn)\bigcap \left( 0,\frac{1}{3}pn \right] \\
& =A(n)\bigcap\left( 0,\frac{p}{3}n \right] \\
&={{A}_{1}}(n)\bigcup {{A}_{2}}(n)\bigcup \cdots \bigcup {{A}_{p}}(n)
\end{align}$
$\begin{align}
&{{A}_{2}}(pn)=A(pn)\bigcap \left( \frac{1}{3}pn,\frac{2}{3}pn \right] \\
& =A(n)\bigcap\left( \frac{p}{3}n,\frac{2p}{3}n \right] \\
&={{A}_{p+1}}(n)\bigcup {{A}_{p+2}}(n)\bigcup \cdots \bigcup {{A}_{2p}}(n)
\end{align}$
$\begin{align}
&{{A}_{3}}(pn)=A(pn)\bigcap \left( \frac{2}{3}pn,pn \right] \\
& =A(n)\bigcap\left( \frac{2p}{3}n,\frac{3p}{3}n \right] \\
&={{A}_{2p+1}}(n)\bigcup {{A}_{2p+2}}(n)\bigcup \cdots \bigcup{{A}_{3p}}(n)
\end{align}$
故 $\left| {{A}_{1}}(pn) \right|=\left| {{A}_{2}}(pn)\right|=\left| {{A}_{3}}(pn) \right|=pm$，即 $pn$ 为平衡的。
（2）若 $pn$，则 $(x,pn)=1\Leftrightarrow(x,n)=1$，且 $(x,p)=1$
于是，$A(pn)=A(n)-B(n)$，其中
$B(n)=\left\{ x\left| x\in A(n),p\left| x \right. \right.\right\}=\left\{ x\left| x=py,y\in A(n) \right. \right\}$
由（1）中讨论，知 $A(n)$ 在区间 $\left( 0,\frac{1}{3}pn \right]$，$\left(\frac{1}{3}pn,\frac{2}{3}pn \right]$，$\left(\frac{2}{3}pn,pn \right]$ 上各有 $pm$ 个点。
集合 $B(n)$ 中的元素 $x=py\in \left(0,\frac{1}{3}pn \right]$ 对应 $A(n)$ 中的元素 $y\in \left( 0,\frac{1}{3}n \right]$，这样的数有 $\left|{{A}_{1}}(n) \right|=m$ 个。
于是，集合 $B(n)$ 在该区间中恰有 $m$ 个点。
同理，$B(n)$ 在另外两个区间中也恰有 $m$ 个点。
由于 $B(n)$ 为 $A(n)$ 的子集，故 $A(pn)=A(n)-B(n)$ 在三个区间上的点数均为 $pm-m$，即 $\left| {{A}_{1}}(pn) \right|=\left| {{A}_{2}}(pn) \right|=\left|{{A}_{3}}(pn) \right|=pm-m=(p-1)m$
所以，$pn$ 为平衡的。
从而，平衡数的任意素数倍均为平衡的。
反复使用引理，平衡数的任意正整数倍均为平衡的。
先假设 $S$ 的元素个数为3的倍数，将 $n$ 分解为 $n=p_{1}^{{{a}_{1}}}p_{2}^{{{a}_{2}}}\cdots p_{k}^{{{a}_{k}}}$
其中，${{p}_{1}},{{p}_{2}},\cdots ,{{p}_{k}}$ 为互不相同的素数，为正整数 ${{a}_{1}},{{a}_{2}},\cdots ,{{a}_{k}}$ 为正整数。
由 $3\left| \left| S \right|=\varphi (n)=({{p}_{1}}-1)\cdots({{p}_{k}}-1)p_{1}^{{{a}_{1}}-1}\cdots p_{k}^{{{a}_{k}}-1} \right.$ 得到 $n$ 为9的倍数或 $n$ 含有 $3k+1$ 型素因子 $p$ 。
简单验算知9和素数 $p=3k+1$ 均为平衡的。从而，正整数 $n$ 为平衡的。
答案
解析
备注
