Information Technology Reference
In-Depth Information
Kikuta-Ruckle conjecture for the values of
k
and
n
that correspond to odd graphs:
in this section, it is our standing assumption that
n
=
2k
−
1
.
Lemma 1.
Suppose that the Kikuta-Ruckle conjecture is correct for the odd graph.
Then it is optimal to put a dose of
1
1
j
,
1
j
+
/
j if and only if h
∈
[
2
−
2
−
)
.
1
Proof.
If the conjecture is correct, then we have to determine what the optimal dose
1
/
j
is, depending on
h
. This is a counting problem. Let
N
j
be the number of lethal
subsets if we put a dose of 1
1
j
. We claim that
N
1
/
≥
−
< ···<
j
and
h
2
N
k
is an
1
increasing sequence. Note that if
h
k
in every
biscuit, so every
k
-subset is lethal, and
N
k
is equal to the total number of biscuits.
Therefore, we only need to consider
j
≥
2
−
k
, then we can put a dose 1
/
<
k
. To fix our ideas, assume that we put the
dose 1
1 biscuits. To compare
N
j
to
N
j
+
1
we need to consider
the effect of reducing the amount of poison in the first 2
j
/
j
in the first 2
j
−
−
1 biscuits from 1
/
j
to
1
in the next two biscuits that previously
did not contain any poison. Such a redistribution can only change the lethality of a
k
-subset if it contains either
j
or
j
/
(
j
+
1
)
, while putting a dose of 1
/
(
j
+
1
)
+
1 elements from
{
1
,...,
2
j
+
1
}
. A lethal subset
becomes non-lethal if it contains
j
elements from
{
1
,...,
2
j
−
1
}
and none from
{
2
j
,
2
j
+
1
}
. There are exactly
2
j
2
k
−
1
−
2
j
−
2
−
j
k
j
such subsets. Conversely, a non-lethal subset becomes lethal if it contains
j
−
1
elements from
{
1
,...,
2
j
−
1
}
and both 2
j
and 2
j
+
1. There are exactly
2
j
2
k
−
1
−
2
j
−
2
−
−
−
j
1
k
j
1
k
−
j
−
1
k
−
j
such subsets. Dividing the first binomial product by the second gives
so
the number of
k
-subsets that become lethal exceeds those that become non-lethal.
Which proves that
N
j
<
<
1
,
N
j
+
1
.
If we put a dose of 1
1
j
, then there are at most 2
j
2 poi-
sonous biscuits. Let
M
j
be the number of lethal
k
-subsets in this case. We claim that
M
1
< ···<
/
j
while
h
<
2
−
−
M
k
is again an increasing sequence. To compare
M
j
to
M
j
+
1
we need
to consider the effect of reducing the amount of poison in the first 2
j
−
2 biscuits,
/
(
+
)
−
while putting a dose of 1
j
1
in biscuit 2
j
1and2
j
. The number of lethal
subsets that become non-lethal now is
2
j
2
k
−
2
−
2
j
−
1
j
k
−
j
while the number of subsets that become lethal is
2
j
2
k
−
2
−
2
j
−
1
.
−
−
−
j
1
k
j
1
Search WWH ::
Custom Search