2004 IMO Problems/Problem 6

Problem

We call a positive integer alternating if every two consecutive digits in its decimal representation are of different parity. Find all positive integers $n$ which have an alternating multiple.

Solution

We claim that all positive integers $n$ except multiples of $20$ have a multiple that is alternating. If $n$ is a multiple of $20$ , then the units digit is $0$ and the tens digit is a multiple of $2$ , so both digits are even. Now, we will prove that if $20\nmid n$ , then there is a multiple of $n$ that is alternating.

We claim that there exists a $2k$ digit alternating integer that is a multiple of $2^{2k+1}$ and there exists an alternating integer with at most $k$ digits that is a multiple of $2\cdot5^k$ . We will prove this by induction.

Base Case: $k=1$ We can let the number be $16$ .

Inductive Step: Let $a$ be a $2k-2$ digit alternating number such that $2^{2k-1}\mid a$ . Since $a$ is even, this means that the first digit of $a$ is odd. Let $b\cdot2^{2k-1}\equiv a\pmod{2^{2k+1}}$ , where $b\in\{0,1,2,3\}$ . Let $x=16-2b$ . We see that $x$ is alternating, so the number $x\cdot10^{2k-2}+a$ is also alternating. We also have $x\equiv-2b\pmod8$ . Since $a\equiv b\cdot2^{2k-1}\pmod{2^{2k+1}}$ , this means that we have \begin{align*} x\cdot10^{2k-2}+a&\equiv x\cdot10^{2k-2}+b\cdot2^{2k-1}\pmod{2^{2k+1}}\\ &\equiv2^{2k-2}\left(x\cdot5^{2k-2}+2b\right)\pmod{2^{2k+1}}\\ &\equiv2^{2k-2}\left(-2b\cdot5^{2k-2}+2b\right)\pmod{2^{2k+1}}\\ &\equiv -b\cdot2^{2k-1}\left(5^{2k-2}-1\right)\pmod{2^{2k+1}}.\end{align*} Since $4\mid5^{2k-2}-1$ , this means that $x\cdot10^{2k-2}+a\equiv0\pmod{2^{2k+1}}$ , so $x\cdot10^{2k-2}+a$ is a $2k$ digit alternating number that is a multiple of $2^{2k+1}$ .

Now, we will prove that there exists an alternating integer with at most $k$ digits that is a multiple of $2\cdot5^k$ .

Base Case: $k=1$ We can let the number be $0$ .

Inductive Step: Let $a$ be a $k-1$ digit alternating number such that $2\cdot5^{k-1}\mid a$ . Let $S$ be the set of digits such that $x\cdot10^{k-1}+a$ is alternating. We see that either $S=\{0,2,4,6,8\}$ or $S=\{1,3,5,7,9\}$ . In each possible set, each $\mod5$ residue appears exactly once. Let $a=2\cdot5^{k-1}\cdot b$ . Then, $x\cdot10^{k-1}+a=2\cdot5^{k-1}\left(x\cdot2^{k-2}+b\right)$ . Therefore, there exists an $x$ such that $2\cdot5^k\mid x\cdot10^{k-1}+a$ , so there exists an alternating integer with at most $k$ digits that is a multiple of $2\cdot5^k$ . If $k$ is even, then $0\not\in S$ , so it has exactly $k$ digits.

Now, let $n=2^a\cdot5^b\cdot m$ . Then, if $20\nmid n$ , then $a<2$ or $b=0$ . If $b=0$ , then there exists a $2a$ digit alternating integer $x$ that is a multiple of $2^{2a+1}$ . Consider the sequence $a_i=x\cdot\frac{10^{2ai}-1}{10^{2a}-1}$ . Then, the decimal representation of $a_i$ is the result when $x$ is written $i$ times. For any prime $p$ that divides $n$ , if $p\mid10^{2a}-1$ , then $\nu_p\left(10^{2ai}-1\right)=\nu_p\left(10^{2a}-1\right)+\nu_p(i)$ , so $\nu_p(a_i)=\nu_p(x)+\nu_p(i)\geq\nu_p(i)$ . Therefore, there exists an $i$ such that $p^{\nu_p(n)}\mid a_{ci}$ for all $c$ . If $p\nmid10^{2a}-1$ , then if $i=\phi(n)$ , then $p^{\nu_p(n)}\mid10^{2ai}-1$ if $p\neq2,5$ . Since $5\nmid n$ , this means that we only need to make sure $2^a\mid x\cdot\frac{10^{2ai}-1}{10^{2a}-1}$ . Since $2^{2a+1}\mid x$ , this means that this is true, so if $5\nmid n$ , then there exists a multiple of $n$ that is alternating.

If $a<2$ , then there exists an alternating integer $x$ with exactly $2b$ digits that is a multiple of $2\cdot5^{2b}$ . Then, the first digit of $x$ is odd. Let $a_i=x\cdot\frac{10^{2bi}-1}{10^{2b}-1}$ . Then, if $p\mid10^{2b}-1$ , then $\nu_p(a_i)\geq\nu_p(i)$ , so there exists an $i$ such that $p^{\nu_p(n)}\mid a_i$ . If $p\nmid10^{2a}-1$ , then we can let $i=\phi(n)$ , so $p^{\nu_p(n)}\mid a_i$ . If $p=5$ , then $5^b\mid5^{2b}\mid x$ , and if $p=2$ , then $a=0,1$ , so $p^a\mid x$ . Therefore, $n\mid a_i$ for some $i$ .

Therefore, all positive integers except multiples of $20$ have an alternating multiple.

2004 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Problem
All IMO Problems and Solutions

Page

Toolbox

Search

2004 IMO Problems/Problem 6

Problem

Solution

See Also