Number Theory: Structures, Examples, and Problems

1.7. Numerical Systems
43
Problem 1.7.10.
Can the number obtained by writing the numbers from 1 to n in
order
(
n
>
1
)
be the same when read left to right and right to left?
(1996 Russian Mathematical Olympiad)
Solution.
It is not possible. Suppose 10
p
≤
n
<
10
p
+
1
. If
N
does not end with
321, then it will not be palindromic, so we may assume
p
≥
2. The longest run
of consecutive zeros in
N
will have length
p
. These runs occur exactly where we
write down the multiples of 10
p
. Suppose further
k
·
10
p
≤
n
< (
k
+
1
)
·
10
p
for a digit
k
. Then there are exactly
k
runs of
p
consecutive zeros, and the
k
th is
bracketed by
. . .
9
k
00
. . .
0
k
0
. . .
. Thus none of the runs of
p
zeros can be sent to
itself or another run by reversing the order of the digits.
Problem 1.7.11.
Three boxes with at least one marble in each are given. In a step
we choose two of the boxes, doubling the number of marbles in one of the boxes
by taking the required number of marbles from the other box. Is it always possible
to empty one of the boxes after a finite number of steps?
(1999 Slovenian Mathematical Olympiad)
Solution.
Without loss of generality suppose that the number of marbles in the
boxes are
a
,
b
, and
c
with
a
≤
b
≤
c
. Write
b
=
qa
+
r
where 0
≤
r
<
a
and
q
≥
1. Then express
q
in binary:
q
=
m
0
+
2
m
1
+ · · · +
2
k
m
k
,
where each
m
i
∈ {
0
,
1
}
and
m
k
=
1. Now for each
i
=
0
,
1
, . . . ,
k
, add 2
i
a
marbles to the first box: if
m
i
=
1 take these marbles from the second box;
otherwise, take them from this third box. In this way we take at most
(
2
k
−
1
)
a
<
qa
≤
b
≤
c
marbles from the third box and exactly
qa
marbles from the second
box altogether.
In the second box there are now
r
<
a
marbles left. Thus the box with the
least number of marbles now contains fewer than
a
marbles. Then by repeating
the described procedure, we will eventually empty one of the boxes.
Additional Problems
Problem 1.7.12.
The natural number
A
has the following property: the sum of the
integers from 1 to
A
, inclusive, has decimal expansion equal to that of
A
followed
by three digits. Find
A
.
(1999 Russian Mathematical Olympiad)
Problem 1.7.13.
A positive integer is said to be
balanced
if the number of its
decimal digits equals the number of its distinct prime factors. For instance, 15
is balanced, while 49 is not. Prove that there are only finitely many balanced
numbers.
(1999 Italian Mathematical Olympiad)

---

44