Information Technology Reference
In-Depth Information
Deleting the intervals of this chain from
T
,
we can form a second chain and so on
until we obtain
m
chains in all.
CLAIM 3: A chain which has precisely
i
intervals of length
b
where 0
≤
i
≤
1
/
b
has exactly
λ
i
intervals of length
a
where
λ
i
satisfies (
9.2
).
I
r
with precisely
i
intervals of length
b
for
which the assertion is false then, using the definition of
Suppose there is a chain
I
1
,
I
2
,...,
λ
i
in (
9.2
),theremustbeat
least
λ
i
+
1
≥
1 intervals of length
a
in the chain and the termination point
w
of
I
r
satisfies
w
≥
1
+
a
.
Because the interval
I
r
starts before the point 1,
I
r
must be an
interval of length
b
.
Let
s
=
max
{
j
:
|
I
j
|
=
a
}
where
|
I
|
denotes the length of
I
,
then
s
<
r
.
Let
T
s
+
1
,...,
T
r
denote the pure strategies containing
I
s
+
1
,...,
I
r
respectively;
r
let
T
j
for
j
=
s
+
1
,...,
denote the pure strategy obtained from
T
j
by moving
I
j
a
distance
a
to the left.
The analysis now divides into two parts (I) and (II).
(I)
T
j
has overlapping intervals.
If there is a
T
j
which has overlapping intervals, let
T
g
denote the one for which
j
is maximal, then the strategy
S
−
obtained from
S
∗
by replacing
T
j
with
T
j
for
j
≥
g
is clearly still optimal. Note that, in
T
g
,
the interval of length
a
precedes the
The intervals of
T
g
interval of length
b
because
|
I
g
|
=
b
.
overlap so we can take a
pure strategy
T
−∗
g
whose intervals do not overlap and cover the points covered by
the intervals of
T
g
and in which the interval of length
b
precedes the interval of
Replacing
T
g
by
T
−
g
in
S
−
now gives rise to an optimal strategy and this
optimal strategy has more pure strategies having the interval of length
b
preceding
the interval of length
a
than
S
∗
.
length
a
.
However the construction of
S
∗
ensures that
S
∗
and
S
0
have the same number of pure strategies having the intervals of length
b
preceding the interval of length
a
so we have a contradiction to Assumption
3
at the
beginning of the proof.
(II) No
T
j
has overlapping intervals
If no
T
j
has overlapping intervals, replacing
T
j
by
T
j
r
in
S
∗
and moving the interval
I
s
so that it starts at the point 1 would still be an optimal
strategy and the argument above that proves
S
∗
is a strategy in
Z
for
j
=
s
+
1
,...,
Z
shows that this
cannot be the case. Thus we have established the claim, a chain which has precisely
i
intervals of length
b
where 0
×
≤
i
≤
1
/
b
has exactly
λ
i
intervals of length
a
where
λ
i
satisfies (
9.2
).
=
,
,...,
/
,
For each integer
i
i
of chains that
have precisely
i
intervals of length
b
and hence, by what we have just proved, each
of these chains must have precisely
0
1
1
b
there is a non-negative integer
β
λ
i
intervals of length
a
.
The chains have a total
1
/
b
1
/
b
of
i
β
i
intervals of length
b
and
λ
i
β
i
intervals of length
a
.
Since no
∑
∑
i
=
0
i
=
0
member of
K
|
Z
|
has an interval starting at 1 or more,
Search WWH ::
Custom Search