Fairground Attractions

Sam Loyd advertised a Coney Island booth as “The Squarest Game on the Beach.” Ten dummies stand in a row, each painted with a number, and for a cent a throw you may topple as many as you can. Make the toppled numbers add to exactly fifty, no more and no less, and you win a twenty-five cent cigar. The numbers are $3, 6, 9, 12, 15, 30, 21, 25, 27$ and $30$. Stand as close as you like. It sounds generous. It is a swindle, and the cleanest way to see why is to ask a solver to win.

The squarest swindle

Toppling a subset to hit a target is the binary knapsack in its barest form: a $0/1$ variable per dummy, one equation fixing the sum. The same model, with the variables allowed to count past one, handles a companion Loyd puzzle in which an archer scores a target with repeated shots at rings worth $16, 17, 23, 24, 39$ and $40$.

from ortools.sat.python import cp_model

def reach_target(values, target, repeat=False):
    m = cp_model.CpModel()
    hi = target if repeat else 1               # repeat: a value may recur
    x = [m.NewIntVar(0, hi, "") for _ in values]
    m.Add(sum(v * xi for v, xi in zip(values, x)) == target)
    s = cp_model.CpSolver()
    if s.Solve(m) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None                            # target is unreachable
    return [s.Value(xi) for xi in x]

For the archer the model finds a score at once, for instance four shots at the seventeen and two at the sixteen, $4 \cdot 17 + 2 \cdot 16 = 100$. For the beach booth it returns nothing: no subset of the ten dummies sums to fifty. The booth cannot be beaten, and the reason survives without the solver. Every number on a dummy is a multiple of three except the lone twenty-five. A subset that leaves the twenty-five out sums to a multiple of three; a subset that takes it in sums to one more than a multiple of three. Fifty is neither, being two more than a multiple of three, so no choice can reach it. The barker keeps his cigars, and the integer program reports the swindle as a plain infeasibility.

The pile of cans

A stall with an honest target makes a richer model. Three piles of cans stand on a shelf, three to a pile, and you have three throws. The second throw counts double, the third triple, and you may only strike the exposed top can of a pile, so toppling one uncovers the can beneath for a later throw. The cans carry the values of Figure 43.1, and the target is exactly fifty.

Now the order of throws matters and so does what each throw uncovers. Let $x_{ijk}$ mark that the can at depth $i$ in pile $j$ is struck by throw $k$; the target weights each hit by its throw number, and a precedence rule lets a deeper can be hit only once the can above it has fallen on an earlier throw.

from ortools.sat.python import cp_model

V = {(1, 1): 8, (1, 2): 10, (1, 3): 7,     # value at (depth, pile)
     (2, 1): 10, (2, 2): 7, (2, 3): 9,
     (3, 1): 7, (3, 2): 9, (3, 3): 8}

def solve_cans(target=50, n=3):
    m = cp_model.CpModel()
    P = range(1, n + 1)
    cells = [(i, j, k) for i in P for j in P for k in P]
    x = {c: m.NewBoolVar("") for c in cells}
    m.Add(sum(k * V[i, j] * x[i, j, k] for (i, j, k) in cells) == target)
    for i in P:
        for j in P:
            m.Add(sum(x[i, j, k] for k in P) <= 1)  # each can once
    for k in P:
        m.Add(sum(x[i, j, k] for i in P for j in P) == 1)
    m.Add(sum(x[1, j, 1] for j in P) == 1)  # throw 1 hits a top can
    for i in P:
        for j in P:
            for k in P:
                if i > 1:  # uncover from above first
                    m.Add(x[i, j, k] <= sum(x[i - 1, j, l]
                                            for l in range(1, k)))
    s = cp_model.CpSolver()
    s.Solve(m)
    return sorted((k, i, j) for (i, j, k) in cells if s.Value(x[i, j, k]))

There is one way to do it, drawn in Figure 43.1: the first throw takes the seven from the top of pile three, the second takes the eight from pile one and counts as sixteen, and the third takes the nine now exposed in pile three and counts as twenty-seven. Seven, sixteen and twenty-seven make fifty. Adding the no-good cut that forbids this exact triple and solving again confirms there is no other.

Sources. The “Squarest Game on the Beach” and the archery target are from Sam Loyd, Cyclopedia of Puzzles (The Lamb Publishing Company, New York, $1914$), page $8$; the pile-of-cans puzzle is from Tony Love’s Mathematical Puzzles ($2011$). The integer-programming treatment of all three, the knapsack and sequenced-knapsack formulations, and the use of the model to expose the beach booth as unwinnable and to check the cans puzzle for uniqueness, are from Martin J. Chlond, Puzzle—Fairground Attractions, INFORMS Transactions on Education volume $12$, number $2$ ($2012$), pages $114$–$115$. The infeasibility of the fifty target, the archer’s hundred, and the unique cans solution are all reproduced by the models above; the fifty’s impossibility is confirmed independently by the residue argument modulo three.