1. Introduction

The following puzzle is taken from Dennis Shasha's book "Puzzling Adventures", a lovely collection of mathematical puzzles embedded in a variety of quaint scenarios that belie the difficulty of the problems themselves. Many of the puzzles first appeared in Scientific American in a column of the same name and this particular one was printed in the February 2002 issue. It is very much in the spirit of the logical puzzles popularized by Raymond Smullyan in a series of books published over a twenty year period beginning in the late seventies (see especially "The Lady or the Tiger"). A complete list of Smullyan's puzzle books is in Chlond and Toase(2003).

The puzzle scenario involves five untrustworthy witnesses who have trailed ten suspected drug dealers. The witnesses are asked to vote on whether or not each of the suspects has drugs. The results are summarized as follows:

We are also told that the total number of lies among the witnesses is eight or nine and that most of the lies claim "no drugs" when the truth is "has drugs". Is it possible from this sparse and unreliable data to identify which of the suspects have drugs?

2. IP Formulation

A discussion of IP modeling of logical puzzles is in Chlond and Toase(2003) and a couple of these ideas have been put to use in the following formulation.

We define ranges M = 1..m and N = 1..n where m and n are, respectively, the number of witnesses and the number of suspects and we use subscripts i and j, respectively, to identify witnesses and suspects. We go on to define parameters and decision variables as follows.

2.1 Parameters

d_j = number of witnesses stating "has drugs" for suspect j

2.2 Decision Variables

v_i,j = 1 if witness i states truly that suspect j has drugs, else 0

w_i,j = 1 if witness i states truly that suspect j has no drugs, else 0

x_j = 1 if suspect j has drugs, 0 otherwise

y_i,j = 1 if witness i states that suspect j "has drugs", else 0

2.3 Constraints

The objective of the puzzle is merely to satisfy all the conditions and hence no objective function is required. The conditions are satisfied as follows.

The number of witnesses saying "has drugs" for each suspect is consistent with the puzzle.

Set tell truth "has drugs" variables

Set tell truth "no drugs" variables

Total truths consistent with puzzle

More truths regarding "has drugs" statements

The formulation was implemented in the Gnu Linear Programming Kit (GLPK) which will accept MathProg (a subset of AMPL) as input and the model file is here. A solution was also obtained using Excel and a spreadsheet with Solver instructions is here.

Incidentally, GLPK is well worth investigating by those instructors who wish to teach mathematical programming using a modeling language but are put off by the high cost and restrictive academic licences of some of the better known commercial packages. As an example of the performance of GLPK the above puzzle was solved in 36 seconds on a P4 1.4 MHz laptop. In contrast, Excel Solver took 96 minutes to obtain a solution on the same computer. The home page for GLPK is http://www.gnu.org/software/glpk/.

References

Chlond, M.J. and Toase C.M., (2003), "IP Modeling and the Logical Puzzles of Raymond Smullyan", INFORMS Transactions on Education, Vol. 3, No 3,

Shasha, D.E., (2005), Puzzling Adventures, W.W. Norton

Smullyan, R., (1982), The Lady or The Tiger, Alfred A. Knopf, Inc.