# 2004 IMO Problems/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 which have an alternating multiple.

## Solution

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

We claim that there exists a digit alternating integer that is a multiple of and there exists an alternating integer with at most digits that is a multiple of . We will prove this by induction.

Base Case: We can let the number be .

Inductive Step: Let be a digit alternating number such that . Since is even, this means that the first digit of is odd. Let , where . Let . We see that is alternating, so the number is also alternating. We also have . Since , 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 , this means that , so is a digit alternating number that is a multiple of .

Now, we will prove that there exists an alternating integer with at most digits that is a multiple of .

Base Case: We can let the number be .

Inductive Step: Let be a digit alternating number such that . Let be the set of digits such that is alternating. We see that either or . In each possible set, each residue appears exactly once. Let . Then, . Therefore, there exists an such that , so there exists an alternating integer with at most digits that is a multiple of . If is even, then , so it has exactly digits.

Now, let . Then, if , then or . If , then there exists a digit alternating integer that is a multiple of . Consider the sequence . Then, the decimal representation of is the result when is written times. For any prime that divides , if , then , so . Therefore, there exists an such that for all . If , then if , then if . Since , this means that we only need to make sure . Since , this means that this is true, so if , then there exists a multiple of that is alternating.

If , then there exists an alternating integer with exactly digits that is a multiple of . Then, the first digit of is odd. Let . Then, if , then , so there exists an such that . If , then we can let , so . If , then , and if , then , so . Therefore, for some .

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