Information Technology Reference
In-Depth Information
j
−
1
The quotient of these two binomial products is
so the number of subsets
that become lethal upon redistribution again exceeds the number of those that be-
come non-lethal. Now we claim that
M
k
<
<
1
,
j
N
1
, so it is better to put a single unit
dose. Indeed
M
k
=
2
k
−
k
while
N
1
=
2
k
−
2
k
−
1
. So putting a dose 1
/
j
for
j
>
1 is only
1
j
.
≥
−
optimal once
h
2
We have an amount of poison
h
that we distribute over the biscuits, putting a
dose
h
i
in the
i
-th biscuit. A
k
-subset
V
is lethal if and only if
h
1.
We number the biscuits in decreasing order of their doses, putting the most poi-
sonous biscuit first, i.e.,
h
1
≥ ··· ≥
(
V
)=
∑
i
∈
V
h
i
≥
be the family of poisonous
k
-
subsets. We want to distribute the poison in such a way that
h
2
k
−
1
.Let
P
P
has maximum car-
dinality. We adopt hypergraph terminology. We say that
V
∈ P
is an edge, and
deg
P
(
i
)
is equal to the number of edges that contains
i
.
2
2
k
−
2
1
.
1
1
Lemma 2.
If h
<
2
−
then
deg
P
(
2
j
+
1
)
≤
j
+
1
k
−
Proof.
By the decreasing dosage of poison
2
j
+
1
(
2
j
+
1
)
h
2
j
+
1
≤
h
1
+
···
+
h
2
j
+
1
≤
h
<
1
,
+
j
1thenlet
V
V
c
+
<
+
=
∪{
+
and so
h
h
2
j
+
1
2. If
V
is any
k
-subset that contains 2
j
2
j
.Inotherwords,
V
is the neighbor of
V
in the odd graph
}
O
k
that is connected by
1
V
the edge that has 2
j
+
1 as the odd one in. Then
h
(
V
)+
h
(
)=
h
+
h
2
j
+
1
<
2. So if
V
is poisonous then
V
is not, and we conclude that deg
P
(
2
j
+
1
)
is at most half of
thedegreeof2
j
+
1 in the complete hypergraph on all
k
subsets. The degree of the
complete hypergraph is
2
k
−
2
k
1
.
−
1
Lemma 3.
If h
<
2
−
then the number of lethal edges is at most
j
+
1
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
Proof.
We maximize the number of edges
V
under the constraint that the hypergraph
has maximal
∑
i
≥
2
j
+
1
deg
(
i
)
, which by the previous lemma is bounded by
2
k
n
−
2
j
−
2
.
2
k
−
1
The greedy solution is to first take all
k
-subsets that have no elements in
{
2
j
+
1
,
etc, until the sum of the degrees exceed the given bound. We need to show that this
happens exactly when we have taken all
k
-subsets that contain
,...,
2
k
−
1
}
,thentotakeall
k
-subsets that have one element in
{
2
j
+
1
,...,
2
k
−
1
}
>
j
elements from
{
and half of the
k
-subsets that contain exactly
j
elements from this set.
In other words, we need to show that
1
,...,
2
j
}
Search WWH ::
Custom Search