|
I Fundamentals, 5. Basic Principles in Number Theory
(2) (Erd˝os) Given
n
+
1 distinct positive integers
m
1
,
m
2
, . . . ,
m
n
+
1
not ex-
ceeding 2
n
, prove that there are two of them,
m
i
and
m
j
, such that
m
i
|
m
j
.
Indeed, for each
s
∈ {
1
,
2
, . . . ,
n
}
write
m
s
=
2
e
s
q
s
, where
e
s
is a non-
negative integer and
q
s
is an odd positive integer. Because
q
1
,
q
2
, . . . ,
q
n
+
1
∈
{
1
,
2
, . . . ,
2
n
}
and the set
{
1
,
2
, . . . ,
2
n
}
has exactly
n
odd elements, it follows
that
q
i
=
q
j
for some
i
and
j
. Without loss of generality, assume that
e
i
<
e
j
.
Then
m
i
|
m
j
, as desired.
Problem 5.1.4.
Prove that among any integers a
1
,
a
2
, . . . ,
a
n
, there are some
whose sum is a multiple of n.
Solution.
Let
s
1
=
a
1
,
s
2
=
a
1
+
a
2
, . . .
,
s
n
=
a
1
+
a
2
+ · · · +
a
n
. If at least
one of the integers
s
1
,
s
2
, . . . ,
s
n
is divisible by
n
, then we are done. If not, there
are
n
−
1 possible remainders when
s
1
,
s
2
, . . . ,
s
n
are divided by
n
. It follows that
s
i
≡
s
j
(
mod
n
)
for some
i
and
j
,
i
<
j
. Then
s
j
−
s
i
=
a
i
+
1
+ · · · +
a
j
is a
multiple of
n
(see also Example (1) above).
Problem 5.1.5.
In a
10
×
10
table are written natural numbers not exceeding
10
.
Every pair of numbers that appear in adjacent or diagonally adjacent spaces of
the table are relatively prime. Prove that some number appears in the table at
least
17
times.
(2001 St. Petersburg City Mathematical Olympiad)
Solution.
In any 2
×
2 square, only one of the numbers can be divisible by 2 and
only one can be divisible by 3, so if we tile the table with these 2
×
2 squares,
at most 50 of the numbers in the table are divisible by 2 or 3. The remaining 50
numbers must be divided among the integers not divisible by 2 or 3, and thus
the only ones available are 1, 5, and 7. By the pigeonhole principle, one of these
numbers appears at least 17 times.
Problem 5.1.6.
Prove that from any set of
117
distinct three-digit numbers, it is
possible to select
4
pairwise disjoint subsets such that the sums of the numbers in
each subset are equal.
(2001 Russian Mathematical Olympiad)
Solution.
We examine subsets of exactly two numbers. Clearly, if two distinct
subsets have the same sum, they must be disjoint. The number of two-element
subsets is
117
2
=
6786. Furthermore, the lowest attainable sum is 100
+
101
=
201, while the highest sum is 998
+
999
=
1997, for a maximum of 1797 different
sums. By the pigeonhole principle and the fact that 1797
·
3
+
1
=
5392
<
6786,
we see that there are four two-element subsets with the required property.
Additional Problems
Problem 5.1.7.
Let
n
1
<
n
2
<
· · ·
<
n
2000
<
10
100
be positive integers. Prove
that one can find two nonempty disjoint subsets
A
and
B
of
{
n
1
,
n
2
, . . . ,
n
2000
}
5.2. Mathematical Induction
93
such that
|
A
| = |
B
|
,
x
∈
A
x
=
x
∈
B
x
,
and
x
∈
A
x
2
=
x
∈
B
x
2
.
(2001 Polish Mathematical Olympiad)
Problem 5.1.8.
Find the greatest positive integer
n
for which there exist
n
nonneg-
ative integers
x
1
,
x
2
, . . . ,
x
n
, not all zero, such that for any sequence
ε
1
, ε
2
, . . . , ε
n
of elements
{−
1
,
0
,
1
}
, not all zero,
n
3
does not divide
ε
1
x
1
+
ε
2
x
2
+ · · · +
ε
n
x
n
.
(1996 Romanian Mathematical Olympiad)
Problem 5.1.9.
Given a positive integer
n
, prove that there exists
ε >
0 such that
for any
n
positive real numbers
a
1
,
a
2
, . . . ,
a
n
, there exists a real number
t
>
0
such that
ε <
{
ta
1
}
,
{
ta
2
}
, . . . ,
{
ta
n
}
<
1
2
.
(1998 St. Petersburg City Mathematical Olympiad)
Problem 5.1.10.
We have 2
n
prime numbers written on the blackboard in a line.
We know that there are fewer than
n
different prime numbers on the blackboard.
Prove that there is a subsequence of numbers in that line whose product is a perfect
square.
Problem 5.1.11.
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 5.1.12.
Prove that among seven arbitrary perfect squares there are two
whose difference is divisible by 20.
(Mathematical Reflections)
5.2
Mathematical Induction
Mathematical induction is a powerful and elegant method for proving statements
depending on nonnegative integers.
Let
(
P
(
n
))
n
≥
0
be a sequence of propositions. The method of mathematical
induction assists us in proving that
P
(
n
)
is true for all
n
≥
n
0
, where
n
0
is a given
nonnegative integer.
Mathematical Induction
(weak form):
Suppose that:
•
P
(
n
0
)
is true;
•
For all k
≥
n
0
, P
(
k
)
is true implies P
(
k
+
1
)
is true.
Then P
(
n
)
is true for all n
≥
n
0
.
94
I Fundamentals, 5. Basic Principles in Number Theory
Mathematical Induction
(with step
s
):
Let s be a fixed positive integer. Suppose
that:
•
P
(
n
0
),
P
(
n
0
+
1
), . . . ,
P
(
n
0
+
s
−
1
)
are true;
•
For all k
≥
n
0
, P
(
k
)
is true implies P
(
k
+
s
)
is true.
Then P
(
n
)
is true for all n
≥
n
0
.
Mathematical Induction
(strong form):
Suppose that
•
P
(
n
0
)
is true;
•
For all k
≥
n
0
, P
(
m
)
is true for all m with n
0
≤
m
≤
k implies P
(
k
+
1
)
is true.
Then P
(
n
)
is true for all n
≥
n
0
.
This method of proof is widely used in various areas of mathematics, includ-
ing number theory.
Problem 5.2.1.
Prove that for any integer n
≥
2
, there exist positive integers
a
1
,
a
2
, . . . ,
a
n
such that a
j
−
a
i
divides a
i
+
a
j
for
1
≤
i
<
j
≤
n.
(Kvant)
Solution.
We will prove the statement by induction on the number of terms
n
. For
n
=
2, we can choose
a
1
=
1 and
a
2
=
2.
We assume that we can find integers
a
1
,
a
2
, . . . ,
a
n
such that
a
j
−
a
i
divides
a
i
+
a
j
for 1
≤
i
<
j
≤
n
, where
n
is a positive integer greater than 1. Let
m
be the
least common multiple of numbers
a
1
,
a
2
, . . . ,
a
n
,
a
j
−
a
i
, for all 1
≤
i
<
j
≤
n
.
Then
(
a
1
,
a
2
,
a
3
, . . . ,
a
n
+
1
)
=
(
m
,
m
+
a
1
,
m
+
a
2
, . . . ,
m
+
a
n
)
is an (
n
+
1)-term sequence satisfying the conditions of the problem. Indeed,
a
i
−
a
1
=
a
i
−
1
divides
m
and
a
i
+
a
1
=
2
m
+
a
i
−
1
by the definition of
m
, and
a
j
−
a
i
=
a
j
−
1
−
a
i
−
1
(
2
≤
i
<
j
≤
n
+
1
)
divides
m
. Also,
a
j
+
a
i
=
2
m
+
(
a
j
−
1
+
a
i
−
1
)
by the definition of
m
and by the inductive hypothesis. Therefore
our induction is complete.
Problem 5.2.2.
Prove that for each n
≥
3
, the number n
!
can be represented as
the sum of n distinct divisors of itself.
(Erd˝os)
Solution.
The base case is 3
! =
6
=
1
+
2
+
3. Strengthening the statement by
imposing the condition that one of the
n
divisors should be 1 puts us in a winning
position. The question here is how we came to think of this. Indeed, there is just
about one way to go in using the induction hypothesis
n
! =
d
1
+
d
2
+ · · · +
d
n
Do'stlaringiz bilan baham: |
