|
partition
p
−
1 consecutive integers into two classes with equal product. This
problem is the particular case
p
=
7.
Problem 1.1.14.
The positive integers d
1
,
d
2
, . . . ,
d
n
are distinct divisors of
1995
.
Prove that there exist d
i
and d
j
among them such that the numerator of the re-
duced fraction d
i
/
d
j
is at least n.
(1995 Israeli Mathematical Olympiad)
1.1. Divisibility
217
Solution.
Note that 3
·
5
·
7
·
19
=
1995. If the chosen divisors include one divisible
by 19 and another not divisible by 19, the quotient of the two has numerator
divisible by 19, solving the problem since
n
≤
16. If this is not the case, either
all divisors are divisible by 19 or none of them has this property, and in particular
n
≤
8. Without loss of generality, assume that the divisors are all not divisible by
19.
Under this assumption, we are done if the divisors include one divisible by 7
and another not divisible by 7, unless
n
=
8. In the latter case all of the divisors
not divisible by 19 occur, including 1 and 3
·
5
·
7, so this case also follows. We
now assume that none of the chosen divisors is divisible by 4, so that in particular
n
≤
4.
Again, we are done if the divisors include one divisible by 5 and another not
divisible by 5. But this can fail to occur only if
n
=
1 or
n
=
2. The former case
is trivial, while in the latter case we simply divide the larger divisor by the smaller
one, and the resulting numerator has at least one prime divisor and so is at least 3.
Hence the problem is solved in all cases.
Problem 1.1.15.
Determine all pairs
(
a
,
b
)
of positive integers such that ab
2
+
b
+
7
divides a
2
b
+
a
+
b.
(39th International Mathematical Olympiad)
Solution.
From the divisibility
ab
2
+
b
+
7
|
a
2
b
+
a
+
b
we obtain
ab
2
+
b
+
7
|
b
(
a
2
b
+
a
+
b
)
−
a
(
ab
2
+
b
+
7
)
⇒
ab
2
+
b
+
7
|
b
2
−
7
a
.
When
b
2
−
7
a
=
0, it follows that
b
2
=
7
k
,
a
=
7
k
2
. Observe that all pairs
(
7
k
2
,
7
k
)
,
k
≥
1, are solutions to the problem.
Suppose
b
2
−
7
a
>
0. Then
ab
2
+
b
+
7
≤
b
2
−
7
a
, and we get a contradiction:
b
2
−
7
a
<
b
2
<
ab
2
+
b
+
7
.
Suppose
b
2
−
7
a
<
0. Then
ab
2
+
b
+
7
≤
7
a
−
b
2
. This is possible only for
b
2
<
7, i.e., either
b
=
1 or
b
=
2. If
b
=
1, we obtain
a
+
8
|
a
2
+
a
+
1, that
is,
a
+
8
|
a
(
a
+
8
)
−
7
(
a
+
8
)
+
57. Hence
a
+
8
|
57 and we get
a
+
8
=
19 or
a
+
8
=
49, so
a
=
11 or
a
=
49.
If
b
=
2, we obtain 4
a
+
9
|
a
+
22
⇒
4
a
+
9
≤
a
+
22
⇒
3
a
≤
13. This
case cannot give a solution.
Hence, the solutions of the problem are
(
7
k
2
,
7
k
)
,
(
11
,
1
)
, and
(
49
,
1
)
.
Problem 1.1.16.
Find all integers a
,
b
,
c with
1
<
a
<
b
<
c such that
(
a
−
1
)(
b
−
1
)(
c
−
1
)
is a divisor of abc
−
1
.
(33rd International Mathematical Olympiad)
218
II Solutions, 1. Divisibility
Solution.
It is convenient to define
a
−
1
=
x
,
b
−
1
=
y
, and
c
−
1
=
z
. Then
we have the conditions 1
≤
x
<
y
<
z
and
x yz
|
x y
+
yz
+
zx
+
x
+
y
+
z
.
The idea of the solution is to point out that we cannot have
x yz
≤
x y
+
yz
+
zx
+
x
+
y
+
z
for infinitely many triples
(
x
,
y
,
z
)
of positive integers. Let
f
(
x
,
y
,
z
)
be the quotient of the required divisibility.
From the algebraic form
f
(
x
,
y
,
z
)
=
1
x
+
1
y
+
1
z
+
1
x y
+
1
yz
+
1
zx
we can see that
f
is a decreasing function in one of the variables
x
,
y
,
z
. By
symmetry and because
x
,
y
,
z
are distinct numbers,
f
(
x
,
y
,
z
)
≤
f
(
1
,
2
,
3
)
=
2
+
5
6
<
3
.
Thus, if the divisibility is fulfilled we can have either
f
(
x
,
y
,
z
)
=
1 or
f
(
x
,
y
,
z
)
=
2. So, we have to solve in positive integers the equations
x y
+
yz
+
zx
+
x
+
y
+
z
=
kx yz
,
(
1
)
where
k
=
1 or
k
=
2.
Observe that
f
(
3
,
4
,
5
)
=
59
60
<
1. Thus
x
∈ {
1
,
2
}
. Also
f
(
2
,
3
,
4
)
=
35
24
<
2.
Thus, for
x
=
2, we necessarily have
k
=
1. The conclusion is that only three
equations have to be considered in (1).
Case 1.
x
=
1 and
k
=
1. We obtain the equation
1
+
2
(
y
+
z
)
+
yz
=
yz
.
It has no solutions.
Case 2.
x
=
1 and
k
=
2. We obtain the equation
1
+
2
(
y
+
z
)
=
yz
.
Write it in the form
(
y
−
2
)(
z
−
2
)
=
5 and obtain
y
−
2
=
1,
z
−
2
=
5. It
has a unique solution:
y
=
3,
z
=
7.
Case 3.
x
=
2 and
k
=
1. We obtain the equation
2
+
3
(
y
+
z
)
=
yz
.
By writing it in the form
(
y
−
3
)(
z
−
3
)
=
11, we obtain
y
−
3
=
1,
z
−
3
=
11.
Thus, it has a unique solution:
y
=
4,
z
=
15.
From Case 2 and Case 3 we obtain respectively
a
=
2,
b
=
4,
c
=
8 and
a
=
3,
b
=
5,
c
=
16. These are the solutions of the problem.
1.1. Divisibility
219
Problem 1.1.17.
Find all pairs of positive integers
(
x
,
y
)
for which
x
2
+
y
2
x
−
y
is an integer that divides
1995
.
(1995 Bulgarian Mathematical Olympiad)
Solution.
It is enough to find all pairs
(
x
,
y
)
for which
x
>
y
and
x
2
+
y
2
=
k
(
x
−
y
)
, where
k
divides 1995
=
3
·
5
·
7
·
19. We shall use the following well-
known fact: if
p
is prime of the form 4
q
+
3 and if it divides
x
2
+
y
2
then
p
divides
x
and
y
. (For
p
=
3, 7, 19 the last statement can be proved directly.) If
k
is divisible by 3, then
x
and
y
are divisible by 3 too. Simplifying by 9 we get an
equality of the form
x
2
1
+
y
2
1
=
k
1
(
x
1
−
y
1
)
, where
k
1
divides 5
·
7
·
19. Considering
7 and 19 analogously we get an equality of the form
a
2
+
b
2
=
5
(
a
−
b
)
, where
a
>
b
. (It is not possible to get an equality of the form
a
2
+
b
2
=
a
−
b
.) From
here
(
2
a
−
5
)
2
+
(
2
b
+
5
)
2
=
50, i.e.,
a
=
3,
b
=
1, or
a
=
2,
b
=
1. The above
consideration implies that the pairs we are looking for are of the form
(
3
c
,
c
)
,
(
2
c
,
c
)
,
(
c
,
3
c
)
,
(
c
,
2
c
)
, where
c
=
1
,
3
,
7
,
19
,
3
·
7
,
3
·
19
,
7
·
19
,
3
·
7
·
19.
Problem 1.1.18.
Find all positive integers
(
x
,
n
)
such that x
n
+
2
n
+
1
is a divisor
of x
n
+
1
+
2
n
+
1
+
1
.
(1998 Romanian International Mathematical Olympiad Team Selection Test)
Solution.
The solutions are
(
x
,
n
)
=
(
4
,
1
)
and (11,1). If
n
=
1, we need
x
+
3
=
x
+
2
+
1
|
x
2
+
4
+
1
=
x
2
+
5
=
(
x
+
3
)(
x
−
3
)
+
14, so
x
+
3 divides 14 and
x
=
4 or 11. Suppose
n
≥
2. For
x
∈ {
1
,
2
,
3
}
we have
1
+
2
n
+
1
<
1
+
2
n
+
1
+
1
<
2
(
1
+
2
n
+
1
),
2
n
+
2
n
+
1
<
2
n
+
1
+
2
n
+
1
+
1
<
2
(
2
n
+
2
n
+
1
),
2
(
3
n
+
2
n
+
1
) <
3
n
+
1
+
2
n
+
1
+
1
<
3
(
3
n
+
2
n
+
1
),
so
x
n
+
2
n
+
1 does not divide
x
n
+
1
+
2
n
+
1
+
1. For
x
≥
4,
x
n
=
x
n
/
2
+
x
n
/
2
≥
2
2
n
/
2
+
x
2
/
2, so
(
2
n
+
1
)
x
≤
((
2
n
+
1
)
2
+
x
2
)/
2
=
(
2
2
n
+
2
n
+
1
+
1
+
x
2
)/
2
<
2
n
+
1
+
x
n
+
2
n
+
2
.
Therefore
(
x
−
1
)(
x
n
+
2
n
+
1
)
=
x
n
+
1
+
2
n
x
+
x
−
x
n
−
2
n
−
1
<
x
n
+
1
+
2
n
+
1
+
1
<
x
(
x
n
+
2
n
+
1
)
;
again
x
n
+
2
n
+
1 does not divide
x
n
+
1
+
2
n
+
1
+
1. So the only solutions are
(
4
,
1
)
and
(
11
,
1
)
.
220
Do'stlaringiz bilan baham: |
