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 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.
See Also
2004 IMO (Problems) • Resources | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Last Problem |
All IMO Problems and Solutions |