Information Technology Reference
In-Depth Information
Case 2.
|C|≤n/
2
−
1
for every
C ∈{R, B, G}
.
If
x
2
is not red, then the point
x
p
=
x
2
is the desired point because for every
C ∈{R, B, G}
,
1=
n −
=
n − p
2
2
2
|C ∩{x
3
,...,x
n
}| ≤ |C|≤
−
.
2
x
2
is red. Then there exists a blue or green point
Hence we may assume that
x
t
(
t ≥
x
1
,...,x
t−
1
are all red. We now consider a sequence
3), such that
Y
=(
y
1
,y
2
,...,y
n−
2
)=(
x
2
,...,x
t−
1
,x
t
+1
,...,x
n
)
,
which is obtained from the original sequence by removing one red point
x
1
and
one blue or green point
x
t
. Note that the points
y
1
(=
x
2
)and
y
n−
2
(=
x
n
)have
the same color, namely red. For every
C ∈{R, B, G}
,
|C∩Y |≤|C|≤n/
2
−
1=
(
n −
2)
/
2
. Thus, by applying the inductive hypothesis to
Y
, there exists an
even number
q
(2
≤ q ≤ n −
3) such that
y
q
is a blue or green point and for
every
C ∈{R, B, G}
,
|C ∩{y
1
,...,y
q
}| ≤
2
,
n −
2
− q
|C ∩{y
q
+1
,...,y
n−
2
}| ≤
.
2
Then
y
q
=
x
q
+2
and
t
+1
≤ q
+ 2 since
x
1
,...,x
t−
1
are red,
x
t
∈ Y
,and
y
q
is not red. Hence, since
x
1
and
x
t
have distinct colors, for every
C ∈{R, B, G}
,
|C ∩{x
1
,x
t
,y
1
,...,y
q
}| ≤
2
+1=
q
+2
2
|C ∩{x
1
,...,x
q
+2
}|
=
,
n −
=
n −
2
− q
(
q
+2)
|C ∩{x
q
+3
,...,x
n
}|
|C ∩{y
q
+1
,...,y
n−
2
}| ≤
.
=
2
2
Therefore, since
q
is even, namely
q
+2 is even, the point
x
p
=
x
q
+2
is the desired
point.
3 Proof of Theorem
1.2
by Using Lemma
1.8
We briefly call a non-crossing properly colored geometric perfect matching
a
Perfect Matching
. Set 2
n
=
|X|
. We prove the theorem by induction on
n
.If
n
n ≥
= 1 then the theorem is true. For
2, we suppose that the theorem holds
n −
for 2(
1) points.
Suppose that
|C|
=
n
for some
C ∈{R, B, G}
. Set
W
=
C
and
K
=
(
R ∪ B ∪ G
)
\ C
. We recolor all the points of
W
with white, and all the points
of
with black. Then there exists the desired Perfect Matching by applying
Theorem
1.1
to
K
W ∪ K
.
Search WWH ::
Custom Search