|
3.1. General Problems
67
Problem 3.1.12.
Evaluate the difference between the numbers
2000
k
=
0
%
3
k
+
2000
3
k
+
1
&
and
2000
k
=
0
%
3
k
−
2000
3
k
+
1
&
.
Problem 3.1.13.
(a) Prove that there are infinitely many rational positive numbers
x
such that
{
x
2
} + {
x
} =
0
.
99
.
(b) Prove that there are no rational numbers
x
>
0 such that
{
x
2
} + {
x
} =
1
.
(2004 Romanian Mathematical Olympiad)
Problem 3.1.14.
Show that the fractional part of the number
√
4
n
2
+
n
is not
greater than 0.25.
(2003 Romanian Mathematical Olympiad)
Problem 3.1.15.
Prove that for every natural number
n
,
n
2
k
=
1
{
√
k
} ≤
n
2
−
1
2
.
(1999 Russian Mathematical Olympiad)
Problem 3.1.16.
The rational numbers
α
1
, . . . , α
n
satisfy
n
i
=
1
{
k
α
i
}
<
n
2
for every positive integer
k
.
(a) Prove that at least one of
α
1
, . . . , α
n
is an integer.
(b) Do there exist
α
1
, . . . , α
n
that satisfy, for every positive integer
k
,
n
i
=
1
{
k
α
i
} ≤
n
2
,
such that no
α
i
is an integer?
(2002 Belarusian Mathematical Olympiad)
68
I Fundamentals, 3. Floor Function and Fractional Part
3.2
Floor Function and Integer Points
The following results are helpful in proving many relations involving the floor
function.
Theorem 3.2.1.
Let a
,
b
,
c
,
d be nonnegative real numbers and let f
: [
a
,
b
] →
[
c
,
d
]
be a bijective increasing function.
Then
a
≤
k
≤
b
f
(
k
)
+
c
≤
k
≤
d
f
−
1
(
k
)
−
n
(
G
f
)
=
b
d
−
a
−
1
c
−
1
,
(
1
)
where k ranges over integers and n
(
G
f
)
is the number of points with integer
coordinates on the graph of f .
Proof.
Note that
x
is the number of integers in the interval
[
0
,
x
)
,
x
is the
number of integers in the interval
(
0
,
x
]
, and hence
x
+
1 is the number of
integers in the interval
[
0
,
x
]
.
For a bounded region
M
of the plane we denote by
n
(
M
)
the number of points
with nonnegative integral coordinates in
M
.
Since
f
is increasing and bijective, it is continuous. Hence we can consider
the following regions (see Figure 3.1):
M
1
= {
(
x
,
y
)
∈
R
2
|
a
≤
x
≤
b
,
0
≤
y
≤
f
(
x
)
}
,
M
2
= {
(
x
,
y
)
∈
R
2
|
c
≤
y
≤
d
,
0
≤
x
≤
f
−
1
(
y
)
}
,
M
3
= {
(
x
,
y
)
∈
R
2
|
0
≤
x
≤
b
,
0
≤
y
≤
d
}
,
M
4
= {
(
x
,
y
)
∈
R
2
|
0
≤
x
<
a
,
0
≤
y
<
d
}
.
Then using the remarks above, we compute
n
(
M
1
)
=
a
≤
k
≤
b
(
f
(
k
)
+
1
),
n
(
M
2
)
=
c
≤
k
≤
d
(
f
−
1
(
k
)
+
1
)
n
(
M
3
)
=
(
b
+
1
)(
d
+
1
),
n
(
M
4
)
=
a
·
c
.
Since
M
1
∪
M
2
=
M
3
\
M
4
and
M
1
∩
M
2
=
G
f
is the graph of
f
, we get the
identity
a
≤
k
≤
b
(
f
(
k
)
+
1
)
+
c
≤
k
≤
d
(
f
−
1
(
k
)
+
1
)
−
n
(
G
f
)
=
(
b
+
1
)(
d
+
1
)
−
a
·
c
.
The interval
[
a
,
b
] = [
0
,
b
] − [
0
,
a
)
contains
b
+
1
−
a
integers, and
therefore the first sum on the right has this many terms. Similarly, the second sum
3.2. Floor Function and Integer Points
69
has
d
+
1
−
c
terms. Hence we get
a
≤
k
≤
b
f
(
k
)
+
c
≤
k
≤
d
f
−
1
(
k
)
−
n
(
G
f
)
=
(
b
+
1
)(
d
+
1
)
−
a
·
c
−
(
b
+
1
−
a
)
−
(
d
+
1
−
c
)
=
b
d
−
a
−
1
c
−
1
.
Figure 3.1.
Theorem 3.2.2.
Let m
,
n
,
s be positive integers, m
≤
n. Then
s
k
=
1
%
km
n
&
+
1
≤
k
≤
ms
n
%
kn
m
&
=
s
#
ms
n
$
+
%
gcd
(
m
,
n
)
·
s
n
&
.
(
2
)
Proof.
We first prove the following lemma.
Lemma.
The collection
1
·
m
n
,
2
·
m
n
, . . . ,
s
·
m
n
contains exactly
#
gcd
(
m
,
n
)
·
s
n
$
integers.
Proof of the lemma.
Let
d
be the greatest common divisor of
m
and
n
. Hence
m
=
m
1
d
and
n
=
n
1
d
for some integers
m
1
and
n
1
.
The numbers in the collection are
1
·
m
1
n
1
,
2
·
m
1
n
1
, . . . ,
s
·
m
1
n
1
and since
m
1
,
n
1
are relatively prime, there are
s
/
n
1
integers among them. Be-
cause
n
1
=
n
d
=
n
gcd
(
m
,
n
)
it follows that there are
gcd
(
m
,
n
)
s
n
integers in the
collection.
70
I Fundamentals, 3. Floor Function and Fractional Part
In order to prove the desired result, let us consider the function
f
: [
1
,
s
] →
m
n
,
ms
n
,
f
(
x
)
=
m
n
x
in Theorem 3.2.1. Using the lemma above we have
n
(
G
f
)
=
gcd
(
m
,
n
)
·
s
n
, and the conclusion follows.
Remark.
The special case
s
=
n
leads to an important result:
n
k
=
1
%
km
n
&
+
m
k
=
1
%
kn
m
&
=
mn
+
gcd
(
m
,
n
).
(
3
)
Theorem 3.2.3.
Let a
,
b
,
c
,
d be nonnegative real numbers and let f
: [
a
,
b
] →
[
c
,
d
]
be a bijective, decreasing function.
Then
a
≤
k
≤
b
f
(
k
)
−
c
≤
k
≤
d
[
f
−
1
(
k
)
] =
b
c
−
1
−
d
a
−
1
,
where again k ranges over integers.
Proof.
Use the notation of the proof of Theorem 3.2.1. Since
f
is decreasing and
bijective, it is continuous and we can define the regions (see Figure 3.2)
N
1
= {
(
x
,
y
)
∈
R
2
|
a
≤
x
≤
b
,
c
≤
y
≤
f
(
x
)
}
,
N
2
= {
(
x
,
y
)
∈
R
2
|
c
≤
y
≤
d
,
a
≤
x
≤
f
−
1
(
y
)
}
,
N
3
= {
(
x
,
y
)
∈
R
2
|
a
≤
x
≤
b
,
0
≤
y
<
c
}
,
N
4
= {
(
x
,
y
)
∈
R
2
|
a
≤
x
≤
b
,
c
≤
y
≤
d
}
.
Figure 3.2.
Do'stlaringiz bilan baham: |
