Information Technology Reference
In-Depth Information
q
C
1
n
−
q
C
p
−
1
+
2
q
C
2
n
−
q
C
p
−
2
+
···
+
r
q
C
r
n
−
q
C
p
−
r
+
···
+
p
q
C
p
n
−
q
C
0
;
n
C
p
this expression can be rearranged to
pq
/
n
1
C
p
−
1
W
n
−
where
n
−
q
C
p
−
1
+
q
−
1
C
1
n
−
q
C
p
−
2
+
···
+
q
−
1
C
r
−
1
n
−
q
C
p
−
r
+
···
+
q
−
1
C
p
−
1
W
=
Because
W
is the coefficient of
x
p
−
1
in the expansion of
n
−
q
q
−
1
and the
(
1
+
x
)
(
1
+
x
)
denominator is the coefficient of
x
p
−
1
in the expansion of
n
−
1
(
1
+
x
)
,
they are equal
and the expression simplifies to
pq
/
n
.
Optimal strategies for RED and BLUE are
to select the set of
p
,
respectively
q
,
integers from
{
1
,
2
,...,
n
}
by simple random
sampling.
We now introduce notation which enables us to give alternative optimal strategies
in the Simple Point Catcher Game which are more useful as a guide for optimal
strategies in the modified Interval Overlap games described below. In fact they are
the optimal strategies Ruckle used to solve the Modified Number Hides Game in
which the players can choose sequences modulo
n
.
Let
n
be a fixed positive integer
x
∗
where
x
∗
≤
and, for each positive integer
x
,
let
x
=
λ
n
+
λ
is an integer and 0
<
n
.
For positive integers
m
<
n
and
x
,
put
x
∗
,
x
∗
+
if
x
∗
+
[
m
−
1
]
m
−
1
≤
n
,
I
m
(
x
)=
x
∗
,
x
∗
−
if
x
∗
+
[
n
]
∪
[
1
,
m
+
n
−
1
]
m
−
1
>
n
.
Thus the sets in
I
m
=
{
I
m
(
x
)
:
x
=
1
+
μ
m
for
μ
=
0
,
1
,...,
n
−
1
}
cover the integer interval
[
1
,
n
]
precisely
m
times and every integer
y
∈
[
1
,
n
]
is in
precisely
m
members of
I
m
.
Hence, if RED chooses one of the members of
I
p
at
random and BLUE chooses any set of
q
integers in
[
1
,
n
]
,
RED has an expectation
of
pq
/
n
.
Similarly, if BLUE chooses one of the members of
I
q
at random, RED
has an expectation of
pq
/
n
whatever set of
p
integers in
[
1
,
n
]
RED chooses. Thus,
I
I
taking a member at random from
q
respectively are optimal strategies for
RED and BLUE in the Simple Catcher Game. These optimal strategies and the ones
mentioned earlier demonstrate that the game has the unusual property that, if the
roles are reversed (so that RED loses the number of integers in the intersection of
the chosen intervals), a player still has the same optimal strategy.
We now look at the analogous problems on the real interval
p
and
[
0
,
1
]
where one
or both players can, instead of choosing an interval of length
α
,
choose a set of
(Lebesgue) measure
α
.
This gives rise to the following three games over the unit
Search WWH ::
Custom Search