|
Problem 1.4.1.
Let m and n be integers m
≥
1
and n
>
1
. Prove that m
n
is the
sum of m odd consecutive integers.
Solution.
The equality
m
n
=
(
2
k
+
1
)
+
(
2
k
+
3
)
+ · · · +
(
2
k
+
2
m
−
1
)
is equivalent to
m
n
=
2
km
+
(
1
+
3
+ · · · +
2
m
−
1
)
or
m
n
=
2
km
+
m
2
. It follows that
k
=
m
(
m
n
−
2
−
1
)/
2, which is an integer
because
m
and
m
n
−
2
−
1 have different parities.
Problem 1.4.2.
Let n be a positive integer. Find the sum of all even numbers
between n
2
−
n
+
1
and n
2
+
n
+
1
.
Solution.
We have
n
2
−
n
+
1
=
n
(
n
−
1
)
+
1 and
n
2
+
n
+
1
=
n
(
n
+
1
)
+
1, both
odd numbers. It follows that the least even number to be considered is
n
2
−
n
+
2
and the greatest is
n
2
+
n
. The desired sum is
(
n
2
−
n
+
2
)
+
(
n
2
−
n
+
4
)
+ · · · +
(
n
2
+
n
−
2
)
+
(
n
2
+
n
)
=
(
n
2
−
n
)
+
2
+
(
n
2
−
n
)
+
4
+ · · · +
(
n
2
−
n
)
+
2
n
−
2
+
(
n
2
−
n
)
+
2
n
=
n
(
n
2
−
n
)
+
2
(
1
+
2
+ · · · +
n
)
=
n
3
−
n
2
+
n
2
+
n
=
n
3
+
n
.
Problem 1.4.3.
Let n be a positive integer and let
ε
1
, ε
2
, . . . , ε
n
∈ {−
1
,
1
}
be
such that
ε
1
ε
2
+
ε
2
ε
3
+ · · · +
ε
n
ε
1
=
0
. Prove that n is divisible by
4
.
(Kvant)
Solution.
The sum
ε
1
ε
2
+
ε
2
ε
3
+ · · · +
ε
n
ε
1
has
n
terms equal to 1 or
−
1, so
n
is
even, say
n
=
2
k
. It is clear that
k
of the terms in the sequence
ε
1
ε
2
, ε
2
ε
3
,. . . , ε
n
ε
1
28
I Fundamentals, 1. Divisibility
are equal to 1 and
k
of them are equal to
−
1. On the other hand, the product of
the terms in the sum is
(ε
1
ε
2
)(ε
2
ε
3
)
· · ·
(ε
n
ε
1
)
=
ε
2
1
ε
2
2
. . . ε
2
n
=
1
;
hence
(
+
1
)
k
(
−
1
)
k
=
1. That is,
k
is even and the conclusion follows.
Note that the result of this problem is sharp.
For any integer
n
=
4
m
there exist
ε
1
, ε
2
, . . . , ε
n
such that
ε
1
ε
2
+
ε
2
ε
3
+ · · · +
ε
n
ε
1
=
0
;
for example,
ε
1
=
ε
4
=
ε
5
=
ε
8
= · · · =
ε
4
m
−
3
=
ε
4
m
= +
1
,
ε
2
=
ε
3
=
ε
6
=
ε
7
= · · · =
ε
4
m
−
2
=
ε
4
m
−
1
= −
1
.
Problem 1.4.4.
A table of numbers with m rows and n columns has all entries
−
1
or
1
such that for each row and each column the product of entries is
−
1
. Prove
that m and n have the same parity.
Solution.
We compute the product
P
of the
m
·
n
entries in two ways, by rows
and by columns, respectively:
P
=
(
−
1
)(
−
1
)
· · ·
(
−
1
)
m
times
=
(
−
1
)
m
=
(
−
1
)
n
=
(
−
1
)(
−
1
)
· · ·
(
−
1
)
n
times
.
The conclusion now follows.
We show such a table for
m
=
3 and
n
=
5:
−
1
1
1
−
1
−
1
1
1
−
1
1
1
1
−
1
1
1
1
Remark.
If
m
and
n
have the same parity, then the number of tables with the
above property is 2
(
m
−
1
)(
n
−
1
)
.
Additional Problems
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
.
Problem 1.4.6.
Let
n
be an integer
≥
1996. 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)
1.5. Modular Arithmetic
29
Problem 1.4.7.
Is it possible to place 1995 different natural numbers around a
circle so that in each pair of these numbers, the ratio of the larger to the smaller is
a prime?
(1995 Russian Mathematical Olympiad)
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)
1.5
Modular Arithmetic
Let
a
,
b
,
n
be integers, with
n
=
0. We say that
a
and
b
are
congruent modulo
n
if
n
|
a
−
b
. We denote this by
a
≡
b
(
mod
n
)
. The relation “
≡
” on the set
Z
of integers is called the
congruence relation
. If
m
does not divide
a
−
b
, then
we say that integers
a
and
b
are not congruent modulo
n
and we write
a
≡
b
(
mod
n
)
. It is clear that if
a
is divided by
b
with remainder
r
, then
a
is congruent
to
r
modulo
b
. In this case
r
is called the
residue of a modulo b
. The following
properties can be directly derived:
(1)
a
≡
a
(
mod
n
)
(reflexivity).
(2) If
a
≡
b
(
mod
n
)
and
b
≡
c
(
mod
n
)
, then
a
≡
c
(
mod
n
)
(transitivity).
(3) If
a
≡
b
(
mod
n
)
, then
b
≡
a
(
mod
n
)
(symmetry).
(4) If
a
≡
b
(
mod
n
)
and
c
≡
d
(
mod
n
)
, then
a
+
c
≡
b
+
d
(
mod
n
)
and
a
−
c
≡
b
−
d
(
mod
n
)
.
(5) If
a
≡
b
(
mod
n
)
, then for any integer
k
,
ka
≡
kb
(
mod
n
)
.
(6) If
a
≡
b
(
mod
n
)
and
c
≡
d
(
mod
n
)
, then
ac
≡
bd
(
mod
n
)
.
(7) If
a
i
≡
b
i
(
mod
n
)
,
i
=
1
, . . . ,
k
, then
a
1
+· · ·+
a
k
≡
b
1
+· · ·+
b
k
(
mod
n
)
and
a
1
· · ·
a
k
≡
b
1
· · ·
b
k
(
mod
n
)
. In particular, if
a
≡
b
(
mod
n
)
, then for
any positive integer
k
,
a
k
≡
b
k
(
mod
n
)
.
(8) We have
a
≡
b
(
mod
m
i
)
,
i
=
1
, . . . ,
k
, if and only if
a
≡
b
(
mod lcm
(
m
1
, . . . ,
m
k
)).
In particular, if
m
1
, . . . ,
m
k
are pairwise relatively prime, then
a
≡
b
(
mod
m
i
)
,
i
=
1
, . . . ,
k
, if and only if
a
≡
b
(
mod
m
1
, . . . ,
m
k
)
.
30
Do'stlaringiz bilan baham: |
