A Location Game On Disjoint Circles

Proof. This is because whenever R places a point in an empty circle, G
places a point there in the same round, assigning the number of key positions
for that circle to dN/Ke. Thus red key intervals of the size 1/bN/Kc can
be created only on the circles where G placed the first point, and so after
all key points in each such circle are taken, G will take no less key positions
there than R. Moreover strategy Y * ensures that each red key point has
at most one neighbouring red key point (because G places a point next to
a newly placed red point, if possible, and starts by placing it on the same
side (clockwise in the case of strategy Y^*)).⁸ Thus the number of green
key intervals in such circles cannot be smaller than the number of red key
intervals there. ■

Now assume that all key positions are taken and R places a point.
Then there is one more red points than green points on the circles, and
by Lemma 1, there is at least one red interval. Thus the next move of G is
implementable and the game is either in stage (b) or (c).

Observe that in stage (b) G will place a point in all red key intervals
of size 1/bN/Kc (as he has at least twice the number of such intervals of
points left, and these intervals are being broken first). Moreover G will place
a point in all red key intervals of size 1/dN/Ke in the stage (b) (as he saves
at least one point each time such interval is created by R). Notice also that
whenever R creates a red interval of the size ≥ 1/dN/K e, this interval is
created by placing two red points within a green key interval of the size
1/bN/Kc and at most one red interval of this size can be created in such
green key interval. Since the stage (b) ends when both players have only
one point left, so all such intervals created in the stage (b) will have been
broken by G by the end of that stage. Thus after the stage (b) there is no

⁸ The restriction on the game, so that players move one-by-one is crucial for this prop-
erty. Notice that this issue arises only when bN/Kc 6= dN/Ke, i.e. K-N.

19

<<   19   20   21   22   23   24   25   >>

More intriguing information