A Location Game On Disjoint Circles

i.e. the difference between the number if red points and green points placed
on the family of circles is equal to the difference between the number of red
and green intervals on that family of circles.

Proof. In Ahn et al. [2004] it is shown that for any circle C it holds that
I^R(C)-I^G(C) = r^C-g^C. Then ^Pk^K=1(I^R(Ck)-I^G(Ck)) = ^Pk^K=1(r^Ck-g^Ck)
and, so PK 11R(Ck) - PK=ι I^G(Ck)) = PK=ι rC^k - PK=ι SC. ■

The following corollary is immediate from the above lemma.

Corollary 1 Let {Cj }_j^K₌₁ be a family of circles where each of the players R
and G placed the same number of points. Then the number of red and green
intervals is the same.

Lemma 2 Let {Ck }_k^K₌₁ be a family of circles with key positions with respect
to some M for each circle. Assume that (i) there are r = ^P_k^K₌₁ r^Ck ≤ KM
red and g = ^P_k^K₌₁ g^Ck < r green points on the family of circles covering all
KM key positions and (ii) there is only one red interval which is not a key
interval. Then there exists a bichromatic key interval.

Proof. The argument used in Ahn et al. [2004] for an analogical lemma
for one circle works for this lemma as well. We have r + g ≤ 2KM - 1
points on the circles and KM of them are key points. Thus there are at
most KM - 1 points lying within some key intervals. This leaves one key
interval without a point. This key interval cannot be red, as there is only
one red interval which is not a key interval. The key interval cannot be
green, as by Lemma 1, this would mean that there are more then one red
intervals (notice that r > g). Thus the key interval must be bichromatic. ■

We now prove our first main result by identifying a tying strategy called
T* for R, the first mover.

11

<<   11   12   13   14   15   16   17   >>

More intriguing information