How to Poison Your Mother-in-Law, and Other Caching Problems - Search Theory: A Game Theoretic Perspective - page 148

10.1 The Kikuta-Ruckle Conjecture

The Kikuta-Ruckle conjecture arose from a series of papers on search games and
optimal allocation that were written by Ken Kikuta and William Ruckle [ 9 - 11 ]over
a number of years. In fact, there is not one, but there are several conjectures that
can be found dispersed over these papers. In this chapter we discuss one of these
conjectures, as well as its ramifications into search games, which have led to some
fascinating new results on expanding search that have been reported by Tom Lid-
better in Chap. 2 . The interplay of game theory and combinatorics is a hallmark of
Ruckle's work. It is manifest in the two cable ambush game, as described in the
previous chapter by Vic Baston and Ian Woodward. The Kikuta-Ruckle conjecture
is no different.
Suppose your mother-in-law comes over for tea. You know that she is going to
eat k biscuits from a tray that contains n biscuits in total, but you do not know which
biscuits she is going to take. Each biscuit is equally likely. You possess h grammes
of arsenic, where h 1 is a real number. The lethal dose of arsenic is one gramme.

Unfortunately, you cannot put the poison in her tea, you have to put it in the biscuits.
How should you distribute the poison to maximize the probability that your mother-
in-law gets the lethal dose?

>

Kikuta-Ruckle Conjecture ([ 11 ]) It is optimal to put a dose of 1 / j in as many

biscuits as possible, for a natural number j that depends on h , k , n .

Here, optimal means that the distribution maximizes the number of k -element sub-
set such that the cumulative amount is lethal. To illustrate this conjecture we first
present a solution for the particular case of k

5, which involves
the Petersen graph, see Fig. 10.1 . Each vertex represents a possible selection of
three biscuits, and two vertices are neighbors if and only if they have exactly one
biscuit in common. The solution of k

= 3and n =

= 3and n = 5breaksupintotwoparts,de-

pending on the value of h :
3
2 ≤

5
3 : Any circuit of length five contains contains each biscuit exactly thrice.
So the amount of poison in the circuit adds up to 3 h

h <

5. Therefore, any circuit
contains at least one non-lethal vertex. Any pair of vertices can be avoided by a
circuit of length five, so there are at least three non-lethal vertices. Now it is not
hard to see that a poison distribution of

<

1
2 ,

1
2 ,

1
2 ,

0 , 0 is optimal. So the conjecture

holds with j = 2 in this case.

3
2 : There must be adjacent vertices that are lethal, otherwise there would
hardly be any. Adjacent vertices share one common biscuit. If both vertices are
lethal, the common biscuit contains a dose of

1 ≤ h <

1
2 since h

2. It follows that any
other lethal vertex contains this particular biscuit. So we may just as well put a unit
dose in it. The conjecture holds with j

> < 3 /

=

1 in this case.