A Location Game On Disjoint Circles

Theorem 2 Let hN, {Cj}_j^K₌₁i define a game on the family of disjoint circles
with K ≥ 2. If K - N, then T * is a tying strategy for R.

Proof. We start by showing that strategy T* is implementable. The
only situation, where the strategy may not be applied is the one where at
some round r, R faces the situation where there is no key position left (and
he is having e > 0 points left). This means that in each of the K circles,
dN/K e key positions are taken (notice that if G does not take any key
position up to the round r, then this situation cannot appear). Let r⁰ ≤ r
be the last round such that at the round r⁰ - 1, G took a key position.
Observe that it must be that r⁰ = r, as R is able to cover all remaining key
positions at r. Consider R’s move at the round r - 1. Since R has enough
points to cover all remaining key positions at this stage, he would do that
and this contradicts the assumption that G places a point in a key position
at this round. Thus the strategy is implementable.

Now we will show that using this strategy either R wins or ties. Firstly,
observe that after R’s move in the last round all key positions must be
covered. For assume throughout the game G did not take any key position
(this means in particular that G has never placed a point in an empty circle,
as such point is always a key position). Then at round (N mod K)dN/Ke +
1⁶ R plays in an empty circle and he can cover bN/Kc key positions in each
of the remaining empty circles, so the game finishes and all key positions
are covered. Now assume that at some round r, G places a point in a
key position. Then R is still capable of covering all remaining key positions
towards the end of the game. Moreover after G’s move, the number of circles
where R would have to take bN/Kc key positions decreases by 1. After G
takes K - (N mod K) key positions, R is capable of covering all remaining
key positions and at the and of the game dN/Ke key positions will be taken

⁶Notice that N = (N mod K)dN∕K"∣ + (K - N mod K)[N∕KJ.

12

<<   12   13   14   15   16   17   18   >>

More intriguing information