|
5
Basic Principles in Number Theory
5.1
Two Simple Principles
Problem 5.1.7.
Let n
1
<
n
2
<
· · ·
<
n
2000
<
10
100
be positive integers. Prove
that one can find two disjoint subsets A and B of
{
n
1
,
n
2
, . . . ,
n
2000
}
such that
|
A
| = |
B
|
,
x
∈
A
x
=
x
∈
B
x
,
and
x
∈
A
x
2
=
x
∈
B
x
2
.
(2001 Polish Mathematical Olympiad)
Solution.
Given any subset
S
⊆ {
n
1
,
n
2
, . . . ,
n
2000
}
of size 1000, we have
0
<
x
∈
S
x
<
1000
·
10
100
,
0
<
x
∈
S
x
2
<
1000
·
10
200
.
Thus, as
S
varies, there are fewer than
(
1000
·
10
100
)(
1000
·
10
200
)
=
10
306
values of
"
x
∈
S
x
,
"
x
∈
S
x
2
.
Because
"
2000
k
=
0
2000
k
=
2
2000
and
2000
1000
is the biggest term in the sum,
2000
1000
>
2
2000
2001
. There are
2000
1000
>
2
2000
2001
>
10
600
2001
>
10
306
distinct subsets of size 1000. By the pigeonhole principle, there exist distinct sub-
sets
C
and
D
of size 1000 such that
"
x
∈
C
x
2
=
"
x
∈
D
x
2
and
"
x
∈
C
x
=
"
x
∈
D
x
. Removing the common elements from
C
and
D
yields sets
A
and
B
with the required properties.
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_16,
275
276
II Solutions, 5. Basic Principles in Number Theory
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)
Solution.
The statement holds for
n
=
9 by choosing 1
,
2
,
2
2
, . . . ,
2
8
, since in
that case
|
ε
1
+ · · · +
ε
9
2
8
| ≤
1
+
2
+ · · · +
2
8
<
9
3
.
However, if
n
≥
10, then 2
10
>
10
3
, so by the pigeonhole principle, there are
two subsets
A
and
B
of
{
x
1
, . . . ,
x
10
}
whose sums are congruent modulo 10
3
. Let
ε
i
=
1 if
x
i
occurs in
A
but not in
B
,
−
1 if
x
i
occurs in
B
but not in
A
, and 0
otherwise; then
"
ε
i
x
i
is divisible by
n
3
.
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)
Solution.
More generally, we prove by induction on
n
that for any real number
0
<
r
<
1, there exists 0
< ε <
r
such that for
a
1
, . . . ,
a
n
any positive real
numbers, there exists
t
>
0 with
{
ta
1
}
, . . . ,
{
ta
n
} ∈
(ε,
r
).
The case
n
=
1 needs no further comment.
Assume without loss of generality that
a
n
is the largest of the
a
i
. By hypoth-
esis, for any
r
>
0 (which we will specify later) there exists
ε
>
0 such that for
any
a
1
, . . . ,
a
n
−
1
>
0, there exists
t
>
0 such that
{
t
a
1
}
, . . . ,
{
t
a
n
−
1
} ∈
(ε
,
r
).
Let
N
be an integer also to be specified later. A standard argument using the
pigeonhole principle shows that one of
t
a
n
,
2
t
a
n
, . . . ,
N t
a
n
has fractional part
in
(
−
1
/
N
,
1
/
N
)
. Let
st
a
n
be one such term, and take
t
=
st
+
c
for
c
=
(
r
−
1
/
N
)/
a
n
. Then
ta
n
−
st
s
n
∈
(
r
−
2
/
N
,
r
).
So we choose
N
such that 0
<
r
−
2
/
N
, thus making
{
ta
n
} ∈
(
r
−
2
/
N
,
r
)
.
Note that this choice of
N
makes
c
>
0 and
t
>
0, as well.
5.1. Two Simple Principles
277
As for the other
ta
i
, for each
i
we have
k
i
+
ε
<
t
a
i
<
k
i
+
r
for some
integer
k
i
, so
sk
i
+
s
ε
<
st
a
i
<
sk
i
+
sr
and
sk
i
+
ε
< (
st
+
c
)
a
i
<
sk
i
+
sr
+
a
i
(
r
−
1
/
N
)
a
n
≤
sk
i
+
N r
+
r
−
1
/
N
.
So we choose
r
such that
N r
−
1
/
N
<
0, thus making
{
ta
i
} ∈
(ε
,
r
)
.
Therefore, letting
ε
=
min
{
r
−
2
/
N
, ε
}
, we have
0
< ε <
{
ta
1
}
,
{
ta
2
}
, . . . ,
{
ta
n
}
<
r
for any choices of
a
i
. This completes the inductive step, and the claim is true for
all natural numbers
n
.
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 consecutive numbers in that line whose prod-
uct is a perfect square.
Solution.
Suppose that
p
1
,
p
2
, . . . ,
p
m
(
m
<
n
)
are primes that we met in the se-
quence
a
1
,
a
2
, . . . ,
a
2
n
written on the blackboard. It is enough to prove that there
is a subsequence in which each prime occurs an even number of times. Denote
by
c
i j
the exponent of the prime
p
i
(
1
≤
i
≤
m
)
in the product
a
1
· · ·
a
2
· · ·
a
j
of the first
j
numbers from our sequence. Let
d
i j
be the residue modulo 2 of
c
i j
,
so we can write
c
i j
=
2
t
i j
+
d
i j
,
d
i j
∈ {
0
,
1
}
. Every system
(
d
1
j
,
d
2
j
, . . . ,
d
m j
)
is formed from
m
zeros and ones. The number of possible such systems is 2
m
,
which is less than 2
n
. Hence by the pigeonhole principle there exist two identical
systems
(
d
1
k
,
d
2
k
, . . . ,
d
mk
)
=
(
d
1
l
,
d
2
l
, . . . ,
d
ml
),
1
≤
k
<
l
≤
2
n
.
We have
d
i k
=
d
il
for 1
≤
i
≤
m
, and therefore
c
il
−
c
i k
=
2
(
t
il
−
t
i k
)
+
(
d
il
−
d
i k
)
=
2
(
t
il
−
t
i k
),
and
c
il
−
c
i k
is divisible by 2 for 1
≤
i
≤
m
.
Thus the exponent of the
p
i
in the product
a
k
+
1
a
k
+
2
· · ·
a
l
=
a
1
a
2
···
a
l
a
1
a
2
···
a
k
is
equal to
c
il
−
c
i k
, so every number
p
i
has an even exponent in the product
a
k
+
1
a
k
+
2
· · ·
a
l
. Hence
a
k
+
1
a
k
+
2
· · ·
a
l
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
.
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
278
Do'stlaringiz bilan baham: |
