|
4.2. The Sum of the Digits of a Number
271
(a) Prove that there exist infinitely many elements in A with the following
property: the digits that appear in the decimal expansion of A appear the same
number of times.
(b) Show that for each positive integer k, there exists an element in A with
exactly k digits.
(2001 Austrian–Polish Mathematics Competition)
Solution.
(a) We can take
n
k
=
11
. . .
1
3
k
times
and prove by induction that 3
k
+
2
|
10
3
k
−
1. Alternatively, one can observe that
10
3
k
−
1
=
(
10
−
1
)(
10
2
+
10
+
1
)(
10
2
·
3
+
10
3
+
1
)
· · ·
(
10
2
·
3
k
−
1
+
10
3
k
−
1
+
1
)
and that 9
|
10
−
1 and 3
|
10
2
·
3
i
+
10
3
i
+
1 for 0
≤
i
≤
k
−
1.
(b) We will need the following lemmas.
Lemma 1.
For every d
>
0
there exists a d-digit number that contains only ones
and twos in its decimal expansion and is a multiple of
2
d
.
Proof.
Exactly in the same way as in the proof of Theorem 1.7.1 one can prove
that any two
d
-digit numbers that have only ones and twos give different residues
mod 2
d
. Since there are 2
d
such numbers, one of them is a multiple of 2
d
.
Lemma 2.
For each k
>
2
there exists d
≤
k such that the following inequality
holds: k
+
d
≤
2
d
≤
9
k
−
8
d.
Proof.
For 3
≤
k
≤
5,
d
=
3 satisfies the inequalities. For 5
≤
k
≤
10,
d
=
4
satisfies the inequalities. We will show that
d
=
log
2
4
k
satisfies the inequality
for all
k
>
10. If
k
>
3, then log
2
4
k
≤
2
k
, so
d
<
k
. Additionally,
k
+
d
≤
2
k
≤
2
d
. If
k
>
10, then 16
k
2
≤
2
k
, so 4
k
≤
2
k
/
2
≤
2
5
k
/
8
,
d
≤
log
2
4
k
≤
5
8
n
, and
8
k
−
8
d
≥
4
k
≥
2
d
.
Now return to the original problem. For
k
=
1,
n
=
1 has the desired property.
For
k
=
2,
n
=
12 has the desired property. Now, for each
k
>
2 we have some
number
d
satisfying the condition Lemma 2. Consider a
k
-digit integer
n
such
that the last
d
digits of
n
have the property described in the first lemma. We can
choose each of the other digits of
n
to be any number between zero and nine. We
know that the sum of the last
d
digits of
n
is between
d
and 2
d
, and we can choose
the sum of the other
k
−
d
digits to be any number between
k
−
d
and 9
(
k
−
d
)
.
Since
k
−
d
+
2
d
≤
2
d
≤
9
(
k
−
d
)
+
d
, we can choose the other digits such that
the sum of the digits of
n
is 2
d
. This completes the proof because
n
is a multiple
of 2
d
.
Remarks.
(1) Suppose 3
m
≤
k
<
3
m
+
1
and choose an integer
r
with
k
+
1
−
3
m
decimal digits and
S
(
r
)
=
3, for example,
r
=
10
k
−
3
m
+
2. Then the desired
number is
n
=
r
·
111
. . .
1, with 3
m
ones. Since
S
(
r
)
=
3, 3
|
r
, and we saw
272
II Solutions, 4. Digits of Numbers
in part (a) that 3
m
|
111
. . .
1. Hence 3
m
+
1
|
n
. Also since
S
(
r
)
=
3
<
10, no
carries occur in multiplying out to compute
n
. Hence
n
has
k
decimal digits and
S
(
n
)
=
3
m
S
(
r
)
=
3
m
+
1
.
(2) A number divisible by the sum of its digits is called a
Niven
1
number
.
It has been proved recently that the number of Niven numbers smaller than
x
is
14
27
log 10
+
o
(
1
)
x
log
x
. The courageous reader may try to prove that there are
arbitrarily long sequences of consecutive numbers that are not Niven numbers
(which is easily implied by the above result; yet there is an elementary proof). For
more details one can read the article “Large and small gaps between consecutive
Niven numbers,”
Journal of Integer Sequences
, 6 (2003), by J.-M. Koninck and
N. Doyon.
4.3
Other Problems Involving Digits
Problem 4.3.3.
A wobbly number is a positive integer whose digits in base
10
are
alternately nonzero and zero, the units digit being nonzero. Determine all positive
integers that do not divide any wobbly number.
(35th International Mathematical Olympiad Shortlist)
Solution.
If
n
is a multiple of 10, then the last digit of any multiple of
n
is 0.
Hence it is not wobbly. If
n
is a multiple of 25, then the last two digits of any
multiple of
n
are 25, 50, 75 or 00. Hence it is not wobbly. We now prove that
these are the only numbers not dividing any wobbly number.
We first consider odd numbers
m
not divisible by 5. Then gcd
(
m
,
10
)
=
1,
and we have gcd
((
10
k
−
1
)
m
,
10
)
=
1, for any
k
≥
1. It follows that there exists
a positive integer
l
such that 10
l
≡
1
(
mod
(
10
k
−
1
)
m
)
, and we have 10
kl
≡
1
(
mod
(
10
k
−
1
)
m
)
. Now
10
kl
−
1
=
(
10
k
−
1
)(
10
k
(
l
−
1
)
+
10
k
(
l
−
2
)
+ · · · +
10
k
+
1
).
Hence
x
k
=
10
k
(
l
−
1
)
+
10
k
(
l
−
2
)
+ · · · +
10
k
+
1 is a multiple of
m
for any
k
≥
1. In particular,
x
2
is a wobbly multiple of
m
. If
m
is divisible by 5, then 5
x
2
is a wobbly multiple of
m
.
Next, we consider powers of 2. We prove by induction on
t
that 2
2
t
+
1
has
a wobbly multiple
w
t
with precisely
t
nonzero digits. For
t
=
1, take
w
1
=
8.
Suppose
w
t
exists for some
t
≥
1. Then
w
t
=
2
2
t
+
1
d
for some
d
. Let
w
t
+
1
=
10
2
t
c
+
w
t
, where
c
∈ {
1
,
2
,
3
, . . . ,
9
}
is to be chosen later. Clearly,
w
t
+
1
is
wobbly, and has precisely
t
+
1 nonzero digits. Since
w
t
+
1
=
2
2
t
(
5
2
t
c
+
2
d
)
, it is
divisible by 2
2
t
+
3
if and only if 5
2
t
c
+
2
d
≡
0
(
mod 8
)
or
c
≡
6
d
(
mod 8
)
. We
1
Ivan Niven (1915–1999), Canadian mathematician with contributions in the areas of Diophantine
approximation, the study of irrationality and transcendence of numbers, and combinatorics.
4.3. Other Problems Involving Digits
273
can always choose
c
to be one of 8, 6, 4, and 2 in order to satisfy this congruence.
Thus the inductive argument is completed. It now follows that every power of 2
has a wobbly multiple.
Finally, consider numbers of the form 2
t
m
, where
t
≥
1 and gcd
(
m
,
10
)
=
1.
Such a number has
w
t
x
2
t
as a wobbly multiple.
Problem 4.3.4.
A positive integer is called monotonic if its digits in base 10, read
from left right, are in nondecreasing order. Prove that for each n
∈
N
, there exists
an n-digit monotonic number that is a perfect square.
(2000 Belarusian Mathematical Olympiad)
Solution.
Any 1-digit perfect square (namely, 1, 4, or 9) is monotonic, proving
the claim for
n
=
1. We now assume
n
>
1.
If
n
is odd, write
n
=
2
k
−
1 for an integer
k
≥
2, and let
x
k
=
(
10
k
+
2
)/
6
=
1 66
. . .
6
k
−
2
7
.
Then
x
2
k
=
10
2
k
+
4
·
10
k
+
4
36
=
10
2
k
36
+
10
k
9
+
1
9
.
(
1
)
Observe that
10
2
k
36
=
10
2
k
−
2
72
36
+
28
36
2
·
10
2
k
−
2
+
10
2
k
−
2
·
7
9
=
2 77
. . .
7
2
k
−
2
+
7
9
.
Thus, the right-hand side of
(
1
)
equals
2 77
. . .
7
2
k
−
2
+
7
9
+
11
. . .
1
k
+
1
9
+
1
9
=
2 77
. . .
7
k
−
2
88
. . .
8
k
−
1
9
,
an
n
-digit monotonic perfect square.
If
n
is even, write
n
=
2
k
for an integer
k
≥
1, and let
y
k
=
10
k
+
2
3
=
33
. . .
3
k
−
1
4
.
Then
y
2
k
=
1
9
(
10
2
k
+
4
·
10
k
+
4
)
=
10
2
k
9
+
4
·
10
k
9
+
4
9
=
11
. . .
1
2
k
+
1
9
+
44
. . .
4
k
+
4
9
+
4
9
=
11
. . .
1
k
55
. . .
5
k
−
1
6
,
an
n
-digit monotonic perfect square. This completes the proof.
Do'stlaringiz bilan baham: |
