A Location Game On Disjoint Circles

determined by m and some point in C. A point placed in a key position
will be called a key point and an interval formed by two key points will be
called a key interval.

Before presenting our results in the next section, we report the main
result from Ahn et al. [2004] for the case K = 1. Consider the following
strategy, S* used by player G (where key positions are simply N equidistant
points on the circle:

Strategy S*

if there is an empty key position left then

(a) |_ place a point on s key position

else if if r < Z then

(b) |_ place a point in the middle of a maximal interval of the opponent
else

(c) if there is more than one interval of the opponent then
place a point in the middle of a maximal interval of the
opponent

else if there is exactly one interval of the opponent and its length
is l then

place a point in a bichromatic key interval at distance less

_ than 1/N — l from endpoint of the opponent

Theorem 1 (Ahn et al. [2004]) Let hN, {Cj}_j^K₌₁i define a game on a sin-
gle circle such that K = 1. Then S^* is a winning strategy for G although R
can always bring the difference SG — SR as close as possible to zero.

<<   8   9   10   11   12   13   14   >>

More intriguing information