Information Technology Reference
In-Depth Information
2
j
j
2
k
min
{
2
j
,
k
−
1
}
∑
i
=
j
+
1
2
j
i
2
k
1
2
−
2
j
−
1
−
2
j
−
1
(
k
−
j
)+
(
k
−
i
)
k
−
j
k
−
i
2
2
k
−
2
1
. This equality can be rewritten to
n
−
2
j
is equal to
k
−
2
j
2
k
−
2
j
−
2
1
2
i
2
k
−
2
j
−
2
1
min
{
2
j
,
k
−
1
}
1
2
.
k
−
j
−
k
−
i
−
∑
k
−
1
+
=
2
2
k
−
2
2
k
−
2
k
−
1
i
=
j
+
1
Let
X
be a hypergeometric random variable that describes the number of successes
in
k
−
1 draws from a population of
N
=
2
k
−
2 with 2
j
successes. Then this equation
is equal to
1
2
.
In other words, the median of
X
is at
j
. To see why this is true, notice that drawing
k
1
2
P
(
=
)+
(
>
)=
X
j
P
X
j
−
1 from 2
k
−
2 is equivalent to leaving
k
−
1 from 2
k
−
2. Since the number of
successes is 2
j
, this implies that
P
(
X
>
j
)=
P
(
X
<
j
)
.
Theorem 1.
The Kikuta-Ruckle conjecture is true for odd graphs, i.e., if n
=
2
k
−
1
.
Proof.
If we put 2
j
−
1 doses of 1
/
j
then an edge is lethal if and only if it contains
at least
j
out of the first 2
j
−
1 biscuits. So the number of lethal edges is equal to
2
j
2
k
k
i
=
j
−
1
−
2
j
.
i
k
−
i
By the previous lemma, it suffices to show that this is equal to
2
j
j
2
k
2
j
i
2
k
k
∑
1
2
−
2
j
−
1
−
2
j
−
1
+
.
−
−
k
j
k
i
i
=
j
+
1
If we divide both sums by
2
k
−
k
then the first quotient is
P
for a hypergeo-
metric random variable that counts the number of successes if we draw
k
times with
2
j
(
X
1
≥
j
)
1
2
P
if the number
of successes is 2
j
. To see why these probabilities are the same, start with the popu-
lation that has 2
j
successes and call one of them a failure, which transforms
X
2
into
X
1
.Let
U
be the event that the draw does not contain the success which turns into a
failure. Then
X
1
≥
−
1 successes. The second quotient is
(
X
2
=
j
)+
P
(
X
2
≥
j
+
1
)
j
is equal to
(
X
2
≥
j
+
1
)
∪{
U
∩
X
2
=
j
}.
Now observe that
1
2
P
P
(
U
∩
X
2
=
j
)=
P
(
U
|
X
2
=
j
)
P
(
X
2
=
j
)=
(
X
2
=
j
)
.
Search WWH ::
Custom Search