Shasha’s Shifty Witnesses

Five witnesses have trailed ten suspected dealers, and every one of the five is a liar some of the time. Each witness votes on each suspect, “has drugs” or “no drugs,” and all we are handed is the tally: for each suspect, how many of the five cried “drugs.” We are told two things more, that the witnesses lie eight or nine times across the fifty votes, and that most of those lies are cowardly ones, calling a real dealer clean. From this thin and untrustworthy evidence the truth is to be recovered. The puzzle is Dennis Shasha’s, and Chlond’s trick is to let the unknown facts and the known claims sit in the same integer program and force them into agreement.

The puzzle

The tally is the only hard data. Writing $d_j$ for the number of witnesses who accused suspect $j$, the votes run $$d = (5,\,0,\,2,\,5,\,4,\,0,\,3,\,5,\,0,\,1)$$ for suspects $1$ through $10$, the remaining $5 - d_j$ in each case having voted “no drugs.” Three suspects drew a unanimous accusation, three a unanimous acquittal, and the middle four are split. A witness who accuses an innocent suspect has lied, and so has one who clears a guilty one; the puzzle fixes the total number of lies at eight or nine, and adds that the lies which clear the guilty outnumber those that frame the innocent. Which suspects deal?

The model

Variables

The facts and the claims need separate names. Let $x_j = 1$ mean suspect $j$ deals, the unknown to be found. Let $y_{ij} = 1$ record that witness $i$ voted “drugs” on suspect $j$, the claim. The art is in two more families that mark the true statements: $v_{ij} = 1$ when witness $i$ truly says “drugs” (voted “drugs” and the suspect deals), and $w_{ij} = 1$ when witness $i$ truly says “no drugs” (voted “no drugs” and the suspect is clean).

Pinning each claim to the facts

The tally is honoured directly, $$\sum_{i} y_{ij} = d_j \qquad (\text{all } j) .$$ A true accusation is the logical and of the vote and the fact, $v_{ij} = y_{ij} \wedge x_j$, which a pair of inequalities pins exactly: $$y_{ij} + x_j - v_{ij} \le 1, \qquad y_{ij} + x_j - 2\,v_{ij} \ge 0 .$$ The first forces $v_{ij} = 1$ once both the vote and the fact are present; the second forbids it whenever either is absent. A true acquittal is the and of the two negations, $w_{ij} = (1 - y_{ij}) \wedge (1 - x_j)$, pinned the same way with the signs turned around: $$y_{ij} + x_j + w_{ij} \ge 1, \qquad y_{ij} + x_j + 2\,w_{ij} \le 2 .$$ Every vote is now labelled true or false by its own $v$ or $w$, and the labels are bound to the hidden $x_j$ they depend on.

Counting the lies

A statement is a lie exactly when it is neither a true accusation nor a true acquittal, so the truths number $\sum_{ij} (v_{ij} + w_{ij})$ and the puzzle’s “eight or nine lies” caps the truths between $41$ and $42$: $$41 \le \sum_{ij} (v_{ij} + w_{ij}) \le 42 .$$ The last clue, that clearing the guilty is the commoner lie, asks for more false acquittals than false accusations. Because exactly $\sum_j d_j = 25$ of the fifty votes cried “drugs” and the other $25$ cried “no drugs,” the true and false counts on each side balance, and that lopsided-lies condition is the same as asking for more true accusations than true acquittals: $$\sum_{ij} v_{ij} - \sum_{ij} w_{ij} \ge 1 .$$ There is nothing to optimize; any board obeying every line is the answer.

The solver

from ortools.sat.python import cp_model

def find_dealers(d):
    m, n = 5, len(d)            # 5 witnesses, n suspects
    M = cp_model.CpModel()
    x = [M.NewBoolVar("") for _ in range(n)]      # suspect j deals
    y = [[M.NewBoolVar("") for _ in range(n)] for _ in range(m)]
    v = [[M.NewBoolVar("") for _ in range(n)] for _ in range(m)]
    w = [[M.NewBoolVar("") for _ in range(n)] for _ in range(m)]
    IJ = [(i, j) for i in range(m) for j in range(n)]
    for j in range(n):
        M.Add(sum(y[i][j] for i in range(m)) == d[j])    # votes match tally
    for i, j in IJ:                      # v = vote AND fact, w = neither
        M.Add(y[i][j] + x[j] - v[i][j] <= 1)
        M.Add(y[i][j] + x[j] - 2 * v[i][j] >= 0)
        M.Add(y[i][j] + x[j] + w[i][j] >= 1)
        M.Add(y[i][j] + x[j] + 2 * w[i][j] <= 2)
    truth = sum(v[i][j] + w[i][j] for i, j in IJ)
    M.Add(truth >= 41)                   # eight or nine lies among fifty
    M.Add(truth <= 42)
    lie = sum(v[i][j] for i, j in IJ)
    M.Add(lie - sum(w[i][j] for i, j in IJ) >= 1)
    s = cp_model.CpSolver()
    if s.Solve(M) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None
    return [j + 1 for j in range(n) if s.Value(x[j])]

The thin data is enough: the program names suspects $1, 4, 5, 7, 8, 10$ as the dealers, and no other set of suspects can satisfy the clues, so the answer is forced. Nine witnesses lied, seven of them clearing a guilty suspect and two framing an innocent one, just as promised. The verdict is laid out in Figure 28.1: the three unanimous accusations and the four-vote suspect convict cleanly, and the surprises are suspect $3$, accused twice yet innocent, and suspect $10$, accused only once yet guilty.

Reading the deduction

The puzzle is a lesson in keeping fact and claim apart and then welding them. The variables $x_j$ hold what is true; the $y_{ij}$ hold what was said; and the $v_{ij}$, $w_{ij}$ are the rivets, each an and of a claim with a fact, turned into a pair of linear inequalities. Once a statement’s truth is a variable, counting lies is just summing, and a clue as soft as “most lies run one way” becomes a single inequality. The same move, a product of two binary decisions replaced by a fresh binary and two inequalities, is the workhorse of logical modelling, and it is what lets a solver reason about who is telling the truth when none of the witnesses can be trusted to.

Sources. The formulation follows Martin J. Chlond, Shasha’s Shifty Witnesses: An IP Lie Detector, INFORMS Transactions on Education volume $7$, number $3$ ($2007$), pages $238$–$239$. The puzzle is from Dennis E. Shasha, Puzzling Adventures (W. W. Norton, $2005$), and first appeared in his Scientific American column of February $2002$; it is in the tradition of Raymond Smullyan’s knights-and-knaves logic. The dealers $\{1, 4, 5, 7, 8, 10\}$, the uniqueness of that verdict, and the nine-lie split (seven clearing the guilty, two framing the innocent) are reproduced and checked here, the verdict’s uniqueness by exhaustion over all $2^{10}$ possible guilty sets.