|
1.4. Odd and Even
231
Solution.
The solution is any pair of the form
(
m
, (
2
k
+
1
)
m
)
, where
k
is any
nonnegative integer, i.e.,
n
must be an odd multiple of
m
.
Call
x
i
=
(
−
1
)
i
a
(
2
k
−
i
)
m
b
i m
=
a
2
km
r
i
, where
k
is any nonnegative integer,
and
r
= −
b
a
m
. Clearly, the sum of all
x
i
for
i
=
0
,
1
,
2
, . . . ,
2
k
is an integer,
and
2
k
i
=
0
x
i
=
a
2
km
2
k
i
=
0
r
i
=
a
2
km
1
−
r
2
k
+
1
1
−
r
=
a
(
2
k
+
1
)
m
+
b
(
2
k
+
1
)
m
a
m
+
b
m
.
Thus
a
m
+
b
m
divides
a
n
+
b
n
for all
n
=
(
2
k
+
1
)
m
, where
k
is any nonnegative
integer. We prove that these are the only possible values of
n
.
Note that if
a
and
b
are relatively prime, then so are
a
m
+
b
m
and
ab
. Let us
assume that for some integer
n
such that
m
<
n
≤
2
m
,
a
m
+
b
m
divides
a
n
+
b
n
.
Now,
(
a
m
+
b
m
)(
a
n
−
m
+
b
n
−
m
)
−
(
a
n
+
b
n
)
=
(
ab
)
n
−
m
(
a
2
m
−
n
+
b
2
m
−
n
),
so
a
m
+
b
m
must divide
a
2
m
−
n
+
b
2
m
−
n
, since it is relatively prime to
(
ab
)
n
−
m
.
But this is absurd, since 2
m
−
n
<
m
. So the only
n
such that 0
≤
m
≤
2
m
−
1
and
a
m
+
b
m
divides
a
n
+
b
n
is
n
=
m
. Let us complete our proof by showing
by induction that for all nonnegative integers
k
, if
n
=
2
mk
+
d
, where 0
≤
d
≤
2
m
−
1, then
a
m
+
b
m
divides
d
=
m
. The result is already proved for
k
=
0. Let
us assume it true for some
k
−
1. Then
(
a
m
+
b
m
)
a
(
2
k
−
1
)
m
+
d
+
b
(
2
k
−
1
)
m
+
d
−
(
ab
)
m
a
2
(
k
−
1
)
m
+
d
+
b
2
(
k
−
1
)
m
+
d
=
a
2
km
+
d
+
b
2
km
+
d
=
a
n
+
b
n
.
If
a
m
+
b
m
divides
a
n
+
b
n
, since
a
m
+
b
m
is prime to
(
ab
)
m
, then
a
m
+
b
m
must
also divide
a
2
(
k
−
1
)
m
+
d
+
b
2
(
k
−
1
)
m
+
d
. But by the induction hypothesis,
d
=
m
,
and we are done.
1.4
Odd and Even
Problem 1.4.5.
We are given three integers a
,
b
,
c such that a
,
b
,
c, a
+
b
−
c,
a
+
c
−
b, b
+
c
−
a, and a
+
b
+
c are seven distinct primes. Let d be the
difference between the largest and smallest of these seven primes. Suppose that
800
∈ {
a
+
b
,
b
+
c
,
c
+
a
}
. Determine the maximum possible value of d.
Solution.
Answer: 1594.
First, observe that
a
,
b
,
c
must all be odd primes; this follows from the as-
sumption that the seven quantities listed are distinct primes and the fact that
there is only one even prime, 2. Therefore, the smallest of the seven primes is
232
II Solutions, 1. Divisibility
at least 3. Next, assume without loss of generality that
a
+
b
=
800. Because
a
+
b
−
c
>
0, we must have
c
<
800. We also know that
c
is prime; there-
fore, since 799
=
17
·
47, we have
c
≤
797. It follows that the largest prime,
a
+
b
+
c
, is no more than 1597. Combining these two bounds, we can bound
d
by
d
≤
1597
−
3
=
1594. It remains to observe that we can choose
a
=
13,
b
=
787,
c
=
797 to achieve this bound. The other four primes are then 3, 23, 1571, and
1597.
Problem 1.4.6.
Determine the number of functions f
: {
1
,
2
, . . . ,
n
} → {
1995
,
1996
}
that satisfy the condition that f
(
1
)
+
f
(
2
)
+ · · · +
f
(
1996
)
is odd.
(1996 Greek Mathematical Olympiad)
Solution.
We can send 1
,
2
, . . . ,
n
−
1 anywhere, and the value of
f
(
n
)
will then
be uniquely determined. Hence there are 2
n
−
1
such functions.
Problem 1.4.7.
Is it possible to place
1995
different natural numbers around a
circle so that for any two adjacent numbers, the ratio of the greatest to the least
is a prime?
(1995 Russian Mathematical Olympiad)
Solution.
No, this is impossible. Let
a
0
, . . . ,
a
1995
=
a
0
be the integers. Then for
i
=
1
, . . . ,
1995,
a
k
−
1
/
a
k
is either a prime or the reciprocal of a prime; suppose
the former occurs
m
times and the latter 1995
−
m
times. The product of all of
these ratios is
a
0
/
a
1995
=
1, but this means that the product of some
m
primes
equals the product of some 1995
−
m
primes. This can occur only when the primes
are the same (by unique factorization), and in particular there has to be the same
number on both sides. But
m
=
1995
−
m
is impossible, since 1995 is odd,
contradiction.
Problem 1.4.8.
Let a
,
b
,
c
,
d be odd integers such that
0
<
a
<
b
<
c
<
d and
ad
=
bc. Prove that if a
+
d
=
2
k
and b
+
c
=
2
m
for some integers k and m,
then a
=
1
.
(25th International Mathematical Olympiad)
Solution.
Since
ad
=
bc
, we have
a
((
a
+
d
)
−
(
b
+
c
))
=
(
a
−
b
)(
a
−
c
) >
0
.
Thus
a
+
d
>
b
+
c
, 2
k
>
2
m
, and
k
>
m
. Since
ad
=
a
(
2
k
−
a
)
=
bc
=
b
(
2
m
−
b
)
, we obtain
2
m
b
−
2
k
a
=
b
2
−
a
2
=
(
b
−
a
)(
b
+
a
).
By the equality 2
m
(
b
−
2
k
−
m
a
)
=
(
b
−
a
)(
b
+
a
)
, we infer that 2
m
|
(
b
−
a
)(
b
+
a
)
. But
b
−
a
and
b
+
a
differ by 2
a
, an odd multiple of 2, so either
b
−
a
1.5. Modular Arithmetic
233
or
b
+
a
is not divisible by 4. Hence, either 2
m
−
1
|
b
−
a
or 2
m
−
1
|
b
+
a
. But
0
<
b
−
a
<
b
<
2
m
−
1
, so it must be that 2
m
−
1
|
b
+
a
.
Since 0
<
b
+
a
<
b
+
c
=
2
m
, it follows that
b
+
a
=
2
m
−
1
and
b
=
2
m
−
1
−
a
.
Then
c
=
2
m
−
1
and
ad
=
bc
=
(
2
m
−
1
−
a
)(
2
m
−
1
+
a
)
.
From this equality we obtain
a
(
a
+
d
)
=
2
2
m
−
2
; hence
a
=
1.
Do'stlaringiz bilan baham: |
