A Location Game On Disjoint Circles

red interval of the size ≥ 1/dN/Ke.

Consider now stage (c), where both players place their last points. The
following situations are possible after R places his point in that round: (i)
there are two or more red intervals, or (ii) there is one red interval. Assume
that case (i) holds. Then G places a point in the largest red interval. If the
size of the newly created red interval was ≥ dN/K e, then the green point
was placed within this interval, as after the stage (b) there is no red interval
of the size ≥ 1/dN/Ke. Thus after the last round there is no red interval
of the size ≥ 1/dN/K e. Since, also, by Lemma 1, there is the same amount
of green and red intervals and, moreover, each of green intervals is a key
interval (as by strategy Y*, G never created a green interval apart from the
first stage), so G must be winning (recall that the size of a key interval is
≥ 1/dN/Ke).⁹

Now assume that case (ii) holds. Consider the situation before R’s move.
It must be that there is no red interval. Consider the group of circles for
which dN/Ke key positions are assigned. It cannot be that R has more
points than G on these circles (as otherwise, by Lemma 1 there would be
a red interval there). Similarly R cannot have more points on the group of
the circles with bN/Kc key positions assigned. Thus on each such group of
circles, classified by the number of key positions, G and R have the same
number of points. Suppose that after R’s move, a red interval is created in
the group of circles for which bN/K c key positions are assigned (notice that
such red interval may have the size ≥ 1/dN/Ke). Then, by Lemma 2, there
must be a bichromatic key interval in that group of circles (i.e. a bichromatic
key interval of the size 1/bN/Kc). Thus G can win by placing a point in
that key interval and creating a green interval of the size bigger than the

⁹Notice that G’s advantage may be arbitrarily small, as non-key intervals created by
R may be arbitrarily close in size to that of key intervals.

20

<<   20   21   22   23   24   25   26   >>

More intriguing information