|
II Solutions, 5. Basic Principles in Number Theory
Second, we claim that
x
1
,
y
1
,
z
1
>
0. This is obvious for
x
1
. Next, note that
y
1
=
x
0
+
y
0
−
2
z
0
≥
2
√
x
0
y
0
−
2
z
0
>
2
z
0
−
2
z
0
=
0. Finally, because
x
0
≤
y
0
and
x
0
y
0
=
z
2
0
+
1, we have
x
0
≤
6
z
2
0
+
1, or
x
0
≤
z
0
. However,
x
0
=
z
0
,
because this would imply that
z
0
y
0
=
z
2
0
+
1, but
z
0
(
z
2
0
+
1
)
when
z
0
>
1. Thus,
z
0
−
x
0
>
0, or
z
1
>
0.
Therefore,
(
x
1
,
y
1
,
z
1
)
is a triple of positive integers
(
x
,
y
,
z
)
satisfying
x y
=
z
2
+
1 and with
z
<
z
0
. By the inductive hypothesis, we can write
x
1
=
a
2
+
b
2
,
y
1
=
c
2
+
d
2
, and
z
1
=
ac
+
bd
. Then
(
ac
+
bd
)
2
=
z
2
1
=
x
1
y
1
−
1
=
(
a
2
+
b
2
)(
c
2
+
d
2
)
−
1
=
(
a
2
c
2
+
b
2
d
2
+
2
abcd
)
+
(
a
2
d
2
+
b
2
c
2
−
2
abcd
)
−
1
=
(
ac
+
bd
)
2
(
ad
−
bc
)
2
−
1
,
so that
|
ad
−
bc
| =
1.
Now note that
x
0
=
x
1
=
a
2
+
b
2
and
y
0
=
x
1
+
y
1
+
2
z
1
=
a
2
+
b
2
+
c
2
+
d
2
+
2
(
ac
+
bd
)
=
(
a
+
c
)
2
+
(
b
+
d
)
2
. In other words,
x
0
=
a
2
+
b
2
and
y
0
=
c
2
+
d
2
for
(
a
,
b
,
c
,
d
)
=
(
a
,
b
,
a
+
c
,
b
+
d
)
. Then
|
a
d
−
b
c
| = |
ad
−
bc
| =
1,
implying (by logic analogous to the reasoning in the previous paragraph) that
z
0
=
a
c
+
b
d
, as desired. This completes the inductive step, and the proof.
Problem 5.2.9.
Find all pairs of sets A
,
B, which satisfy the following conditions:
(i) A
∪
B
=
Z
;
(ii) if x
∈
A, then x
−
1
∈
B;
(iii) if x
∈
B and y
∈
B, then x
+
y
∈
A.
(2002 Romanian International Mathematical Olympiad Team Selection Test)
Solution.
We shall prove that either
A
=
B
=
Z
or
A
is the set of even numbers
and
B
the set of odd numbers.
First, assume that 0
∈
B
. Then we have
x
∈
B
,
x
+
0
∈
A
, and so
B
⊂
A
.
Then
Z
=
A
∪
B
⊂
A
, and so
A
=
Z
. From (ii) we also find that
B
=
Z
. Now
suppose that 0
∈
B
; thus 0
∈
A
and
−
1
∈
B
. Then, using (ii) we obtain
−
2
∈
A
,
−
3
∈
B
,
−
4
∈
A
, and by induction
−
2
n
∈
A
and
−
2
n
−
1
∈
B
, for all
n
∈
N
. Of
course, 2
∈
A
(otherwise 2
∈
B
and 1
=
2
+
(
−
1
)
∈
A
and 0
=
1
−
1
∈
B
, false),
and so 1
=
2
−
1
∈
B
. Let
n
>
1 be minimal with 2
n
∈
B
. Then 2
n
−
1
∈
A
and
2
(
n
−
1
)
∈
B
, contradiction. This shows that 2
N
⊂
A
\
B
and all odd integers are
in
B
\
A
. One can also observe that
−
1
∈
A
(otherwise
−
2
∈
B
implies
−
1
∈
B
,
i.e.,
−
1
∈
A
), and so
A
=
2
Z
,
B
=
2
Z
+
1.
Problem 5.2.10.
Find all positive integers n such that
n
=
m
k
=
0
(
a
k
+
1
),
5.2. Mathematical Induction
281
where a
m
a
m
−
1
· · ·
a
0
is the decimal representation of n.
(2001 Japanese Mathematical Olympiad)
Solution.
We claim that the only such
n
is 18. If
n
=
a
m
· · ·
a
1
a
0
, then let
P
(
n
)
=
m
j
=
0
(
a
j
+
1
).
Note that if
s
≥
1 and
t
is a single-digit number, then
P
(
10
s
+
t
)
=
(
t
+
1
)
P
(
s
)
. Using this we will prove the following two statements.
Lemma 1.
If P
(
s
)
≤
s, then P
(
10
s
+
t
) <
10
s
+
t.
Proof.
Indeed, if
P
(
s
)
≤
s
, then
10
s
+
t
≥
10
s
≥
10
P
(
s
)
≥
(
t
+
1
)
P
(
s
)
=
P
(
10
s
+
t
).
Equality must fail either in the first inequality (if
t
=
0) or in the third in-
equality (if
t
=
9).
Lemma 2.
P
(
n
)
≤
n
+
1
for all n.
Proof.
We prove this by induction on the number of digits of
n
. First, we know
that for all one-digit
n
,
P
(
n
)
=
n
+
1. Now suppose that
P
(
n
)
≤
n
+
1 for all
m
-digit numbers
n
. Any
(
m
+
1
)
-digit number
n
is of the form 10
s
+
t
, where
s
is an
m
-digit number. Then
t
(
P
(
s
)
−
1
)
≤
9
((
s
+
1
)
−
1
),
t P
(
s
)
−
10
s
−
t
≤ −
s
,
P
(
s
)(
t
+
1
)
−
10
s
−
t
≤
P
(
s
)
−
s
,
P
(
10
s
+
t
)
−
(
10
s
+
t
)
≤
P
(
s
)
−
s
≤
1
,
completing the inductive step. Thus,
P
(
n
)
≤
n
+
1 for all
n
.
If
P
(
n
)
=
n
, then
n
has more than one digit and we may write
n
=
10
s
+
t
.
From the first statement, we have
P
(
s
)
≥
s
+
1. From the second one, we have
P
(
s
)
≤
s
+
1. Thus,
P
(
s
)
=
s
+
1. Hence,
(
t
+
1
)
P
(
s
)
=
P
(
10
s
+
t
)
=
10
s
+
t
,
(
t
+
1
)(
s
+
1
)
=
10
s
+
t
,
1
=
(
9
−
t
)
s
.
This is possible if
t
=
8 and
s
=
1, so the only possible
n
such that
P
(
n
)
=
n
is 18. Indeed,
P
(
18
)
=
(
1
+
1
)(
8
+
1
)
=
18.
282
II Solutions, 5. Basic Principles in Number Theory
Problem 5.2.11.
The sequence
(
u
n
)
n
≥
0
is defined as follows: u
0
=
2
, u
1
=
5
2
and
u
n
+
1
=
u
n
(
u
2
n
−
1
−
2
)
−
u
1
for n
=
1
,
2
, . . . .
Prove that
u
n
=
2
2
n
−
(
−
1
)
n
3
, for all n
>
0
(
x
denotes the integer part of x).
(18th International Mathematical Olympiad)
Solution.
To start, we compute a few members of the sequence. Write
u
1
=
5
2
=
2
+
1
2
.
Then:
u
2
=
u
1
(
u
2
0
−
2
)
−
2
+
1
2
=
2
+
1
2
(
2
2
−
2
)
−
2
+
1
2
=
2
+
1
2
,
u
3
=
u
2
(
u
2
1
−
2
)
−
2
+
1
2
=
2
+
1
2
1
2
+
1
2
2
−
2
2
−
2
+
1
2
=
2
+
1
2
2
2
+
1
2
2
−
2
+
1
2
=
2
+
1
2
2
2
−
1
+
1
2
2
=
2
3
+
1
2
3
,
u
4
=
2
3
+
1
2
3
1
2
+
1
2
2
−
2
2
−
2
+
1
2
=
2
3
+
1
2
3
2
2
+
1
2
2
−
2
+
1
2
=
2
5
+
1
2
+
2
+
1
2
5
−
2
+
1
2
=
2
5
+
1
2
5
,
u
5
=
2
5
+
1
2
5
1
2
3
+
1
2
3
2
−
2
2
−
2
+
1
2
=
2
5
+
1
2
5
2
6
+
1
2
6
−
2
+
1
2
=
2
11
+
1
2
11
.
Taking into account the required result, we claim that
u
n
=
2
a
n
+
2
−
a
n
, where
a
n
=
2
n
−
(
−
1
)
n
3
, for all
n
≥
1. We observe that
a
n
is a positive integer, because
2
n
≡
(
−
1
)
n
(
mod 3
).
Observe that the claimed formula is true for
n
=
1
,
2
,
3
,
4
,
5. Using induction
and the inductive formula that defined
u
n
, we have
u
n
+
1
=
(
2
a
n
+
2
−
a
n
)
[
(
2
a
n
−
1
+
2
−
a
n
−
1
)
−
2
] −
2
+
1
2
=
(
2
a
n
+
2
−
a
n
)(
2
2
a
n
−
1
+
2
−
2
a
n
−
1
)
−
2
+
1
2
=
2
a
n
+
2
a
n
−
1
+
2
−
a
n
−
2
a
n
−
1
+
2
2
a
n
−
1
−
a
n
+
2
a
n
−
2
a
n
−
1
−
2
−
2
−
1
.
We have only to consider the equalities
a
n
+
2
a
n
−
1
=
a
n
+
1
,
2
a
n
−
1
−
a
n
=
(
−
1
)
n
,
5.2. Mathematical Induction
283
which are easy to check. Hence, we obtain the general formula
u
n
=
2
2
n
−
(
−
1
)
n
3
+
1
2
2
n
−
(
−
1
)
n
3
,
for all
n
≥
1
.
The required result,
u
n
=
2
2
n
−
(
−
1
)
n
3
,
is now obvious.
Second solution.
We have
u
0
≥
2,
u
1
≥
5
2
. We prove by induction that
u
n
≥
5
2
,
for all
n
≥
1
.
u
n
+
1
=
u
n
(
u
2
n
−
1
−
2
)
−
5
2
≥
5
2
25
4
−
2
−
5
2
=
5
2
25
4
−
3
>
5
2
.
The equation
x
+
1
x
=
u
n
has a unique real solution
x
n
, with
x
n
>
1. Indeed, write the equation in the form
x
2
−
u
n
x
+
1
=
0
,
and we observe that
=
u
2
n
−
4
≥
25
4
−
4
>
0. The equation has two positive
real solutions, only one being greater than 1.
Therefore, there exists a unique real sequence
(
x
n
)
n
≥
1
such that
x
n
>
1 and
x
n
+
1
x
n
=
u
n
.
Put this formula in the definition for
u
n
+
1
and obtain
x
n
+
1
+
1
x
n
+
1
=
x
n
x
2
n
−
1
+
1
x
n
x
2
n
−
1
+
x
n
x
2
n
−
1
+
x
2
n
−
1
x
n
−
5
2
.
We claim that the sequence
(
x
n
)
n
≥
1
is uniquely defined by the conditions
x
n
+
1
=
x
n
x
2
n
−
1
,
(1)
x
n
+
1
x
2
n
−
1
=
2
(
−
1
)
n
−
1
.
(2)
Actually, from condition (1) and
x
1
=
2,
x
2
=
2 we deduce
x
3
=
2
1
+
2
=
2
3
,
x
4
=
2
1
+
2
·
2
1
·
2
=
2
5
,
and generally,
x
n
=
2
2
n
−
(
−
1
)
n
3
. After that, the solution follows as in the first part.
284
II Solutions, 5. Basic Principles in Number Theory
5.3
Infinite Descent
Problem 5.3.2.
Find all primes p for which there exist positive integers x
,
y, and
n such that p
n
=
x
3
+
y
3
.
(2000 Hungarian Mathematical Olympiad)
Solution.
Observe that 2
1
=
1
3
+
1
3
and 3
2
=
2
3
+
1
3
. We will prove that
the only answers are
p
=
2 and
p
=
3. Assume by contradiction that there
exists
p
≥
5 such that
p
n
=
x
3
+
y
3
with
x
,
y
,
n
positive integers and
n
of
the smallest possible value. Hence at least one of
x
and
y
is greater than 1. We
have
x
3
+
y
3
=
(
x
+
y
)(
x
2
−
x y
+
y
2
)
with
x
+
y
≥
3 and
x
2
−
x y
+
y
2
=
(
x
−
y
)
2
+
x y
≥
2. It follows that both
x
+
y
and
x
2
−
x y
+
y
2
are divisible by
p
. Therefore
(
x
+
y
)
2
−
(
x
2
−
x y
+
y
2
)
=
3
x y
is also divisible by
p
. However,
3 is not divisible by
p
, so at least one of
x
and
y
must be divisible by
p
. Since
x
+
y
is divisible by
p
, both
x
and
y
are divisible by
p
. Then
x
3
+
y
3
≥
2
p
3
and
necessarily
n
>
3. We obtain
p
n
−
3
=
p
n
p
3
=
x
3
p
3
+
y
3
p
3
=
x
p
3
+
y
p
3
,
and this contradicts the minimality of
n
(see the remark after FMID Variant 1,
Do'stlaringiz bilan baham: |
