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
n
, 2
·
4
n
,..., 2
·
2( p
1)
.
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