|
I Fundamentals, 9. Some Special Problems in Number Theory
Solution.
Consider the possible values of
(
a
n
,
a
n
+
1
)
modulo 4:
a
n
0 1 2 3
a
n
+
1
3 0 3 2
No matter what
a
1
is, the terms
a
3
,
a
4
, . . .
are all 2 or 3
(
mod 4
)
. However,
all perfect squares are 0 or 1
(
mod 4
)
, so at most two terms (
a
1
and
a
2
) can
be perfect squares. If
a
1
and
a
2
are both perfect squares, then writing
a
1
=
a
2
,
a
2
=
b
2
we have
a
6
+
1999
=
b
2
or 1999
=
b
2
−
(
a
3
)
2
=
(
b
+
a
3
)(
b
−
a
3
)
.
Because 1999 is prime,
b
−
a
3
=
1 and
b
+
a
3
=
1999. Thus
a
3
=
1999
−
1
2
=
999,
which is impossible. Hence at most one term of the sequence is a perfect square.
Problem 9.3.18.
Determine whether there exists an infinite sequence of positive
integers such that
(i) no term divides any other term;
(ii) every pair of terms has a common divisor greater than
1
, but no integer
greater than
1
divides all the terms.
(1999 Hungarian Mathematical Olympiad)
Solution.
The desired sequence exists. Let
p
0
,
p
1
, . . .
be the primes greater than
5 in order, and let
q
3
i
=
6,
q
3
i
+
1
=
10,
q
3
i
+
2
=
15 for each nonnegative integer
i
. Then let
s
i
=
p
i
q
i
for all
i
≥
0. The sequence
s
0
,
s
1
,
s
2
, . . .
clearly satisfies (i)
because
s
i
is not even divisible by
p
j
for
i
=
j
. For the first part of (ii), any two
terms have their indices both in
{
0
,
1
}
, both in
{
0
,
2
}
, or both in
{
1
,
2
}
(
mod 3
)
,
so they have a common divisor of 2, 3, or 5, respectively. For the second part, we
just need to check that no prime divides all the
s
i
. Indeed, 2
s
2
, 3
s
1
, 5
s
0
, and
no prime greater than 5 divides more than one
s
i
.
Problem 9.3.19.
Let a
1
,
a
2
, . . .
be a sequence satisfying a
1
=
2
, a
2
=
5
, and
a
n
+
2
=
(
2
−
n
2
)
a
n
+
1
+
(
2
+
n
2
)
a
n
for all n
≥
1
. Do there exist indices p
,
q, and r such that a
p
a
q
=
a
r
?
(1995 Czech–Slovak Match)
Solution.
No such
p
,
q
,
r
exist. We show that for all
n
,
a
n
≡
2
(
mod 3
)
. This
holds for
n
=
1 and
n
=
2 by assumption and follows for all
n
by induction:
a
n
+
2
=
(
2
−
n
2
)
a
n
+
1
+
(
2
+
n
2
)
a
n
≡
2
(
2
−
n
2
)
+
2
(
2
+
n
2
)
=
8
≡
2
(
mod 3
).
Let
p
,
q
,
r
be positive integers. We have
a
p
a
q
≡
1
(
mod 3
)
, so
a
p
a
q
is
different from
a
r
, which is congruent to 2
(
mod 3
)
.
9.3. Sequences of Integers
193
Problem 9.3.20.
Is there a sequence of natural numbers in which every natural
number occurs just once and moreover, for any k
=
1
,
2
,
3
, . . .
the sum of the
first k terms is divisible by k?
(1995 Russian Mathematical Olympiad)
Solution.
We recursively construct such a sequence. Suppose
a
1
, . . . ,
a
m
have
been chosen, with
s
=
a
1
+ · · · +
a
m
, and let
n
be the smallest number not yet
appearing. By the Chinese remainder theorem, there exists
t
such that
t
≡ −
s
(
mod
m
+
1
)
and
t
≡ −
s
−
n
(
mod
m
+
2
)
. We can increase
t
by a suitably large
multiple of
(
m
+
1
)(
m
+
2
)
to ensure that it does not equal any of
a
1
, . . . ,
a
m
.
Then
a
1
, . . . ,
a
m
,
t
,
n
also has the desired property, and the construction ensures
that 1
, . . . ,
m
all occur among the first 2
m
terms.
Additional Problems
Problem 9.3.21.
Let
{
a
n
}
be a sequence of integers such that for
n
≥
1,
(
n
−
1
)
a
n
+
1
=
(
n
+
1
)
a
n
−
2
(
n
−
1
).
If 2000 divides
a
1999
, find the smallest
n
≥
2 such that 2000 divides
a
n
.
(1999 Bulgarian Mathematical Olympiad)
Problem 9.3.22.
The sequence
(
a
n
)
n
≥
0
is defined by
a
0
=
1,
a
1
=
3, and
a
n
+
2
=
a
n
+
1
+
9
a
n
if
n
is even
,
9
a
n
+
1
+
5
a
n
if
n
is odd
.
Prove that
(a)
"
2000
k
=
1995
a
2
k
is divisible by 20,
(b)
a
2
n
+
1
is not a perfect square for any
n
=
0
,
1
,
2
, . . .
.
(1995 Vietnamese Mathematical Olympiad)
Problem 9.3.23.
Prove that for any natural number
a
1
>
1, there exists an in-
creasing sequence of natural numbers
a
1
,
a
2
, . . .
such that
a
2
1
+
a
2
2
+ · · · +
a
2
k
is
divisible by
a
1
+
a
2
+ · · · +
a
k
for all
k
≥
1.
(1995 Russian Mathematical Olympiad)
Problem 9.3.24.
The sequence
a
0
,
a
1
,
a
2
, . . .
satisfies
a
m
+
n
+
a
m
−
n
=
1
2
(
a
2
m
+
a
2
n
)
for all nonnegative integers
m
and
n
with
m
≥
n
. If
a
1
=
1, determine
a
n
.
(1995 Russian Mathematical Olympiad)
194
I Fundamentals, 9. Some Special Problems in Number Theory
Problem 9.3.25.
The sequence of real numbers
a
1
,
a
2
,
a
3
, . . .
satisfies the initial
conditions
a
1
=
2,
a
2
=
500,
a
3
=
2000 as well as the relation
a
n
+
2
+
a
n
+
1
a
n
+
1
+
a
n
−
1
=
a
n
+
1
a
n
−
1
for
n
=
2
,
3
,
4
, . . .
. Prove that all the terms of this sequence are positive integers
and that 2
2000
divides the number
a
2000
.
(1999 Slovenian Mathematical Olympiad)
Problem 9.3.26.
Let
k
be a fixed positive integer. We define the sequence
a
1
,
a
2
,
. . .
by
a
1
=
k
+
1 and the recursion
a
n
+
1
=
a
2
n
−
ka
n
+
k
for
n
≥
1. Prove that
a
m
and
a
n
are relatively prime for distinct positive integers
m
and
n
.
Problem 9.3.27.
Suppose the sequence of nonnegative integers
a
1
,
a
2
, . . .
,
a
1997
satisfies
a
i
+
a
j
≤
a
i
+
j
≤
a
i
+
a
j
+
1
for all
i
,
j
≥
1 with
i
+
j
≤
1997. Show that there exists a real number
x
such
that
a
n
=
nx
for all 1
≤
n
≤
1997.
(1997 USA Mathematical Olympiad)
Problem 9.3.28.
The sequence
{
a
n
}
is given by the following relation:
a
n
+
1
=
a
n
−
1
2
,
if
a
n
≥
1
,
2
a
n
1
−
a
n
,
if
a
n
<
1
.
Given that
a
0
is a positive integer,
a
n
=
2 for each
n
=
1
,
2
, . . . ,
2001, and
a
2002
=
2, find
a
0
.
(2002 St. Petersburg City Mathematical Olympiad)
Problem 9.3.29.
Let
x
1
=
x
2
=
x
3
=
1 and
x
n
+
3
=
x
n
+
x
n
+
1
x
n
+
2
for all
positive integers
n
. Prove that for any positive integer
m
there is an integer
k
>
0
such that
m
divides
x
k
.
Problem 9.3.30.
Find all infinite bounded sequences
a
1
,
a
2
, . . .
of positive inte-
gers such that for all
n
>
2,
a
n
=
a
n
−
1
+
a
n
−
2
gcd
(
a
n
−
1
,
a
n
−
2
)
.
(1999 Russian Mathematical Olympiad)
Problem 9.3.31.
Let
a
1
,
a
2
, . . .
be a sequence of positive integers satisfying the
condition 0
<
a
n
+
1
−
a
n
≤
2001 for all integers
n
≥
1. Prove that there exists an
infinite number of ordered pairs
(
p
,
q
)
of distinct positive integers such that
a
p
is
a divisor of
a
q
.
(2001 Vietnamese Mathematical Olympiad)
Do'stlaringiz bilan baham: |
