IMO 2004 · Problem 6

We call a positive integer alternating if every two consecutive digits in its decimal representation are of different parity.
Find all positive integers \(n\) such that \(n\) has a multiple which is alternating.

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{\text{All positive integers }n\text{ such that }20\nmid n.} \]

Solution

If \(20\mid n\), every multiple of \(n\) ends in \(00,20,40,60\), or \(80\). Its last two digits are both even, so it cannot be alternating. We prove that this is the only obstruction.

We first construct suitable alternating multiples of powers of \(2\) and \(5\). Let \[ C=\{5,6,7,8,9,\ 15,16,17,18,19,\ 25,26,27,28,29,\ 35,36,37,38,39,\ 45,46,47,48,49\}. \] For every \(c\in C\), the integer \(2c\) is a two-digit number with an odd tens digit and an even units digit. Consequently, any concatenation of such two-digit blocks is alternating.

The set \(C\) contains representatives of every residue modulo \(4\), since it contains \(5,6,7,8\). It also contains every residue modulo \(25\): its five displayed groups reduce, respectively, to \[ 5,\ldots,9;\quad15,\ldots,19;\quad0,\ldots,4;\quad 10,\ldots,14;\quad20,\ldots,24. \]

Fix \(q\in\{4,25\}\). We claim that for every \(k\ge0\), we can choose \(c_0,\ldots,c_{k-1}\in C\) such that \[ S_k=\sum_{i=0}^{k-1}c_i100^i \qquad\text{satisfies}\qquad q^k\mid S_k. \] For \(k=0\), take \(S_0=0\). Suppose \(S_k=q^ku\) has been constructed. Then \[ S_{k+1}=S_k+c_k100^k =q^k\left(u+c_k(100/q)^k\right). \] Since \(\gcd(100/q,q)=1\), and \(C\) represents every residue modulo \(q\), we can choose \(c_k\in C\) so that the expression in parentheses is divisible by \(q\). This proves the claim by induction.

For \(k\ge1\), the number \(2S_k\) is precisely the concatenation of the blocks \[ 2c_{k-1},\,2c_{k-2},\,\ldots,\,2c_0, \] because every block lies between \(10\) and \(98\), so there are no carries between blocks. Thus it is alternating, has \(2k\) digits, begins with an odd digit, and ends with an even digit. Taking \(q=4\) and \(q=25\), respectively, gives such numbers divisible by \[ 2^{2k+1} \qquad\text{and}\qquad 2\cdot5^{2k}. \]

Now let \(20\nmid n\), and write \[ n=2^a5^b m,\qquad a,b\ge0,\qquad \gcd(m,10)=1. \] If \(b=0\), choose \(k\ge1\) with \(2k+1\ge a\) and use the construction for \(q=4\). If \(b>0\), the condition \(20\nmid n\) implies \(a\le1\); choose \(k\ge1\) with \(2k\ge b\) and use the construction for \(q=25\).

In either case, we obtain an alternating number \(A\) of even length \(L\), beginning with an odd digit and ending with an even digit, such that \[ 2^a5^b\mid A. \]

Put \(B=10^L\), and define \[ R_0=0,\qquad R_j=1+B+\cdots+B^{j-1}\quad(j\ge1). \] Among \(R_0,R_1,\ldots,R_m\), two have the same remainder modulo \(m\). For some \(0\le i<j\le m\), therefore, \[ m\mid R_j-R_i=B^iR_{j-i}. \] As \(\gcd(B,m)=1\), it follows that \(m\mid R_{j-i}\).

Finally, \(AR_{j-i}\) is the decimal concatenation of \(j-i\) copies of \(A\). It is alternating, including at every junction, since each copy ends with an even digit and the next begins with an odd digit. Moreover, \[ 2^a5^b m=n\mid AR_{j-i}. \] Thus every positive integer not divisible by \(20\) has an alternating multiple.

The solution was checked against Evan Chen's published IMO solution notes.