|
4.2
The Sum of the Digits of a Number
Problem 4.2.7.
Show that there exist infinitely many natural numbers n such that
S
(
3
n
)
≥
S
(
3
n
+
1
)
.
(1997 Russian Mathematical Olympiad)
Solution.
If
S
(
3
n
) <
S
(
3
n
+
1
)
for large
n
, we have (since powers of 3 are divisible
by 9, as are their digit sums)
S
(
3
n
)
≤
S
(
3
n
+
1
)
−
9. Thus
S
(
3
n
)
≥
9
(
n
−
c
)
for
some
c
, which is eventually a contradiction, since for large
n
, 3
n
<
10
n
−
c
.
Problem 4.2.8.
Do there exist three natural numbers a
,
b
,
c such that S
(
a
+
b
) <
5
, S
(
b
+
c
) <
5
, S
(
c
+
a
) <
5
, but S
(
a
+
b
+
c
) >
50
?
(1998 Russian Mathematical Olympiad)
Solution.
The answer is yes. It is easier to focus on the numbers
a
+
b
,
b
+
c
,
c
+
a
instead. Each of these has digit sum at most 4. Hence their sum 2
(
a
+
b
+
c
)
has digit sum at most 12. However, half this
a
+
b
+
c
has digit sum at least 51.
The only way this can happen is if
a
+
b
+
c
has digits either ten 5’s and a 1
or nine 5’s and a 6. Trying the former, we take
a
+
b
+
c
=
105555555555 and
2
(
a
+
b
+
c
)
=
211111111110 (many other choices also work). Each of
a
+
b
,
b
+
c
, and
c
+
a
must have digit sum 4, and they must add to 2
(
a
+
b
+
c
)
, so
there can be no carries. One such choice is
a
+
b
=
100001110000
,
b
+
c
=
11110000000
,
c
+
a
=
100000001110
.
From these we get
a
=
105555555555
−
11110000000
=
94445555555
,
b
=
105555555555
−
100000001110
=
5555554445
,
c
=
105555555555
−
100001110000
=
5554445555
.
4.2. The Sum of the Digits of a Number
269
Problem 4.2.9.
Prove that there exist distinct positive integers
{
n
i
}
1
≤
i
≤
50
such
that
n
1
+
S
(
n
1
)
=
n
2
+
S
(
n
2
)
= · · · =
n
50
+
S
(
n
50
).
(1999 Polish Mathematical Olympiad)
Solution.
We show by induction on
k
that there exist positive integers
n
1
, . . . ,
n
k
with the desired property. For
k
=
1 the statement is obvious. For
k
>
1, let
m
1
<
· · ·
<
m
k
−
1
satisfy the induction hypothesis for
k
−
1. Note that we can
make all the
m
i
arbitrarily large by adding some large power of 10 to all of them,
which preserves the described property. Then, choose
m
with 1
≤
m
≤
9 and
m
≡
m
1
+
1
(
mod 9
)
. Observing that
S
(
x
)
≡
x
(
mod 9
)
, we have
m
1
−
m
+
S
(
m
1
)
−
S
(
m
)
+
11
=
9
l
for some integer
l
. By choosing the
m
i
large enough
we can ensure that 10
l
>
m
k
−
1
. Now let
n
i
=
10
l
+
1
+
m
i
for
i
<
k
and
n
k
=
m
+
10
l
+
1
−
10. It is obvious that
n
i
+
S
(
n
i
)
=
n
j
+
S
(
n
j
)
for
i
,
j
<
k
, and
n
1
+
S
(
n
1
)
=
(
10
l
+
1
+
m
1
)
+
(
1
+
S
(
m
+
1
))
=
(
m
1
+
S
(
m
1
)
+
1
)
+
10
l
+
1
=
(
9
l
+
S
(
m
)
+
m
−
10
)
+
10
l
+
1
=
(
m
+
10
l
+
1
−
10
)
+
(
9
l
+
S
(
m
))
=
n
k
+
S
(
n
k
),
as needed.
Problem 4.2.10.
The sum of the decimal digits of the natural number n is
100
,
and that of
44
n is
800
. What is the sum of the digits of
3
n?
(1999 Russian Mathematical Olympiad)
Solution.
The sum of the digits of 3
n
is 300.
Suppose that
d
is a digit between 0 and 9, inclusive. If
d
≤
2 then
S
(
44
d
)
=
8
d
, and if
d
=
3 then
S
(
8
d
)
=
6
<
8
d
. If
d
≥
4, then 44
d
≤
44
(
9
)
has at most
three digits so that
S
(
44
d
)
≤
27
<
8
d
.
Now write
n
=
"
n
i
·
10
i
, so that the
n
i
are the digits of
n
in base 10. Then
8
n
i
=
S
(
44
n
)
≤
S
(
44
n
i
·
10
i
)
=
S
(
44
n
i
)
≤
8
n
i
,
so equality must occur in the second inequality, that is, each of the
n
i
must equal
0, 1, or 2. Then each digit of 3
n
is simply three times the corresponding digit of
n
, and
S
(
3
n
)
=
3
S
(
n
)
=
300, as claimed.
270
II Solutions, 4. Digits of Numbers
Alternative solution.
Using properties (3) and (5) involving the sum of digits, we
have
S
(
3
n
)
≤
3
S
(
n
)
=
300
and
800
=
S
(
11
·
3
n
+
11
n
)
≤
S
(
11
·
3
n
)
+
S
(
11
n
)
≤
S
(
11
)
S
(
3
n
)
+
S
(
11
)
S
(
n
)
=
2
S
(
3
n
)
+
200
,
whence
S
(
3
n
)
≥
300. Thus,
S
(
3
n
)
=
300.
Problem 4.2.11.
Consider all numbers of the form
3
n
2
+
n
+
1
, where n is a
positive integer.
(a) How small can the sum of the digits (in base
10
) of such a number be?
(b) Can such a number have the sum of its digits (in base
10
) equal to
1999
?
(1999 United Kingdom Mathematical Olympiad)
Solution.
(a) Let
f
(
n
)
=
3
n
2
+
n
+
1. When
n
=
8, the sum of the digits of
f
(
8
)
=
201 is 3. Suppose that there were some
m
such that
f
(
m
)
had a smaller
sum of digits. Then the last digit of
f
(
m
)
must be either 0, 1, or 2. Because
f
(
n
)
≡
1
(
mod 2
)
for all
n
,
f
(
m
)
must have units digit 1.
Because
f
(
n
)
can never equal 1, this means we must have 3
m
2
+
m
+
1
=
10
k
+
1 for some positive integer
k
, and
m
(
3
m
+
1
)
=
10
k
. Because
m
and 3
m
+
1
are relatively prime, and
m
<
3
m
+
1, we must have either
(
m
,
3
m
+
1
)
=
(
1
,
10
k
)
,
which is impossible, or
(
m
,
3
m
+
1
)
=
(
2
k
,
5
k
)
. For
k
=
1, 5
k
=
3
·
2
k
+
1; for
k
>
1, we have
5
k
=
5
k
−
2
·
25
>
2
k
−
2
·
(
12
+
1
)
≥
3
·
2
k
+
1
.
Therefore,
f
(
m
)
cannot equal 10
k
+
1, and 3 is indeed the minimum value for
the sum of digits.
(b) Consider
n
=
10
222
−
1. Then
f
(
n
)
=
3
·
10
444
−
6
·
10
222
+
3
+
10
222
.
Thus, its decimal expansion is
2 9
. . .
9
221
5 0
. . .
0
221
3
,
and the sum of digits in
f
(
10
222
−
1
)
is 1999.
Problem 4.2.12.
Consider the set A of all positive integers n with the following
properties: the decimal expansion contains no
0
, and the sum of the (decimal)
digits of n divides n.
Do'stlaringiz bilan baham: |
