|
particular
a
n
=
2) and we get
a
0
=
3
·
2
2002
−
1. We will show that this is the
only possibility. Using the two rules, there are two possibilities for
a
2001
, namely
5 or 1
/
2. Using the two rules a second time, there are four possibilities for
a
2000
,
namely 11
,
5
/
7
,
2, and 1
/
5. Since we are not allowed to reuse 2, the third is not
actually permitted. Note that the other three are all of the form
p
/
q
for
p
and
q
odd and relatively prime. We will show by (downward) induction on
n
that all
subsequent
a
n
’s have this form, that the denominator never decreases, and that if
we ever use the second rule, then we have
q
>
1. It follows that the only way to
get
a
0
an integer is always to apply the first rule, as claimed above.
Suppose
a
n
+
1
=
p
/
q
with
p
and
q
odd and relatively prime and that we apply
the first rule. Then
a
n
=
2
p
/
q
+
1
=
(
2
p
+
q
)/
q
. The numerator and denominator
are clearly both odd and gcd
(
2
p
+
q
,
q
)
=
gcd
(
2
p
,
q
)
=
1, since
q
is odd and
relatively prime to
p
. Thus
a
n
again has the desired form and the denominator
was unchanged.
Suppose
a
n
+
1
=
p
/
q
with
p
and
q
odd and relatively prime and that we
apply the second rule. Then
a
n
=
p
/(
2
q
+
p
)
. The numerator and denominator
are clearly both odd and gcd
(
p
,
2
q
+
p
)
=
gcd
(
p
,
2
q
)
=
1, since
p
is odd and
relatively prime to
q
. Thus again
a
n
has the desired form and the denominator has
increased. Thus if we ever apply this rule, the denominator will be greater than 1.
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
.
Solution.
Observe that setting
x
0
=
0, the condition is satisfied for
n
=
0.
We prove that there is an integer
k
≤
m
3
such that
x
k
divides
m
. Let
r
t
be the
remainder of
x
t
when divided by
m
for
t
=
0
,
1
, . . . ,
m
3
+
2. Consider the triples
9.3. Sequences of Integers
347
(
r
0
,
r
1
,
r
2
)
,
(
r
1
,
r
2
,
r
3
), . . .
,
(
r
m
3
,
r
m
3
+
1
,
r
m
3
+
2
)
. Since
r
t
can take
m
values, it
follows by the pigeonhole principle that at least two triples are equal. Let
p
be
the smallest number such that triple
(
r
p
,
r
p
+
1
,
r
p
+
2
)
is equal to another triple
(
r
q
,
r
q
+
1
,
r
q
+
2
)
,
p
<
q
≤
m
3
. We claim that
p
=
0.
Assume by way of contradiction that
p
≥
1. Using the hypothesis we have
r
p
+
2
≡
r
p
−
1
+
r
p
r
p
+
1
(
mod
m
)
and
r
q
+
2
≡
r
q
−
1
+
r
q
r
q
+
1
(
mod
m
).
Since
r
p
=
r
q
,
r
p
+
1
=
r
q
+
1
, and
r
p
+
2
=
r
q
+
2
, it follows that
r
p
−
1
=
r
q
−
1
so
(
r
p
−
1
,
r
p
,
r
p
+
1
)
=
(
r
q
−
1
,
r
q
,
r
q
+
1
)
, which is a contradiction to the minimality of
p
. Hence
p
=
0, so
r
q
=
r
0
=
0, and therefore
x
q
≡
0
(
mod
m
)
.
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)
Solution.
The only such sequence is 2
,
2
,
2
, . . .
, which clearly satisfies the given
condition.
Suppose gcd
(
a
k
−
1
,
a
k
−
2
)
=
1 for some
k
. Then
a
k
=
a
k
−
1
+
a
k
−
2
and hence
gcd
(
a
k
,
a
k
−
1
)
=
gcd
(
a
k
−
2
,
a
k
−
1
)
=
1. Hence by induction it follows that
a
n
=
a
n
−
1
+
a
n
−
2
for all
n
≥
k
, and the sequence is unbounded.
Therefore we must have gcd
(
a
n
−
1
,
a
n
−
2
)
≥
2 for all
n
and
a
n
=
a
n
−
1
+
a
n
−
2
gcd
(
a
n
−
1
,
a
n
−
2
)
≤
a
n
−
1
+
a
n
−
2
2
≤
max
(
a
n
−
1
,
a
n
−
2
)
for all
n
. Thus max
(
a
n
,
a
n
−
1
)
≤
max
(
a
n
−
1
,
a
n
−
2
)
. Since this is a decreasing
sequence of positive integers, it is eventually constant. If
a
n
−
1
<
a
n
−
2
, then
the argument above gives
a
n
< (
a
n
−
1
+
a
n
−
2
)/
2 and hence max
(
a
n
,
a
n
−
1
) <
max
(
a
n
−
1
,
a
n
−
2
)
. Thus we must eventually have
a
n
−
1
=
max
(
a
n
−
1
,
a
n
−
2
)
. Hence
the sequence
a
n
must be eventually constant. But if
a
n
−
1
=
a
n
−
2
, then we com-
pute gcd
(
a
n
−
1
,
a
n
−
2
)
=
a
n
−
1
=
a
n
−
2
and
a
n
=
2. Thus the sequence must be
eventually constant at 2.
Suppose now that
a
n
+
1
=
a
n
=
2. Then since gcd
(
a
n
,
a
n
−
1
) >
1, we must
have gcd
(
a
n
,
a
n
−
1
)
=
a
n
=
2 and 2
=
a
n
+
1
=
(
a
n
−
1
+
2
)/
2, implying
a
n
−
1
=
2.
Thus the only way the sequence can be eventually constant at the value 2 is if it
always has the value 2.
348
II Solutions, 9. Some Special Problems in Number Theory
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)
Solution.
Obviously, if
(
a
n
)
n
is such a sequence, so is
(
a
n
+
k
)
n
for all
k
. Thus it
suffices to find
p
<
q
such that
a
p
|
a
q
. Observe that from any 2001 consecutive
natural numbers, at least one is a term of the sequence. Now, consider the table
a
1
+
1
a
1
+
2
. . .
a
1
+
2001
a
1
+
1
+
x
1
a
1
+
2
+
x
1
. . .
a
1
+
2001
+
x
1
a
1
+
1
+
x
1
+
x
2
a
1
+
2
+
x
1
+
x
2
. . .
a
1
+
2001
+
x
1
+
x
2
...
where
x
1
=
2001
i
=
1
(
a
1
+
i
),
x
2
=
2001
i
=
1
(
a
1
+
i
+
x
1
),
x
3
=
2001
i
=
1
(
a
1
+
x
1
+
x
2
+
i
),
and so on. Observe then that if
x
,
y
are in the same column, then
x
|
y
or
y
|
x
.
Now look at the first 2002 lines. We find in this 2002
×
2001 matrix at least 2002
terms of the sequence (at least one on each line). Thus there are two terms of the
sequence in the same column, and one will divide the other.
Problem 9.3.32.
Define the sequence
{
x
n
}
n
≥
0
by x
0
=
0
and
x
n
=
⎧
⎨
⎩
x
n
−
1
+
3
r
+
1
−
1
2
,
if n
=
3
r
(
3
k
+
1
),
x
n
−
1
−
3
r
+
1
+
1
2
,
if n
=
3
r
(
3
k
+
2
),
where k and r are nonnegative integers. Prove that every integer appears exactly
once in this sequence.
(1999 Iranian Mathematical Olympiad)
First solution.
We prove by induction on
t
≥
1 that
(i)
{
x
0
,
x
1
, . . . ,
x
3
t
−
2
} =
)
−
3
t
−
3
2
,
−
3
t
−
5
2
, . . . ,
3
t
−
1
2
*
;
(ii)
x
3
t
−
1
= −
3
t
−
1
2
.
These claims imply the desired result, and they are easily verified for
t
=
1.
Now supposing they are true for
t
, we show they are true for
t
+
1.
For any positive integer
m
, write
m
=
3
r
(
3
k
+
s
)
for nonnegative integers
r
,
k
,
s
, with
s
∈ {
1
,
2
}
, and define
r
m
=
r
and
s
m
=
s
.
Do'stlaringiz bilan baham: |
