A Location Game On Disjoint Circles

Theorem 6 Let hN, {Cj}_j^K₌₁i define a game on the family of disjoint circles
with N > K ≥ 2 and assume that players face a very strict resource mobility
constraint so that they are allowed to place exactly one point at a time. Then
Y * is a winning strategy for G.

Proof. Notice that, just as in the case of S *, the use of strategy Y * leads
to the following three stages of the game for player G. First the option (a)
is excercised, until all key positions are covered (some of them with respect
to dN/K e and others with respect to bN/K c). Then the option (b) is
excercised, until G reaches a round where he has only one point left (since
the game is restricted, so that both players play exactly one point at each
round this will be at the round r = Z). Finally the last stage is reached,
where G plays according to (c). We start with two claims.

Claim 1 After the end of round (a), G has at least one point left.

Proof. Observe first that key positions are taken either with respect to
bN/Kc or dN/Ke and N = (N mod K)dN/Ke + (K - N mod K)bN/Kc,
so a player is capable of capturing all key positions on all circles, taking key
positions with respect to dN/K e on (N mod K) circles, the remaining key
positions with respect to bN/Kc on the remaining K - N mod K circles.
Since R places at least one point in a key position (which is the first point
placed by him) and throughout the game G never assigns dN/Ke as the
number of key positions to more than N mod K circles that do not contain
a red key point (by checking each time when the green point is placed on
free circles as to whether the number of free circles L ≤ K - N mod K), so
G will have at least one point left after all key positions are taken. ■

Claim 2 The number of red key intervals of size 1/bN/K c is never greater
than the number of green key intervals of that size.

18

<<   18   19   20   21   22   23   24   >>

More intriguing information