China Girls' Mathematical Olympiad

(1) If $5\mid n$, let $d_1,d_2,\dots ,d_m$ be the elements in $S_n$ with their last digits equal to $3$, then $5d_1,5d_2,\dots ,5d_m$ are elements in $S_n$ with their last digits equal to $5$. So $m\le \frac{1}{2}|S_n|$. The statement is true in this case.

(2) If $5\nmid n$ and the last digit of every prime divisor of $n$ is either $1$ or $9$, the last digit of any element in $S_n$ is either $1$ or $9$. The statement is also true in this case.

(3) If $5\nmid n$ and there exists a prime divisor $p$ in $S_n$ such that the last digit of $p$ is either $3$ or $7$. Let $n=p^{r}q$, where $q$ and $r$ are positive integers and $p$ is prime to $q$, and let $S_q=\{a_1,a_2,\dots ,a_k\}$ be the set of all positive integer divisors of $q$. Then the elements in $S_n$ can be written in the following way:

For any $d_i=a_s{p}^l\in S_n$, we choose $e_i=$ then $e_i\in S_n$ and we call $e_i$ the partner of $d_i$. If the last digit of $d_i$ is $3$, then that of its partner $e_i$ is not, since that of $p$ is either $3$ or $7$. If $d_i$ and $d_j$ in $S_n$ are different, and their last digits are both $3$, then their partners $e_i$ and $e_j$ are also different. Otherwise, suppose $e_j=e_i=a_s{p}^l$, we may assume that $\{d_i,d_j\}=\{a_s{p}^{l-1},a_s{p}^{l+1}\}$, then $d_i=d_j{p}^2$. As the last digit of $p$ is $3$ or $7$, then that of $p^2$ is always $9$, and that means the last digits of $d_i$ and $d_j$ cannot be the same. It leads to a contradiction.

We then see that every $d_i\in S_n$ with its last digit equal to $3$ has a partner $e_i\in S_n$ with its last digit not equal to $3$, and different $d_i$ has different partner. That means that at most half of the elements in $S_n$ have their last digits equal to $3$. This completes the proof.