|
II Solutions, 1. Divisibility
Problem 1.1.19.
Find the smallest positive integer k such that every k-element
subset of
{
1
,
2
, . . . ,
50
}
contains two distinct elements a
,
b such that a
+
b divides
ab.
(1996 Chinese Mathematical Olympiad)
Solution.
The minimal value is
k
=
39. Suppose
a
,
b
∈
S
are such that
a
+
b
divides
ab
. Let
c
be the greatest common divisor of
a
and
b
, and put
a
=
ca
1
,
b
=
cb
1
, so that
a
1
and
b
1
are relatively prime. Then
c
(
a
1
+
b
1
)
divides
c
2
a
1
b
1
,
so
a
1
+
b
1
divides
ca
1
b
1
. Since
a
1
and
b
1
have no common factor, neither do
a
1
and
a
1
+
b
1
, or
b
1
and
a
1
+
b
1
. In short,
a
1
+
b
1
divides
c
.
Since
S
⊆ {
1
, . . . ,
50
}
, we have
a
+
b
≤
99, so
c
(
a
1
+
b
1
)
≤
99, which
implies
a
1
+
b
1
≤
9; on the other hand, of course
a
1
+
b
1
≥
3. An exhaustive
search produces 23 pairs
a
,
b
satisfying the condition:
a
1
+
b
1
=
3
(
6
,
3
), (
12
,
6
), (
18
,
9
), (
24
,
12
),
(
30
,
15
), (
36
,
18
), (
42
,
21
), (
48
,
24
)
a
1
+
b
1
=
4
(
12
,
4
), (
24
,
8
), (
36
,
12
), (
48
,
16
)
a
1
+
b
1
=
5
(
20
,
5
), (
40
,
10
), (
15
,
10
), (
30
,
20
), (
45
,
30
)
a
1
+
b
1
=
6
(
30
,
6
)
a
1
+
b
1
=
7
(
42
,
7
), (
35
,
14
), (
28
,
21
)
a
1
+
b
1
=
8
(
40
,
24
)
a
1
+
b
1
=
9
(
45
,
36
)
The twelve pairs
(
3
,
6
), (
4
,
12
), (
5
,
20
), (
7
,
42
), (
8
,
24
), (
9
,
18
), (
10
,
40
)
,
(
14
,
35
), (
16
,
48
), (
15
,
30
), (
21
,
28
)
and
(
36
,
45
)
are disjoint. Hence any 39-ele-
ment subset must contain one of these pairs and hence two elements
a
and
b
with
a
+
b
|
ab
. Conversely, the 12-element set
{
6
,
10
,
12
,
18
,
20
,
21
,
24
,
30
,
35
,
42
,
45
,
48
}
meets every pair on the list, so
{
1
,
2
, . . . ,
50
} \ {
6
,
10
,
12
,
18
,
20
,
21
,
24
,
30
,
35
,
42
,
45
,
48
}
is a 38-element set without this property.
1.2
Prime Numbers
Problem 1.2.10.
For each integer n such that n
=
p
1
p
2
p
3
p
4
, where p
1
,
p
2
,
p
3
,
p
4
are distinct primes, let
d
1
=
1
<
d
2
<
d
3
<
· · ·
<
d
16
=
n
be the sixteen positive integers that divide n. Prove that if n
<
1995
, then d
9
−
d
8
=
22
.
(1995 Irish Mathematical Olympiad)
1.2. Prime Numbers
221
Solution.
Note that 35
·
57
=
1995
=
2
·
3
·
7
·
19. Suppose that
n
<
1995 and
d
9
−
d
8
=
22; then
d
8
d
9
=
n
, so
d
8
<
35. Moreover,
d
8
cannot be even, since
that would make
n
divisible by 4, whereas
n
has distinct prime factors. Hence
d
8
,
d
9
, and
n
are odd.
The divisors
d
1
, . . . ,
d
8
each are the product of distinct odd primes, since they
divide
n
. Since 3
·
5
·
7
>
35, none of
d
1
, . . . ,
d
8
is large enough to have three odd
prime factors, so each is either prime or the product of two primes. Since
n
has
only four prime factors, four of the
d
i
must be the product of two odd primes. But
the smallest such numbers are
15
,
21
,
33
,
35
, . . . .
Assume that
p
1
<
p
2
<
p
3
<
p
4
. If
d
8
=
p
1
p
4
, then clearly
d
8
=
15 and
d
8
=
21. Moreover, if
d
8
=
33, then
p
1
=
3 and
p
4
=
11; hence
p
2
=
5 and
p
3
=
7, and we get
d
9
=
p
2
p
3
=
35, giving the difference
d
9
−
d
8
=
2, which is
not possible. If
d
8
=
p
3
p
4
, then
d
8
=
15,
d
8
=
21, and
d
8
=
33, since
p
3
>
3.
In both situations we must have
d
8
≥
35, contrary to assumption.
Problem 1.2.11.
Prove that there are infinitely many positive integers a such that
the sequence
(
z
n
)
n
≥
1
, z
n
=
n
4
+
a, does not contain any prime number.
(11th International Mathematical Olympiad)
Solution.
To consider all positive integers of the form
n
4
+
a
,
n
≥
1, means to
consider all values of the polynomial
P
(
X
)
=
X
4
+
a
in the positive integers. A
decomposition of the polynomial
P
(
X
)
gives us decompositions of the numbers
n
4
+
a
, except in the case of factors taking the value 1.
The polynomial
P
(
X
)
can have a decomposition in integer polynomials only
into quadratic factors:
P
(
X
)
=
(
X
2
+
m X
+
n
)(
X
2
+
m
X
+
n
).
Such a decomposition is possible if and only if
m
+
m
=
0
,
mm
+
n
+
n
=
0
,
mn
+
m
n
=
0 and
nn
=
a
.
We obtain
m
= −
m
,
n
=
n
,
m
2
−
2
n
=
0, and
n
2
=
a
.
The third equation forces
m
to be even. Taking
m
= −
m
=
2
k
gives
n
=
n
=
2
k
2
and
a
=
4
k
4
. The corresponding factorization is
X
4
+
4
k
4
=
(
X
2
−
2
k X
+
2
k
2
)(
X
2
+
2
k X
+
2
k
2
)
. For
k
≥
2, these factors are
X
2
±
2
k X
+
2
k
2
=
(
X
±
k
)
2
+
k
2
≥
k
2
,
hence are nontrivial and
X
4
+
4
k
4
is composite.
For the record, this is the third problem to use this factorization.
222
II Solutions, 1. Divisibility
Problem 1.2.12.
Let p
,
q
,
r be distinct prime numbers and let A be the set
A
= {
p
a
q
b
r
c
:
0
≤
a
,
b
,
c
≤
5
}
.
Find the smallest integer n such that any n-element subset of A contains two
distinct elements x
,
y such that x divides y.
(1997 Romanian Mathematical Olympiad)
Solution.
Define an order relation on
A
by setting
p
a
q
b
r
c
≤
p
a
1
q
b
1
r
c
1
iff
a
≤
a
1
,
b
≤
b
1
,
c
≤
c
1
. Thus, we must find the longest antichain with respect to this
relation, that is, the maximal number
m
such that there is
B
⊂
A
with
|
B
| =
m
and no two elements of
B
are comparable. The answer will then be
n
=
m
+
1.
From now on, identify
p
a
q
b
r
c
with
(
a
,
b
,
c
)
and regard it as a lattice point in
R
3
. One can easily check that the set
B
= {
(
a
,
b
,
c
)
|
a
,
b
,
c
∈ {
0
,
1
, . . . ,
5
}
,
a
+
b
+
c
=
8
}
has 27 elements and that it is an antichain. We will prove that any set with 28 el-
ements contains two comparable elements. Of course, it suffices to find 27 chains
that partition
{
(
a
,
b
,
c
)
|
0
≤
a
,
b
,
c
≤
5
}
and such that each chain has a unique
representation from
B
. Take
A
= {
(
a
,
b
)
|
0
≤
a
,
b
≤
5
}
and partition it into six
chains (draw a picture!)
A
1
= {
(
0
,
0
), (
0
,
1
), . . . , (
0
,
5
), (
1
,
5
), . . . , (
5
,
5
)
}
,
A
2
= {
(
1
,
0
), (
1
,
1
), . . . , (
1
,
4
), (
2
,
4
), . . . , (
5
,
4
)
}
,
A
3
= {
(
2
,
0
), (
2
,
1
), . . . , (
2
,
3
), (
3
,
3
), . . . , (
5
,
3
)
}
,
A
4
= {
(
3
,
0
), (
3
,
1
), (
3
,
2
), (
4
,
2
), (
5
,
2
)
}
,
A
5
= {
(
4
,
0
), (
4
,
1
), (
5
,
1
)
}
,
A
6
= {
(
5
,
0
)
}
.
Next define
A
1
j
= {
(
a
,
b
,
j
)
|
(
a
,
b
)
∈
A
1
}
and similarly for
A
2
,
A
3
. We
have found 18 chains so far.
For
(
a
,
b
)
∈
A
4
∪
A
5
∪
A
6
we define the chain
A
(
a
,
b
)
= {
(
a
,
b
,
j
)
|
0
≤
j
≤
5
}
, and we have 9 chains, for a total of 27 chains.
Problem 1.2.13.
Prove Bonse’s inequality:
p
1
p
2
· · ·
p
n
>
p
2
n
+
1
for n
≥
4
, where p
1
=
2
, p
2
=
3
, . . .
is the increasing sequence of prime
numbers.
Do'stlaringiz bilan baham: |
