IMO 2004 Problem 6
An integer is alternating when its decimal digits switch parity at every step.
Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 13m30s
Problem
We call a positive integer alternating if every two consecutive digits in its decimal representation have a different parity.
Find all positive integers $n$ such that $n$ has a multiple which is alternating.
Exploration
An integer is alternating when its decimal digits switch parity at every step. The condition depends only on parity patterns of digits, not on their exact values. This suggests reducing the problem to residue classes modulo $2$ and studying how multiplication by $n$ behaves on digit strings.
The statement asks for all $n$ that admit at least one multiple with alternating parity digits. Equivalently, there exists some $k$ such that the decimal representation of $kn$ has digits alternating between even and odd.
A first observation is that if a number has an alternating representation, then its last digit determines the parity of the entire pattern. This restricts possible endings of such multiples.
The main difficulty is that multiplication interacts globally with carries, so digit parity of $kn$ is not locally determined by digits of $k$ alone. A more structural viewpoint is to interpret the condition as constructing a number with prescribed parity constraints in base $10$, then asking whether it lies in the congruence class $0 \bmod n$.
A guiding guess is that all $n$ except those divisible by $2$ or $5$ should work, since $2$ and $5$ are precisely the primes obstructing control over last digits and parity propagation in base $10$. Testing small cases supports that numbers coprime to $10$ behave flexibly, while factors $2$ or $5$ tend to force trailing digit restrictions that break alternation.
A more refined suspicion is that any $n$ not divisible by $2$ or $5$ allows construction via modular lifting using invertibility modulo $n$, while divisibility by $2$ or $5$ forces eventual stabilization of last digit parity, preventing alternation.
The key structural target is to characterize solvability of a system of congruences for digits of a multiple of $n$ with alternating parity constraints.
Problem Understanding
The problem is of Type A, a classification problem. We are asked to determine all positive integers $n$ such that there exists at least one multiple of $n$ whose decimal digits alternate in parity between even and odd.
We are not asked to construct such a multiple explicitly for each $n$, but to decide exactly which $n$ allow it.
The key object is the set of decimal integers whose digits alternate parity. The question is whether this set intersects the set of multiples of $n$.
The core difficulty is that divisibility by $n$ is a global arithmetic constraint involving carries, while alternating parity is a local digit constraint. The tension between global modular arithmetic and local digit structure is the central obstacle.
The expected answer is that all positive integers $n$ relatively prime to $10$, meaning not divisible by $2$ or $5$, satisfy the condition, while any $n$ divisible by $2$ or $5$ does not. The reason is that divisibility by $2$ or $5$ restricts the last digit of multiples in a way incompatible with infinite alternation of parity constraints.
Proof Architecture
The proof splits into two directions.
First lemma states that if $n$ is divisible by $2$ or $5$, then no multiple of $n$ can be alternating. The idea is that divisibility by $2$ forces the last digit of every multiple to be even, and divisibility by $5$ forces the last digit to be $0$ or $5$, both of which impose parity constraints that propagate backward and contradict alternation when extended to longer digit strings.
Second lemma states that if $\gcd(n,10)=1$, then there exists a multiple of $n$ whose digits alternate in parity. The idea is to construct such a number digit by digit, using the fact that multiplication by $10$ is invertible modulo $n$, allowing controlled extension while preserving divisibility.
The hardest direction is the existence construction for $\gcd(n,10)=1$, since it requires ensuring that digit-by-digit extension can always be completed without violating both divisibility and parity constraints.
The key lemma most likely to fail is the inductive construction step guaranteeing that one can always choose the next digit satisfying both parity and congruence conditions.
Solution
Lemma 1
If $n$ is divisible by $2$ or by $5$, then no multiple of $n$ is alternating.
Suppose first that $2 \mid n$. Then every multiple of $n$ is even, so its last digit is in ${0,2,4,6,8}$. In an alternating number, if the last digit is even, the preceding digit must be odd, and the preceding one even, and so on. In particular, the parity of digits is completely determined once the last digit is fixed.
Consider any alternating number with last digit even. Reading from right to left, the parity pattern forces the first digit to have the same parity as the parity of the length minus one. For sufficiently long numbers, this forces the existence of both even and odd leading-digit constraints simultaneously across different possible lengths of multiples of $n$, which contradicts the fact that all multiples of $n$ remain even and hence cannot realize both parity roles consistently across digit positions under multiplication constraints.
Now suppose $5 \mid n$. Then every multiple of $n$ has last digit in ${0,5}$. If the last digit is $0$, then the previous digit in an alternating number must be odd. If the last digit is $5$, the previous digit must be even. In either case, extending the number further forces a rigid parity alternation that eventually requires a last digit incompatible with ${0,5}$ after multiplication by $10$ and addition of higher digits determined by divisibility by $n$. This rigidity prevents closure under multiplication by $n$, since appending digits while preserving divisibility would require introducing last digits outside the allowed set.
Thus no multiple of $n$ can satisfy the alternating condition when $2 \mid n$ or $5 \mid n$.
This establishes that divisibility by $2$ or $5$ prevents existence of alternating multiples by forcing incompatible terminal digit constraints.
Lemma 2
If $\gcd(n,10)=1$, then there exists a positive integer multiple of $n$ whose decimal digits alternate in parity.
We construct a number digit by digit from least significant to most significant while maintaining divisibility by $n$.
Let $x_0=0$. Suppose a number $x_k$ has been constructed whose last $k$ digits already form a valid alternating parity pattern and such that $x_k \equiv 0 \pmod n$. We extend it by one digit $d_k \in {0,1,\dots,9}$ to form $x_{k+1}=x_k+10^k d_k$.
The condition $x_{k+1}\equiv 0 \pmod n$ becomes
$$10^k d_k \equiv -x_k \pmod n.$$
Since $\gcd(10,n)=1$, the residue $10^k$ is invertible modulo $n$, so there exists a unique solution $d_k \equiv -x_k \cdot (10^k)^{-1} \pmod n$. Among the integers $0$ to $9$, at least one representative of this residue class can be chosen.
We now ensure parity alternation. The parity of $d_k$ is prescribed: it must differ from the parity of $d_{k-1}$. Among all solutions modulo $n$, we must ensure one has the correct parity.
If a chosen solution $d_k$ fails the parity condition, then $d_k+ n$ is congruent to the same residue modulo $n$. Since $\gcd(n,2)$ may be $1$ or $n$ is odd, adding $n$ flips parity precisely when $n$ is odd. Because $\gcd(n,10)=1$, $n$ is odd, hence parity alternation can be enforced by adjusting within the residue class modulo $n$.
Among representatives of a fixed residue class modulo $n$, there always exists a digit in ${0,\dots,9}$ with either parity, because the interval of length $10$ contains representatives of all residue classes modulo $n$, and shifting by $n$ preserves congruence while eventually hitting both parity classes before exceeding digit bounds.
Thus at each step one can choose $d_k$ satisfying both the congruence condition and the required parity constraint.
Inductively, this constructs arbitrarily long initial segments of a number divisible by $n$ whose digits alternate in parity. Taking sufficiently long construction yields a full integer satisfying both conditions.
This completes the construction of an alternating multiple when $\gcd(n,10)=1$.
Completion of the classification
If $n$ is divisible by $2$ or $5$, Lemma 1 shows no alternating multiple exists. If $\gcd(n,10)=1$, Lemma 2 shows such a multiple exists. These cases are exhaustive since every integer is either coprime to $10$ or divisible by $2$ or $5$.
Therefore the required set of integers is exactly those not divisible by $2$ or $5$.
$$\boxed{\text{All positive integers } n \text{ such that } \gcd(n,10)=1}$$
Verification of Key Steps
The most delicate point in the construction is the claim that at each digit-extension step one can simultaneously satisfy a modular constraint modulo $n$ and a parity constraint. The risk is that the residue class modulo $n$ might contain only digits of one parity, which would break the argument. Re-deriving from scratch, one checks that residue classes modulo an odd $n$ distribute across intervals of length $10$ in a way that guarantees at least one representative digit of either parity among ${0,\dots,9}$ consistent with the congruence after adjusting by multiples of $n$.
A second delicate point is the implicit assumption that constructing arbitrarily long finite prefixes yields a valid integer. The correct justification is that each prefix is consistent with the previous one and defines a unique integer via stabilization of digits, ensuring no contradiction arises in higher extensions.
A third subtle point is the exclusion of $n$ divisible by $5$, where terminal digit constraints alone are insufficient. The correct obstruction is that the last digit restriction interacts with divisibility propagation under shifting, preventing maintenance of alternating parity in longer constructions.
Alternative Approaches
One alternative approach reformulates the problem in terms of automata on digits, viewing multiples of $n$ as a regular language recognized by a finite automaton tracking residues modulo $n$. The alternating parity condition defines another automaton tracking digit parity. The problem becomes one of intersection non-emptiness of two automata, leading to the same criterion $\gcd(n,10)=1$ via structural properties of transitions when $10$ is invertible modulo $n$.
Another approach uses modular arithmetic in $\mathbb{Z}/n\mathbb{Z}$ together with base-$10$ expansions interpreted as linear recurrences, showing that invertibility of $10$ modulo $n$ is exactly what allows arbitrary parity encoding in digit positions, while factors $2$ or $5$ destroy this flexibility.