Information Technology Reference
In-Depth Information
4.2
Conditions for
C
opt
(
k
)=0
Unlike in the basic problem, in the
n
-cyclotomic problem
C
opt
(
k
)=0isnot
always true for
k
2. Apart from online optimization, there arises an interesting
question:
Which pair
(
n, k
)
admits
C
opt
(
k
)=0
?
In this subsection we give a
partial answer. We start from easy cases.
≥
1
n−
Lemma 4.
For any
n
,
C
opt
(1) = 0
,
C
opt
(
n
−
1) =
1
,and
C
opt
(
n
)=0
.
Proof.
C
opt
(1) = 0 and
C
opt
(
n
) = 0 are trivial. We now see why
C
opt
(
n
−
1) =
1
n−
1 points have been placed optimally (though there
is no choice) and their center of mass
G
(
n
holds. Suppose that
n
−
1
1) lies somewhere. Next, add a point
at
P
(
n
), which is the unique destination without a point yet. Then, needless to
say, the new center of mass comes to the origin
O
. By considering that the mass
of the
n
−
1), the new center can also be thought of
as the
positio
n that divides the line segmen
t
G
(
n
−
1 points concentrates at
G
(
n
−
−
1)
P
(
n
) in the ratio 1 :
n
−
1.
1
Since
OP
(
n
) = 1, we obtain
C
opt
(
n
−
1) =
OG
(
n
−
1) =
n−
1
.
The next theorem gives a sucient condition when
n
belongs to a class of com-
posite numbers.
Theorem 4.
For
n
even and divisible by some odd number
p
≥
3
,
C
opt
(
k
)=0
holds if
k
is even or
p
≤
k
≤
n
−
p
.
Proof.
Observe that if some set of placed points forms a diameter of the unit
circle or a regular polygon, then the center of mass of the points lies at the origin.
The idea of our proof is thus to give a strategy that places points in such a way
that they can be decomposed into such sets. If
k
is even, we can choose
2
pairs
of positions that form
2
distinct diameters and the proof is done.
In what follows, assume that
k
is odd and satisfies
p
p
.Wepresent
a strategy for such
k
. For ease of presentation, only the angles appearing in the
strategy are described below. Although we give a series of angles with length
n
≤
k
≤
n
−
p
in total, the strategy is constructed so that to apply only the first
k
angles
always leads to a cost of zero. Let
m
=
2
p
. Intuitively, our strategy first makes
a regular
p
-gon followed by (
m
−
−
1)
p
distinct diameters. Formally, our strategy
is to: (i) Place points at
0
,
2
·
2
mˀ
n
,
2
·
4
mˀ
n
,...,
2
·
2(
p
−
1)
mˀ
.
n
(ii) Then place points, repeatedly for
j
=1
,
2
,...,p
,at
j −
m
π
j −
m
π
j −
m
π
j −
m
π
2((
1)
+1)
2((
1)
+1)
2((
1)
+2)
2((
1)
+2)
,
+
π,
,
+
π,
n
n
n
n
2((
j −
1)
m
+
m −
1)
π
n
2((
j −
1)
m
+
m −
1)
π
n
...,
,
+
π.
Search WWH ::
Custom Search