Information Technology Reference
In-Depth Information
We construct a set
S
j
+
1
from
S
j
which has the same properties as
S
j
.
If there are precisely
m
members of
K
j
containing
(
z
j
,
z
j
+
1
)
,
put
K
j
+
1
=
K
j
and
define
S
j
+
1
=
S
j
.
Clearly
S
j
+
1
satisfies the inductive conditions.
If there are
m
j
>
m
members of
K
j
containing
(
z
j
,
z
j
+
1
)
,
then, because there are
precisely
m
members of
K
j
containing
(
z
j
−
1
,
z
j
)
,
there are at least
m
j
−
m
members
of
K
j
which have intervals starting at
z
j
.
We can therefore modify precisely
m
j
−
m
.
of them by moving the interval starting at
z
j
so that it starts at
z
j
+
1
If, in a modified
pure strategy, the interval
I
which has been moved to start at
z
j
+
1
has interior points
in common with the other interval
J
,
we further modify the strategy by moving
J
to the right until it starts at
w
,
where
w
is the termination point
t
of
I
if
t
<
1and1
otherwise; note that
w
is a point of
Z
∗
by the definitions of
Z
and
Z
∗
.
We now define
K
j
+
1
as the set of the modified strategies together with the unmodified strategies of
K
j
.
Taking
S
j
+
1
to be the strategy which chooses a member of
K
j
+
1
at random it is
easy to see that
S
j
+
1
satisfies the inductive conditions.
Clearly
S
0
satisfies the above conditions on
S
j
with (
γ
) being satisfied vacuously.
Thus, by induction we have established Claim 1.
CLAIM 2:
S
∗
is a strategy in
Z
×
Z
.
Suppose
K
|
Z
|
has a pure strategy
W
r
which has an interval
X
r
of length
x
starting
at the point 1 and let
Y
r
denote the other interval in
W
r
.
If
Y
r
also starts at 1, the intervals of
W
r
do not contain any points in Infiltrator's
finite strategy space so the strategy given by randomly choosing a member of
K
|
Z
|
\
{
W
r
}
k
which is a contradiction.
We can therefore assume that
Y
r
covers some interval
would give a value strictly less than
(
k
−
m
)
/
Let
x
(
1
)
and
x
(
2
)
be the number of closed intervals of length
x
needed to cover the inter-
vals
[
y
1
,
y
2
]
where
y
1
∈
Z
.
respectively. Let
K
be the multiset comprising of
x
(
1
)
+
x
(
2
)
−
[
0
,
y
1
]
and
[
y
2
,
1
]
1
copies of
K
|
Z
|
together with an extra
W
r
,
then
K
contains
x
(
1
)
+
x
(
2
)
copies of
W
r
.
From these copies of
W
r
,
define
x
(
1
)
+
x
(
2
)
pure strategies in
Z
×
Z
by repositioning
the
x
(
1
)
+
x
(
2
)
intervals
X
r
so that they cover
but do not have
y
1
or
y
2
as an interior point and let
K
∗
denote the multiset obtained from
K
by substituting
these strategies for the
x
(
1
)
+
[
0
,
y
1
]
and
[
y
2
,
1
]
x
(
2
)
copies of
W
r
.
The Defender strategy which selects
amemberof
K
∗
at random restricts Infiltrator to at most
x
(
1
)
+
x
(
2
)
−
m
(
1
)+
1
−
1
<
−
=
(
,
)
1
1
mk
v
a
b
x
(
1
)
+
x
(
2
)
−
k
(
1
)+
which is a contradiction. Hence
S
∗
is a strategy in
Z
×
Z
.
We have established
Claim 2.
Let
T
denote the multiset of intervals in the members of
K
|
Z
|
.
By the construction
of
S
∗
,
if there are
j
members of
T
which terminate at
z
i
>
0
,
then there are
j
members
of
T
which start at
z
i
.
We can therefore obtain a “chain” of intervals by selecting a
sequence of intervals
I
0
,
I
1
,...,
I
r
such that
I
0
starts at
z
0
=
0
,
I
i
starts at the point
where
I
i
−
1
terminates
(
i
=
1
,...,
r
)
and
I
r
contains the point 1 but starts before it.
Search WWH ::
Custom Search