Number Theory: Structures, Examples, and Problems

Problem 1.7.15.
How many
10
-digit numbers divisible by
66667
are there whose
decimal representation contains only the digits
3
,
4
,
5
, and
6
?
(1999 St. Petersburg City Mathematical Olympiad)
First solution.
Suppose that 66667
n
had 10 digits, all of which were 3, 4, 5, and
6. Then
3333333333
≤
66667
n
≤
6666666666
⇒
50000
≤
n
≤
99999
.
Now consider the following cases:
(i)
n
≡
0
(
mod 3
)
. Then
66667
n
=
2
3
n
·
10
5
+
1
3
n
,
the five digits of 3
·
n
3
followed by the five digits of
n
3
. These digits are all 3, 4, 5,
or 6 if and only if
n
3
=
33333 and
n
=
99999.
(ii)
n
≡
1
(
mod 3
)
. Then
66667
n
=
2
3
(
n
−
1
)
·
10
5
+
1
3
(
n
+
2
)
+
66666
,
the five digits of
2
3
(
n
−
1
)
followed by the five digits of
1
3
(
n
+
2
)
+
66666. Because
1
3
(
n
+
2
)
+
66666 must be between 66667 and 99999, its digits cannot be 3, 4, 5,
or 6. Hence there are no satisfactory
n
≡
1
(
mod 3
)
.
(iii)
n
≡
2
(
mod 3
)
. Let
a
=
1
3
(
n
−
2
)
. Then
66667
n
=
2
3
(
n
−
2
)
+
1
·
10
5
+
1
3
(
n
−
2
)
+
33334
,
the five digits of
x
=
2
a
+
1 followed by the five digits of
y
=
a
+
33334. The
units digits in
x
and
y
are between 3 and 6 if and only if the units digit in
a
is 1

---

240
II Solutions, 1. Divisibility
or 2. In this case the other digits in
x
and
y
are all between 3 and 6 if and only
if the other digits in
a
are 2 or 3. Thus there are thirty-two satisfactory
a
’s (we
can choose each of its five digits from two options), and each
a
corresponds to a
satisfactory
n
=
3
a
+
2.
Therefore there is exactly one satisfactory
n
≡
0
(
mod 3
)
, and thirty-two
satisfactory
n
≡
2
(
mod 3
)
, making a total of thirty-three values of
n
and thirty-
three ten-digit numbers.
Second solution.
Write 66667
n
=
10
5
A
+
B
, where
A
and
B
are five digit
numbers. Since 66667
|
2
·
10
5
+
1 and 66667
|
2
·
10
5
A
+
2
B
, we have 66667
|
2
B
−
A
. Since
−
66666
≤
2
B
−
A
≤
166662, this leaves only the two possibilities
2
B
−
A
=
0 and 2
B
−
A
=
66667.
If
A
=
2
B
, then working up from the least-significant digit, we see that
B
=
33333 and
A
=
66666 is the only solution. If 2
B
=
A
+
66667
=
10
6
+
(
A
−
33333
)
, then 2
B
must have six digits, with leading digit 1 and the remaining digits
0, 1, 2, or 3. Hence working up from the least significant digit we see that
B
has
only 5’s and 6’s as digits. Conversely, a
B
with all digits 5 or 6 gives a 2
B
of the
desired form and a corresponding
A
. There is 1 solution in the first case and 32 in
the second, so 33 solutions total.
Problem 1.7.16.
Call positive integers similar if they are written using the same
digits. For example, for the digits
1
,
1
,
2
, the similar numbers are
112
,
121
, and
211
. Prove that there exist three similar
1995
-digit numbers containing no zero
digit such that the sum of two them equals the third.
(1995 Russian Mathematical Olympiad)
Solution.
Noting that 1995 is a multiple of 3, we might first try to find three
similar 3-digit numbers such that the sum of two of them equals the third. There
are various digit arrangements to try, one of which is
abc
+
acb
=
cba
. Since
c
,
as a leading digit, cannot be zero, the middle column implies
c
=
9, and there are
carries into and out of this column. Hence 2
a
+
1
=
c
and
b
+
c
=
a
+
10. The
first equation gives
a
=
3, and then the second gives
b
=
5, and we discover that
459
+
495
=
954.
Problem 1.7.17.
Let k and n be positive integers such that
(
n
+
2
)
n
+
2
, (
n
+
4
)
n
+
4
, (
n
+
6
)
n
+
6
, . . . , (
n
+
2
k
)
n
+
2
k
end in the same digit in decimal representation. At most how large is k?
(1995 Hungarian Mathematical Olympiad)
Solution.
We cannot have
k
≥
5, since then one of the terms would be divisible
by 5 and so would end in a different digit from those not divisible by 5. Hence
k
≤
4. In fact, we will see that
k
=
3 is the best possible.

---

1.7. Numerical Systems
241
Since
x
5
≡
x
(
mod 10
)
for all
x
,
x
x
(
mod 10
)
depends only on
x
(
mod 20
)
.
Hence it suffices to tabulate the last digit of
x
x
for
x
=
0
, . . . ,
19 and look for the
longest run. For the evens, we get
0
,
4
,
6
,
6
,
6
,
0
,
6
,
6
,
6
,
4
,
while for the odds, we get
1
,
7
,
5
,
3
,
9
,
1
,
3
,
5
,
7
,
9
.
Clearly a run of 3 is the best possible.
Problem 1.7.18.
Let
1996
n
=
1
(
1
+
nx
3
n
)
=
1
+
a
1
x
k
1
+
a
2
x
k
2
+ · · · +
a
m
x
k
m
,
where a
1
,
a
2
, . . . ,
a
m
are nonzero and k
1
<
k
2
<
· · ·
<
k
m
, Find a
1996
.
(1996 Turkish Mathematical Olympiad)
Solution.
Note that
k
i
/
3 is the number obtained by writing
i
in base 2 and reading
the result as a number in base 3, and
a
i
is the product of the exponents of the
powers of 3 used in
k
i
. Thus
k
1996
=
3
11
+
3
10
+
3
9
+
3
8
+
3
7
+
3
4
+
3
3
and
a
1996
=
3
·
4
·
7
·
8
·
9
·
10
·
11
=
665280
.
Problem 1.7.19.
For any positive integer k, let f
(
k
)
be the number of elements in
the set
{
k
+
1
,
k
+
2
, . . . ,
2
k
}
whose base-
2
representation has precisely three
1
’s.
(a) Prove that for each positive integer m, there exists at least one positive
integer k such that f
(
k
)
=
m.
(b) Determine all positive integers m for which there exists exactly one k with
f
(
k
)
=
m.
(35th International Mathematical Olympiad)
Solution.
(a) Let
g
:
N
→
N
be the function defined as follows:
g
(
k
)
is the
number of elements in the set
{
1
,
2
, . . . ,
k
}
having three digits 1 in their binary
representation. The following equalities are obvious:
f
(
k
)
=
g
(
2
k
)
−
g
(
k
)
and
f
(
k
+
1
)
−
f
(
k
)
=
g
(
2
k
+
2
)
−
g
(
2
k
)
−
(
g
(
k
+
1
)
−
g
(
k
)).

---

242
II Solutions, 1. Divisibility
The binary representation of 2
k
+
2 is obtained by adding a final 0 in the binary
representation of
k
+
1. Thus, we have the following result:
f
(
k
+
1
)
−
f
(
k
)
=
⎧
⎨
⎩
1 if the binary representation of 2
k
+
1
contains three digits 1
,
0 otherwise.
(
1
)
Another way to derive formula (1) is the following: Consider going from com-
puting
f
(
k
)
to computing
f
(
k
+
1
)
. The sets of integers used to compute these
are nearly the same. The difference is just that we replace
k
+
1 with 2
k
+
1 and
2
k
+
2. Since
k
+
1 and 2
k
+
2 have the same number of ones in their binary
representations, we get (1).
It proves that the function
f
increases by at most 1 from
k
to
k
+
1.
Since
g
(
2
n
)
=
n
3
and
f
(
2
n
)
=
n
+
1
3
−
n
3
=
n
2
, it follows that
f
is an
unbounded function. If we combine the above property with the observation that
f
(
4
)
=
1, we find that the range of
f
is the set of all nonnegative integers.
Also, we can obtain the formula
f
(
2
n
)
=
n
2
in a different way: The elements
of
{
2
n
+
1
, . . . ,
2
n
+
1
}
whose binary representation has exactly three 1’s are exactly
the (
n
+
1)-digit binary numbers whose leading digit is 1 and that have ones in 2
of the remaining
n
places. Hence there are
f
(
n
)
=
n
2
of them.
(b) Let us suppose that the equation
f
(
k
)
=
m
has a unique solution. It follows
that
f
(
k
+
1
)
−
f
(
k
)
=
f
(
k
)
−
f
(
k
+
1
)
=
1
.
By (1), it follows that the binary representations of 2
k
+
1 and 2
k
−
1 contain
three digits 1. Then the binary representation of
k
contains two digits 1. From
2
k
−
1
=
2
(
k
−
1
)
+
1 one obtains that the binary representation of
k
−
1 also
contains two digits 1. Hence, the last digit of
k
−
1 is 1, and the last-but-one digit
is 0. Thus,
k
−
1
=
2
n
+
1 and
k
=
2
n
+
2, where
n
≥
2.
For such a number we have
f
(
2
n
+
2
)
=
g
(
2
n
+
1
+
4
)
−
g
(
2
n
+
2
)
=
1
+
g
(
2
n
+
1
)
−
g
(
2
n
)
=
1
+
n
2
.
Thus, we have proved that the equation
f
(
k
)
=
m
has a unique solution if and
only if
m
is a number of the form
m
=
1
+
n
2
,
n
≥
2.
Problem 1.7.20.
For each positive integer n, let S
(
n
)
be the sum of digits in the
decimal representation of n. Any positive integer obtained by removing several
(at least one) digits from the right-hand end of the decimal representation of n
is called a stump of n. Let T
(
n
)
be the sum of all stumps of n. Prove that n
=
S
(
n
)
+
9
T
(
n
)
.
(2001 Asian Pacific Mathematical Olympiad)

---