|
II Solutions, 3. Floor Function and Fractional Part
First solution.
Denote the sum in question by
S
n
. Then
S
n
−
S
n
−
1
=
#
x
n
$
+
%
x
+
1
n
&
+ · · · +
%
x
+
n
−
1
n
&
=
#
x
n
$
+
%
x
n
+
1
n
&
+ · · · +
%
x
n
+
n
−
1
n
&
,
and according to Hermite’s identity,
S
n
−
S
n
−
1
=
#
n
x
n
$
=
x
.
Because
S
1
=
x
, it follows that
S
n
=
n
x
for all
n
.
Second solution.
By Hermite’s identity applied to
x
/
j
we have
j
−
1
i
=
0
%
x
+
i
j
&
=
%
j
x
j
&
=
x
.
Summing this over
j
gives
n
j
=
1
j
−
1
i
=
0
%
x
+
i
j
&
=
n
x
.
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
&
.
Solution.
We can write each term of the difference in question as
#
1
3
+
v
k
$
−
#
1
3
−
v
k
$
,
where
v
k
=
2000
/
3
k
+
1
. Since
−
u
= −
u
+
1 for each nonintegral value of
u
,
and since
1
3
−
v
k
is never an integer, we have to examine the sum
2000
k
=
0
#
v
k
+
1
3
$
+
#
v
k
−
1
3
$
+
1
.
Taking
n
=
3 and
x
=
v
−
1
3
in (1) yields
#
v
+
1
3
$
+
#
v
−
1
3
$
+
1
=
3
v
−
v
.
3.1. General Problems
261
Hence the desired difference becomes
2000
k
=
0
%
2000
3
k
&
−
%
2000
3
k
+
1
&
,
which telescopes to
2000
−
%
2000
3
&
+
%
2000
3
&
−
%
2000
3
2
&
+ · · · =
2000
.
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)
Solution.
(a) Since 0
.
99
=
99
100
, it is natural to look for a rational
x
of the form
n
10
,
for some positive integer
n
. It is not difficult to see that
x
=
13
10
satisfies the given
equality and then that
x
=
10
k
+
13
10
also satisfies the equality for any positive
integer
k
.
(b) Suppose that
x
=
p
/
q
, with
p
,
q
positive integers, gcd
(
p
,
q
)
=
1, satisfies
{
x
2
}+{
x
} =
1. We can see that
p
2
+
pq
−
q
2
q
2
=
x
2
+
x
−
1
∈
Z
; thus
q
|
p
2
, and since
gcd
(
p
,
q
)
=
1, one has
q
=
1. Thus
x
∈
Z
, and this is obviously impossible.
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)
Solution.
From the inequalities 4
n
2
<
4
n
2
+
n
<
4
n
2
+
n
+
1
16
one obtains
2
n
<
√
4
n
2
+
n
<
2
n
+
1
4
. So
√
4
n
2
+
n
=
2
n
and
{
√
4
n
2
+
n
}
<
1
/
4.
Problem 3.1.15.
Prove that for every natural number n,
n
2
k
=
1
{
√
k
} ≤
n
2
−
1
2
.
(1999 Russian Mathematical Olympiad)
262
II Solutions, 3. Floor Function and Fractional Part
Solution.
We prove the claim by induction on
n
. For
n
=
1, we have 0
≤
0. Now
supposing that the claim is true for
n
, we prove that it is true for
n
+
1.
Each of the numbers
√
n
2
+
1
,
√
n
2
+
2
, . . . ,
√
n
2
+
2
n
is between
n
and
n
+
1. Thus
{
n
2
+
i
} =
n
2
+
i
−
n
<
;
n
2
+
i
+
i
2
4
n
2
−
n
=
i
2
n
,
i
=
1
,
2
, . . . ,
2
n
.
Therefore we have
(
n
+
1
)
2
k
=
1
{
√
k
} =
n
2
k
=
1
{
√
k
} +
(
n
+
1
)
2
k
=
n
2
+
1
{
√
k
}
<
n
2
−
1
2
+
1
2
n
2
n
i
=
1
i
+
0
=
n
2
−
1
2
+
2
n
+
1
2
=
(
n
+
1
)
2
−
1
2
,
completing the inductive step and the proof.
Problem 3.1.16.
The rational numbers
α
1
, . . . , α
n
satisfy
n
i
=
1
{
k
α
i
}
<
n
2
for any 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)
Solution.
(a) Assume the contrary. The problem would not change if we replace
α
i
with
{
α
i
}
. So we may assume 0
< α
i
<
1 for all 1
≤
i
≤
n
. Because
α
i
is
rational, let
α
i
=
p
i
q
i
, and
D
=
n
i
=
1
q
i
. Because
(
D
−
1
)α
i
+
α
i
=
D
α
i
is an
integer, and
α
i
is not an integer,
{
(
D
−
1
)α
i
} + {
α
i
} =
1. Then
n
>
n
i
=
1
{
(
D
−
1
)α
i
} +
n
i
=
1
{
α
i
} =
n
i
=
1
1
=
n
,
contradiction. Therefore, one of the
α
i
has to be an integer.
(b) Yes. Let
α
i
=
1
2
for all
i
. Then
"
n
i
=
1
{
k
α
i
} =
0 when
k
is even and
"
n
i
=
1
{
k
α
i
} =
n
2
when
k
is odd.
3.2. Floor Function and Integer Points
263
3.2
Floor Function and Integer Points
Problem 3.2.3.
Prove that
n
k
=
1
%
n
2
k
2
&
=
n
2
k
=
1
%
n
√
k
&
for all integers n
≥
1
.
Solution.
Consider the function
f
: [
1
,
n
] → [
1
,
n
2
]
,
f
(
x
)
=
n
2
x
2
.
Note that
f
is decreasing and bijective, and
f
−
1
(
x
)
=
n
√
x
.
Using the formula in Theorem 3.2.3, we obtain
n
k
=
1
%
n
2
k
2
&
−
n
2
k
=
1
%
n
√
k
&
=
n
1
−
1
−
n
2
1
−
1
=
0
,
hence
n
k
=
1
%
n
2
k
2
&
=
n
2
k
=
1
%
n
√
k
&
,
n
≥
1
,
as desired.
Problem 3.2.4.
Let
θ
be a positive irrational number. Then, for any positive inte-
ger m,
m
k
=
1
k
θ
+
m
θ
k
=
1
%
k
θ
&
=
m
m
θ
.
Solution.
Consider the function
f
: [
0
,
m
] → [
0
,
m
θ
]
,
f
(
x
)
=
θ
x
. Because
θ
is irrational, we have that
n
(
G
f
)
=
1 cancels the
a
−
1
c
−
1
=
(
−
1
)
2
=
1
term, and the conclusion follows from Theorem 3.2.1.
Problem 3.2.5.
Let p and q be relatively prime positive integers and let m be a
real number such that
1
≤
m
<
p.
(1) If s
=
mq
p
, then
m
k
=
1
%
kq
p
&
+
s
k
=
1
%
kp
q
&
=
m
s
.
264
Do'stlaringiz bilan baham: |
