Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2004 IMO Problems/Problem 6"

(Created page with "We call a positive integer alternating if every two consecutive digits in its decimal representation are of different parity. Find all positive integers <math>n</math> which h...")
 
Line 2: Line 2:
 
representation are of different parity. Find all positive integers <math>n</math> which have an
 
representation are of different parity. Find all positive integers <math>n</math> which have an
 
alternating multiple.
 
alternating multiple.
 +
 +
==Solution==
 +
 +
We claim that all positive integers <math>n</math> except multiples of <math>20</math> have a multiple that is alternating. If <math>n</math> is a multiple of <math>20</math>, then the units digit is <math>0</math> and the tens digit is a multiple of <math>2</math>, so both digits are even. Now, we will prove that if <math>20\nmid n</math>, then there is a multiple of <math>n</math> that is alternating.
 +
 +
We claim that there exists a <math>2k</math> digit alternating integer that is a multiple of <math>2^{2k+1}</math> and there exists an alternating integer with at most <math>k</math> digits that is a multiple of <math>2\cdot5^k</math>. We will prove this by induction.
 +
 +
Base Case: <math>k=1</math>
 +
We can let the number be <math>16</math>.
 +
 +
Inductive Step:
 +
Let <math>a</math> be a <math>2k-2</math> digit alternating number such that <math>2^{2k-1}\mid a</math>. Since <math>a</math> is even, this means that the first digit of <math>a</math> is odd. Let <math>b\cdot2^{2k-1}\equiv a\pmod{2^{2k+1}}</math>, where <math>b\in\{0,1,2,3\}</math>. Let <math>x=16-2b</math>. We see that <math>x</math> is alternating, so the number <math>x\cdot10^{2k-2}+a</math> is also alternating. We also have <math>x\equiv-2b\pmod8</math>. Since <math>a\equiv b\cdot2^{2k-1}\pmod{2^{2k+1}}</math>, 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 <math>4\mid5^{2k-2}-1</math>, this means that <math>x\cdot10^{2k-2}+a\equiv0\pmod{2^{2k+1}}</math>, so <math>x\cdot10^{2k-2}+a</math> is a <math>2k</math> digit alternating number that is a multiple of <math>2^{2k+1}</math>.
 +
 +
Now, we will prove that there exists an alternating integer with at most <math>k</math> digits that is a multiple of <math>2\cdot5^k</math>.
 +
 +
Base Case: <math>k=1</math>
 +
We can let the number be <math>0</math>.
 +
 +
Inductive Step:
 +
Let <math>a</math> be a <math>k-1</math> digit alternating number such that <math>2\cdot5^{k-1}\mid a</math>. Let <math>S</math> be the set of digits such that <math>x\cdot10^{k-1}+a</math> is alternating. We see that either <math>S=\{0,2,4,6,8\}</math> or <math>S=\{1,3,5,7,9\}</math>. In each possible set, each <math>\mod5</math> residue appears exactly once. Let <math>a=2\cdot5^{k-1}\cdot b</math>. Then, <math>x\cdot10^{k-1}+a=2\cdot5^{k-1}\left(x\cdot2^{k-2}+b\right)</math>. Therefore, there exists an <math>x</math> such that <math>2\cdot5^k\mid x\cdot10^{k-1}+a</math>, so there exists an alternating integer with at most <math>k</math> digits that is a multiple of <math>2\cdot5^k</math>. If <math>k</math> is even, then <math>0\not\in S</math>, so it has exactly <math>k</math> digits.
 +
 +
Now, let <math>n=2^a\cdot5^b\cdot m</math>. Then, if <math>20\nmid n</math>, then <math>a<2</math> or <math>b=0</math>. If <math>b=0</math>, then there exists a <math>2a</math> digit alternating integer <math>x</math> that is a multiple of <math>2^{2a+1}</math>. Consider the sequence <math>a_i=x\cdot\frac{10^{2ai}-1}{10^{2a}-1}</math>. Then, the decimal representation of <math>a_i</math> is the result when <math>x</math> is written <math>i</math> times. For any prime <math>p</math> that divides <math>n</math>, if <math>p\mid10^{2a}-1</math>, then <math>\nu_p\left(10^{2ai}-1\right)=\nu_p\left(10^{2a}-1\right)+\nu_p(i)</math>, so <math>\nu_p(a_i)=\nu_p(x)+\nu_p(i)\geq\nu_p(i)</math>. Therefore, there exists an <math>i</math> such that <math>p^{\nu_p(n)}\mid a_{ci}</math> for all <math>c</math>. If <math>p\nmid10^{2a}-1</math>, then if <math>i=\phi(n)</math>, then <math>p^{\nu_p(n)}\mid10^{2ai}-1</math> if <math>p\neq2,5</math>. Since <math>5\nmid n</math>, this means that we only need to make sure <math>2^a\mid x\cdot\frac{10^{2ai}-1}{10^{2a}-1}</math>. Since <math>2^{2a+1}\mid x</math>, this means that this is true, so if <math>5\nmid n</math>, then there exists a multiple of <math>n</math> that is alternating.
 +
 +
If <math>a<2</math>, then there exists an alternating integer <math>x</math> with exactly <math>2b</math> digits that is a multiple of <math>2\cdot5^{2b}</math>. Then, the first digit of <math>x</math> is odd. Let <math>a_i=x\cdot\frac{10^{2bi}-1}{10^{2b}-1}</math>. Then, if <math>p\mid10^{2b}-1</math>, then <math>\nu_p(a_i)\geq\nu_p(i)</math>, so there exists an <math>i</math> such that <math>p^{\nu_p(n)}\mid a_i</math>. If <math>p\nmid10^{2a}-1</math>, then we can let <math>i=\phi(n)</math>, so <math>p^{\nu_p(n)}\mid a_i</math>. If <math>p=5</math>, then <math>5^b\mid5^{2b}\mid x</math>, and if <math>p=2</math>, then <math>a=0,1</math>, so <math>p^a\mid x</math>. Therefore, <math>n\mid a_i</math> for some <math>i</math>.
 +
 +
Therefore, all positive integers except multiples of <math>20</math> have an alternating multiple.

Revision as of 07:32, 27 July 2021

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2004_IMO_Problems/Problem_6&oldid=159196"