2003第2届CGMO试题

• 知识点

  >

  二试组合部分

略

考虑如下三种情况：（1）$n$ 能被 $5$ 整除，设 ${{d}_{1}}\text{,}{{d}_{2}}\text{,}\cdots {{d}_{m}}$ 为 ${{S}_{n}}$ 中所有个位数为 $3$ 的元素，则中还包括 $5{{d}_{1}}\text{,5}{{d}_{2}}\text{,}\cdots 5{{d}_{m}}$ 这 $m$ 个个位为 $5$ 的元素。所以 ${{S}_{n}}$ 中至多有一半元素的个位数为 $3$ 。（2）$n$ 不能被 $5$ 整除，且 $n$ 质因子的个位数均为 $1$ 或 $9$，则 ${{S}_{n}}$ 中所有元素的个位数均为 $1$ 或 $9$ 。结论成立。（3）$n$ 不能被 $5$ 整除，且 $n$ 有个位数 $3$ 或 $7$ 的质因子 $p$，令 $n\text{=}pq$，其中 $q\text{,}r$ 都是正整数，$p\text{,}q$ 互质。设 ${{S}_{q}}\text{=}\left\{{{a}_{1}}\text{,}{{a}_{2}}\text{,}\cdots \text{,}{{a}_{k}} \right\}$ 为 $q$ 的所有正约数组成的集合，将 ${{S}_{n}}$ 中的元素写成如下方阵：$\begin{matrix}
&{{a}_{1}}\text{,}{{a}_{1}}p\text{,}{{a}_{1}}{{p}^{2}}\text{,}\cdots{{a}_{1}}{{p}^{r}} \\
&{{a}_{2}}\text{,}{{a}_{2}}p\text{,}{{a}_{2}}{{p}^{2}}\text{,}\cdots{{a}_{2}}{{p}^{r}} \\
& \cdots\cdots \\
&{{a}_{k}}\text{,}{{a}_{k}}p\text{,}{{a}_{k}}{{p}^{2}}\text{,}\cdots{{a}_{k}}{{p}^{r}} \\
\end{matrix}$ 对于 ${{d}_{i}}\text{=}{{a}_{j}}{{p}^{l}}$，选择 ${{a}_{j}}{{p}^{l-1}}$ 或 ${{a}_{j}}{{p}^{l+1}}$ 之一与之配对（所选的数必须在 ${{S}_{n}}$ 中）。设 ${{e}_{i}}$ 为所选的数，我们称 $\left({{d}_{i}}\text{,}{{e}_{i}} \right)$ 为一对朋友 。如果 ${{d}_{i}}$ 的个位数都是 $3$，则由 $p$ 的个位数是 $3$ 或7知 ${{e}_{i}}$ 的个位数不是 $3$ 。 假设 ${{d}_{i}}$ 和 ${{d}_{j}}$ 的个位数都是 $3$，且有相同的朋友 $e\text{=}{{a}_{x}}{{p}^{i}}$，则 $\left\{{{d}_{i}}\text{,}{{d}_{j}} \right\}\text{=}\left\{{{a}_{x}}{{p}^{i-1}}\text{,}{{a}_{x}}{{p}^{i+1}} \right\}$ 。因为 $p$ 的个位数为 $3$ 或 $3$，从而 ${{p}^{2}}$ 的个位数为9。而 $n$ 不能被 $5$ 整除，故 ${{a}_{x}}$ 的个位数不为0。所以 ${{a}_{x}}{{p}^{i-1}}$ 和 ${{a}_{x}}{{p}^{i-1}}\cdot{{p}^{2}}={{a}_{x}}{{p}^{i+1}}$ 的个位数不同。这与 ${{d}_{i}}$ 和 ${{d}_{j}}$ 的个位数都是 $3$ 矛盾。因此每个个位数为 $3$ 的 ${{d}_{i}}$ 均有不同的朋友。 综上所述，${{S}_{n}}$ 中每个个位数为 $3$ 的元素，均与一个 ${{S}_{n}}$ 中个位数不为 $3$ 的元素为朋友，而且两个个位数为 $3$ 的不同元素的朋友也不相同。所以 ${{S}_{n}}$ 中至多有一半元素的个位数为 $3$ 。