International Mathematical Olympiad

Solution I

Lemma 1: If $k$ is a positive integer, then there exist $0\le a_1,a_2,\dots ,a_{2k}\le 9$ such that $a_1,a_3,\dots ,a_{2k-1}$ are odd integers, $a_2,a_4,\dots ,a_{2k}$ are even integers, and $$2^{2k+1}\mid \overline{a_1{a}_2\cdots a_{2k}}$$ Proof of Lemma 1 by mathematical induction. If $k=1$, it follows from $8\mid 16$ that the proposition is true. Assume that if $k=n-1$, the proposition is true. When $k=n$, let $\overline{a_1{a}_2\cdots a_{2n-2}}=2^{2n-1}t$ by the inductive hypothesis. The problem reduces to proving that there exist $1\le a,b\le 9$ with $a$ odd and $b$ even such that $2^{2n+1}\mid \overline{ab}\times 10^{2n-2}+2^{2n-1}t$, or $8\mid \overline{ab}\times 5^{2n-2}+2t$, or $8\mid \overline{ab}+2t$ in view of $5^{2n-2}\equiv 1(\mathrm{mod}8)$. It follows from $8|12+4$, $8|14+2$, $8|16+0$ and $8|50+6$ that Lemma 1 is true.

Lemma 2: If $k$ is a positive integer, then there exists an alternating number $\overline{a_1{a}_2\cdots a_{2k}}$ with an even number $2k$ of digits such that $a_{2k}$ is odd and $5^{2k}\mid \overline{a_1{a}_2\cdots a_{2k}}$, where $a_1$ can be 0, but $a_2\ne 0$. Proof of Lemma 2 by mathematical induction. If $k=1$, it follows from $25\mid 25$ that the proposition is true. Assume that if $k=n-1$, the proposition is true, or there exists an alternating multiple $\overline{a_1{a}_2\cdots a_{2n-2}}$ satisfying $5^{2n-2}\mid \overline{a_1{a}_2\cdots a_{2n-2}}$. When $k=n$, let $\overline{a_1{a}_2\cdots a_{2n-2}}=t\cdot 5^{2n-2}$. The problem reduces to proving that there exist $0\le a,b\le 9$ with $a$ even and $b$ odd such that $5^2\mid \overline{ab}\times 10^{2n-2}+t\cdot 5^{2n-2}$, or $25\mid \overline{ab}\times 2^{2n-2}+t$. Since $2^{2n-2}$ is coprime to 25, there exist $0<\overline{ab}\le 25$ such that $25\mid \overline{ab}\times 2^{2n-2}+t$. If $b$ is odd, between $\overline{ab}$ and $\overline{ab}+50$, at least one satisfies that the highest-valued digit is even. If $b$ is even, between $\overline{ab}+25$ and $\overline{ab}+75$, at least one satisfies that the highest-valued digit is even. This completes the proof of Lemma 2.

Let $n=2^{\alpha }{5}^{\beta }t$, where $t$ is coprime to 10 and $\alpha ,\beta \in \mathbb{N}$. Assume that $\alpha \ge 2$ and $\beta \ge 1$. Let $l$ be an arbitrary multiple of $n$. The last decimal digit is 0, and the digit in tens is even. Hence these $n$ do not satisfy the required condition.

① When $\alpha =\beta =0$, consider $21$, $2121$, $212121$, $\dots$, $2121\dots 21$, $\dots$. There must exist two of them congruent modulo $n$. Without loss of generality, we may assume that $t_1>t_2$, and $$\underset{\text{number }{t}_1\text{ of }21}{\underbrace{2121\cdots 21}}\equiv \underset{\text{number }{t}_2\text{ of }21}{\underbrace{2121\cdots 21}}(\mathrm{mod}n).$$ Then $$\underset{\text{number }{t}_1-t_2\text{ of }21}{\underbrace{2121\cdots 21}}\equiv \underset{\text{number }2t_2\text{ of }0}{\underbrace{00\cdots 0}}\equiv 0(\mathrm{mod}n)$$ Hence $$\underset{\text{number }{t}_1-t_2\text{ of }21}{\underbrace{2121\cdots 21}}\equiv 0(\mathrm{mod}n),$$ because $n$ is coprime to 10. Now these positive integers $n$ satisfy the required condition.

② When $\beta =0$ and $\alpha \ge 1$, it follows from Lemma 1 that there exists an alternating number $\overline{a_1{a}_2\cdots a_{2k}}$ satisfying $2^{\alpha }\mid \overline{a_1{a}_2\cdots a_{2k}}$. Consider $$\overline{a_1{a}_2\cdots a_{2k}},\overline{a_1{a}_2\cdots a_{2k}{a}_1{a}_2\cdots a_{2k}},\dots ,\overline{a_1{a}_2\cdots a_{2k}{a}_1{a}_2\cdots a_{2k}\cdots a_1{a}_2\cdots a_{2k}},\dots$$ There must exist two of them congruent modulo $t$. Without loss of generality, we may assume that $t_1>t_2$, and $$\overline{a_1{a}_2\cdots a_{2k}\cdots a_1{a}_2\cdots a_{2k}}\equiv \overline{a_1{a}_2\cdots a_{2k}\cdots a_1{a}_2\cdots a_{2k}}(\mathrm{mod}t)$$ Since $t$ is coprime to 10, $\overline{a_1{a}_2\cdots a_{2k}\cdots a_1{a}_2\cdots a_{2k}}\equiv 0(\mathrm{mod}t)$. Moreover, since $t$ is coprime to 2, $$2^{\alpha }t\mid \overline{a_1{a}_2\cdots a_{2k}\cdots a_1{a}_2\cdots a_{2k}},$$ which is alternating.

③ When $\alpha =0,\beta \ge 1$, it follows from Lemma 2 that there exists an alternating multiple $\overline{a_1{a}_2\cdots a_{2k}}$ satisfying $5^{\beta }\mid \overline{a_1{a}_2\cdots a_{2k}}$ with $a_{2k}$ odd. Using the same argument as in ②, we obtain that there exist $t_1>t_2$ satisfying $t\mid \overline{a_1{a}_2\cdots a_{2k}\cdots a_1{a}_2\cdots a_{2k}}$. Since $t$ is coprime to 5, $$5^{{\beta }_t}\mid \overline{a_1{a}_2\cdots a_{2k}\cdots a_1{a}_2\cdots a_{2k}}$$ In addition, $\overline{a_1{a}_2\cdots a_{2k}\cdots a_1{a}_2\cdots a_{2k}}$ is alternating, and the last decimal digit $a_{2k}$ is odd.

④ When $\alpha =1$ and $\beta \ge 1$, it follows from ③ that there exists an alternating number $\overline{a_1{a}_2\cdots a_{2k}\cdots a_1{a}_2\cdots a_{2k}}$ satisfying that $a_{2k}$ is odd and $5^{{\beta }_t}\mid \overline{a_1{a}_2\cdots a_{2k}\cdots a_1{a}_2\cdots a_{2k}}$. Hence $2\cdot 5^{{\beta }_t}\mid \overline{a_1{a}_2\cdots a_{2k}\cdots a_1{a}_2\cdots a_{2k}}$, which is alternating.

In conclusion, if $n$ is not divisible by 20, then these positive integers $n$ satisfy the required condition.

Solution II

$n$ should be the positive integers and should satisfy that $n$ is not divisible by 20.

(1) Assume that $20\mid n$. Select a multiple of $n$ arbitrarily. Denote $(a_k{a}_{k-1}\cdots a_1{)}_{10}$, where $a_k\ne 0$. We have $20\mid (a_k{a}_{k-1}\cdots a_1{)}_{10}$. Hence $a_1=0$, $2\mid (a_k{a}_{k-1}\cdots a_1{)}_{10}$. This implies that $a_2$ is even. Therefore, $(a_k{a}_{k-1}\cdots a_1{)}_{10}$ is not alternating.

(2) We will prove that if $n$ is a positive integer and is not divisible by 20, then $n$ must have a multiple which is alternating. We will show three lemmas as follows. Then we divide the proof into four cases.

Lemma 1: If the positive integer $n$ is coprime to 10, then for any $l\in \mathbb{N}$, there exists $k\in \mathbb{N}$ such that \frac{\begin{array}{c} 1 \ 00\cdots0 \\ \underline{\quad} \\ \mathbf{number} \ l \ \mathbf{of} \ 0 \end{array} \quad \begin{array}{c} 1 \ 00\cdots0 \\ \underline{\quad} \\ \mathbf{number} \ l \ \mathbf{of} \ 0 \end{array} \quad \begin{array}{c} 1 \cdots 1 \ 00\cdots0 \\ \underline{\quad} \\ \mathbf{number} \ l \ \mathbf{of} \ 0 \end{array} \quad \begin{array}{c} 1 \\ \underline{\quad} \\ \mathbf{total number} \ k \ \mathbf{of} \ 1 \end{array}} is a multiple of $n$. Proof of Lemma 1: Consider the numbers $x_1=1,x_2=1\underset{\text{number }l\text{ of }0}{\underbrace{00\cdots 0}},\dots ,$ $$x_m=1\underset{\text{number }l\text{ of }0}{\underbrace{00\cdots 0}}1\cdots 1\underset{\text{number }l\text{ of }0}{\underbrace{00\cdots 0}}1,\dots$$ There must exist two of them congruent modulo $n$. Without loss of generality, we may assume that $$x_s\equiv x_t(\text{mod }n),s>t\ge 1.$$ Then $n\mid x_s-x_t$. Moreover, since $x_s-x_t=x_{s-t}\cdot 10^{t(l+1)}$ and $n$ is coprime to $10$, $n\mid x_{s-t}$, $s-t>0$ and $x_{s-t}$ is a positive integer. This completes the proof of Lemma 1.

Lemma 2: For any $m\in \mathbb{N}$, there always exists an alternating number $s_m$ with $m$ digits such that its first digit can be 0, and its last decimal digit is 5, and $5^m\mid s_m$. Proof of Lemma 2 by inductive construction. Start with $s_1=5$. Suppose that $s_m=(a_m{a}_{m-1}\cdots a_1{)}_{10}$ is alternating, where $a_1=5$ and $a_m$ can be 0. In addition, $5^m\mid s_m$. Let $s_m=5^m$. Denote $$A=\{\begin{array}{ll}\{0,2,4,6,8\},& \text{when }{a}_m\text{ is odd,}\\ \{1,3,5,7,9\},& \text{when }{a}_m\text{ is even.}\end{array}$$ Any two of them in $A$ are not congruent modulo $5$, and $2^m$ is coprime to $5$. So any two of the numbers in $\{2^{m}x\mid x\in A\}$ are not congruent modulo $5$. Select $x\in A$ such that $2^{m}x=-l(\mathrm{mod}5)$. Then $5\mid 2^{m}x+l$. Let $s_{m+1}=(x{a}_m{a}_{m-1}\cdots a_1{)}_{10}$. Then $s_{m+1}$ is an alternating number with $m+1$ digits, where $a_1=5$, and its first digit can be 0. In addition, $s_{m+1}=x10^m+s_m=5^m(2^{m}x+l)$ is a multiple of $5^{m+1}$. This completes the proof of Lemma 2.

Lemma 3: For any integer $m\in \mathbb{N}$, there always exists an alternating number $t_m$ with $m$ digits such that its last decimal digit is 2, and $$2^{2k+1}\mid t_{2k+1},2^{2k+3}\mid t_{2k+2}.$$ Proof of Lemma 3 by inductive construction. Start with $t_1=2$. Suppose that $t_{2k+1}=(a_{2k+1}{a}_{2k}\cdots a_1{)}_{10}$ is alternating, where $a_1=2$, and $2^{2k+1}\mid t_{2k+1}$. It follows from the property of the alternating numbers that $a_{2k+1}=a_1=0(\mathrm{mod}2)$. Denote $A=\{1,3,5,7\}$. Any two of them in $A$ are not congruent modulo $8$, and $5^{2k+1}$ is coprime to $8$. So any two numbers of $\{5^{2k+1}x\mid x\in A\}$ are not congruent modulo $8$. Now divide the four numbers in $\{5^{2k+1}x\mid x\in A\}$ by $8$ respectively. The original sentence means the 4 numbers are divisible by 8. Since $5^{2k+1}x$ with $x\in A$ is odd, the remainders are 1, 3, 5, 7. Let $t_{2k+1}=2^{2k+1}l$ with $l$ odd. Select $x\in A$ such that $5^{2k+1}x\equiv -l+4(\mathrm{mod}8)$. Then $2^2\nmid 5^{2k+1}x+l$. Let $t_{2k+2}=(x{a}_{2k+1}\cdots a_1{)}_{10}$. Then $t_{2k+2}$ is alternating with $2k+2$ digits. In addition, $a_1=2$ and $t_{2k+2}=x10^{2k+1}+t_{2k+1}=2^{2k+1}(5^{2k+1}x+l)$. Since $2^2\nmid 5^{2k+1}x+l$, we have $2^{2k+3}\nmid t_{2k+2}$. Moreover, suppose that $t_{2k+2}=(a_{2k+2}\cdots a_1{)}_{10}$, where $a_1=2$, and $2^{2k+3}\nmid t_{2k+2}$. Let $t_{2k+3}=(4a_{2k+2}\cdots a_1{)}_{10}$. Then $t_{2k+3}$ is an alternating number with $2k+3$ digits, and $t_{2k+3}=5^{2k+2}{2}^{2k+4}+t_{2k+2}$. Since $2^{2k+3}\nmid t_{2k+2}$, we have $2^{2k+3}\nmid t_{2k+3}$. This completes the proof of Lemma 3.

Next, we discuss the four cases. (1) If $n$ is coprime to 10, it follows from Lemma 1 that there exists $k\in N^{\ast }$ such that $10101\cdots 101$ is a multiple of $n$. The conclusion is equivalent to selecting $l=1$ in Lemma 1. (2) If $n$ is not divisible by 5, and $n$ is divisible by 2, let $n=2^m{n}_0$ such that $n_0$ is not divisible by 2, then $n_0$ is coprime to 10. Select $m_0>m$ with $m_0$ even. It follows from Lemma 3 that there exists an alternating number $t_{m_0}=(a_{m_0}\cdots a_1{)}_{10}$ with $m_0$ digits, where $a_1=2$. In addition, $2^{m_0+1}\nmid t_{m_0}$. Hence $2^m\mid t_{m_0}$. It follows from Lemma 1 that there exists $k\in N^{\ast }$ such that $$P=t_{m_0}\cdot 1\underset{\begin{array}{c}\text{number }m,-1\text{ of }0\\ \text{number }k\text{ of }1\end{array}}{\underbrace{00\cdots 0}}\cdot 1\cdots 100\cdots 01$$ can be divisible by $2^m{n}_0$, or $n\mid P$. (3) If $n$ is divisible by 5, and $n$ is not divisible by 2, let $n=5^m{n}_0$ such that $n_0$ is not divisible by 5, then $n_0$ is coprime to 10. Select $m_0>m$ with $m_0$ even. It follows from Lemma 2 that there exist an alternating number $s_{m_0}=(a_{m_0}\cdots a_1{)}_{10}$ with $m_0$ digits, where $a_1=5$ and $a_{m_0}$ can be 0. In addition, $5^m\mid s_{m_0}$. Hence $5^m\mid s_{m_0}$. Using the same argument as (2), there exists an alternating number $P$ such that $5^m{n}_0\mid P$ and the last decimal digit $a_1=5$. (4) If $n$ is divisible by 10, and $n$ is not divisible by 20, let $n=10n_0$ with $n_0$ odd, then $n_0$ satisfies the assumption in case (1) or in case (3). It follows from (1) and (3) that there exists $(a_k\cdots a_1{)}_{10}$ an alternating multiple of $n_0$, where $a_1=1$ or 5. Now let $P=(a_k\cdots a_{1}0{)}_{10}$. Then $P$ is an alternating multiple of $n$.

In conclusion, $n$ should be a positive integer and should not be divisible by 20.