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...") |
|||
(One intermediate revision by one other user not shown) | |||
Line 1: | Line 1: | ||
+ | ==Problem== | ||
+ | |||
We call a positive integer alternating if every two consecutive digits in its decimal | 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 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. | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=2004|num-b=5|after=Last Problem}} |
Latest revision as of 00:55, 19 November 2023
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 |