|
I Fundamentals, 5. Basic Principles in Number Theory
Problem 5.2.10.
Find all positive integers
n
such that
n
=
m
k
=
0
(
a
k
+
1
),
where
a
m
a
m
−
1
· · ·
a
0
is the decimal representation of
n
.
(2001 Japanese Mathematical Olympiad)
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)
5.3
Infinite Descent
Fermat
1
was the first mathematician to use a method of proof called
infinite de-
scent
.
Let
P
be a property concerning the nonnegative integers and let
(
P
(
n
))
n
≥
1
be
the sequence of propositions
P
(
n
)
: “
n
satisfies property
P
.”
The following method is useful in proving that proposition
P
(
n
)
is false for
all large enough
n
.
Let k be a nonnegative integer. Suppose that:
•
P
(
k
)
is not true;
•
if P
(
m
)
is true for a positive integer m
>
k, then there is some smaller j ,
m
>
j
≥
k, for which P
(
j
)
is true.
Then P
(
n
)
is false for all n
≥
k.
This is just the contrapositive of strong induction, applied to the negation of
proposition
P
(
n
)
. In the language of the ladder metaphor, if you know you cannot
reach any rung without first reaching a lower rung, and you also know you cannot
reach the bottom rung, then you cannot reach any of the rungs.
The above is often called the
finite descent method
.
Fermat’s method of infinite descent
(FMID) can be formulated as follows:
Let k be an integer. Suppose that:
1
Pierre de Fermat (1601–1665), French lawyer and government official most remembered for his
work in number theory, in particular for Fermat’s last theorem. He is also important in the foundations
of calculus, optics, and geometry.
5.4. Inclusion–Exclusion
99
•
if P
(
m
)
is true for an integer m
>
k, then there must be some smaller
integer j , m
>
j
>
k for which P
(
j
)
is true.
Then P
(
n
)
is false for all n
>
k.
That is, if there were an
n
for which
P
(
n
)
were true, one could construct a
sequence
n
>
n
1
>
n
2
>
· · ·
all of which would be greater than
k
. However, for
the integers, no such sequence is possible.
Two special cases of FMID are particularly useful in solving number theory
problems.
FMID Variant 1.
There is no sequence of nonnegative integers n
1
>
n
2
>
· · ·
.
In some situations it is convenient to replace FMID Variant 1 by the following
equivalent form: If
n
0
is the smallest integer
n
for which
P
(
n
)
is true, then
P
(
n
)
is false for all
n
<
n
0
. In fact, this is equivalent to an extremal argument.
FMID Variant 2.
If the sequence of integers
(
n
i
)
i
≥
1
satisfies the inequalities
n
1
≥
n
2
≥ · · ·
, then there exists i
0
such that n
i
0
=
n
i
0
+
1
= · · ·
.
Problem 5.3.1.
Find all triples
(
x
,
y
,
z
)
of nonnegative integers such that
x
3
+
2
y
3
=
4
z
3
.
Solution.
Note that (0
,
0
,
0) is such a triple. We will prove that there is no other.
Assume that
(
x
1
,
y
1
,
z
1
)
is a nontrivial solution to the given equation. Because
3
√
2,
3
√
4 are both irrational, it is not difficult to see that
x
1
>
0,
y
1
>
0,
z
1
>
0.
From
x
3
1
+
2
y
3
1
=
4
z
3
1
it follows that 2
|
x
1
, so
x
1
=
2
x
2
,
x
2
∈
Z
+
. Then
4
x
3
2
+
y
3
1
=
2
z
3
1
; hence
y
1
=
2
y
2
,
y
2
∈
Z
+
. Similarly,
z
1
=
2
z
2
,
z
2
∈
Z
+
. We
obtain the “new” solution
(
x
2
,
y
2
,
z
2
)
with
x
1
>
x
2
,
y
1
>
y
2
,
z
1
>
z
2
. Continuing
this procedure, we construct a sequence of positive integral triples
(
x
n
,
y
n
,
z
n
)
n
≥
1
such that
x
1
>
x
2
>
x
3
>
· · ·
. But this contradicts FMID Variant 1.
Additional Problems
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)
5.4
Inclusion–Exclusion
The main result in this section is contained in the following theorem.
100
I Fundamentals, 5. Basic Principles in Number Theory
Theorem 5.4.1.
Let S
1
,
S
2
, . . . ,
S
n
be finite sets. Then
n
3
i
=
1
S
i
=
n
i
=
1
|
S
i
| −
1
≤
i
<
j
≤
n
|
S
i
∩
S
j
|
+
1
≤
i
<
j
<
k
≤
n
|
S
i
∩
S
j
∩
S
k
| − · · · +
(
−
1
)
n
−
1
n
4
i
=
1
S
i
,
where
|
S
|
denotes the number of elements in S and n
≥
2
.
Proof.
We proceed by induction. For
n
=
2, we have to prove that
|
S
1
∪
S
2
| =
|
S
1
| + |
S
2
| − |
S
1
∩
S
2
|
. This is clear because the number of elements in
S
1
∪
S
2
is the number of elements in
S
1
and
S
2
less the ones in
S
1
∩
S
2
, since the latter
elements were counted twice.
The inductive step uses the formula above for
S
1
→
5
k
i
=
1
S
k
and
S
2
→
S
k
+
1
.
The formula in the theorem is called the
inclusion–exclusion principle
.
Example.
How many positive integers not exceeding
1000
are divisible by
2
, or
3
, or
5
?
Solution.
Consider the sets
S
1
= {
2
m
:
1
≤
m
≤
500
}
,
S
2
= {
3
n
:
1
≤
n
≤
333
}
,
S
3
= {
5
p
:
1
≤
p
≤
200
}
.
Then
S
1
∩
S
2
= {
6
q
:
1
≤
q
≤
166
}
,
S
1
∩
S
3
= {
10
r
:
1
≤
r
≤
100
}
,
S
2
∩
S
3
= {
15
s
:
1
≤
s
≤
66
}
,
and
S
1
∩
S
2
∩
S
3
= {
30
u
:
1
≤
u
≤
33
}
.
Applying the inclusion–exclusion principle, we obtain
|
S
1
∪
S
2
∪
S
3
| = |
S
1
| + |
S
2
| + |
S
3
| − |
S
1
∩
S
2
| − |
S
1
∩
S
3
|
− |
S
2
∩
S
3
| + |
S
1
∩
S
2
∩
S
3
|
=
500
+
333
+
200
−
166
−
100
−
66
+
33
=
734
.
The dual version of Theorem 5.4.1 is the following:
Theorem 5.4.2.
Let S
1
,
S
2
, . . . ,
S
n
be subsets of the finite set S and let S
i
=
S
−
S
i
be the complementary set of S
i
, i
=
1
,
2
, . . . ,
n. Then
n
4
i
=
1
S
i
= |
S
| −
n
i
=
1
|
S
i
| +
1
≤
i
<
j
≤
n
|
S
i
∩
S
j
|
−
1
≤
i
<
j
<
k
≤
n
|
S
i
∩
S
j
∩
S
k
| + · · · +
(
−
1
)
n
n
4
i
=
1
S
i
.
Do'stlaringiz bilan baham: |
