Playing pickup sticks against Jack Snoeyink would be no fun. While most of us have to rely on limited vision and intuition to decide which stick to move, Snoeyink gets to use computational geometry. While we're forced to ease sticks from the pile with trembling fingers, Snoeyink has a high-powered computer effortlessly do the risky removal for him. Most infuriating of all is that he can design a game you can't possibly win: a configuration of sticks in which you can't budge a single one.
Fortunately, Snoeyink, a mathematician at the University of British Columbia, isn't playing for fun; he's trying to get at the very nature of how things are put together and taken apart. And what better way than to play pickup sticks--or jackstraws or spillikins or mikado or any of the other names the game has been known by since its beginnings in China thousands of years ago. Because it goes straight to the heart of problems of assembly, pickup sticks appeals to technological tinkerers, mathematicians, and manufacturers in much the same way it appeals to children.
Since the early part of the century mathematicians have challenged themselves to build a structure that, like an unsolvable puzzle, can't be taken apart. Naturally they have some strict rules: they've done away with gravity, so the objects float as they could only in deep space or in the memory of a computer. And the objects to be taken apart must be convex: they can't have any hooks, notches, or inward curves; they can bulge outward, though they don't have to. Because these convex objects have nothing to grip onto, clusters of them could, in theory, always be disassembled if you could grab all the pieces at once and pull them apart, as if with a hundred hands. But the rules allow you to use only two hands-- one to hold the group still and the other to pull a piece straight out, without twisting. As in pickup sticks, if you disturb any of the neighboring pieces, you lose.
Even the most skilled gamester will find the challenge maddeningly difficult. Try it with any convex pieces--balls, blocks, chopsticks, watermelons--and you'll find that no matter what the configuration, a piece can always be removed. Over the years mathematicians have tried all kinds of wacky objects--spheres completely covered with tiles, stacked pyramids, square plates arranged into card houses, clusters stuck with headless pins like a voodoo doll--and all failed the test. It seemed impossible to make a structure that would remain stuck. Accordingly, a folk theorem arose among manufacturers and geometers, stating that any group of convex objects could be taken apart with two hands. That theorem held until last year, when Snoeyink brought out his bag of sticks.
These are no ordinary sticks; if you look closely, each one is a long, thin tetrahedron that appears to have been squeezed through a toothpaste tube. It has three triangular sides and an extended, tilted triangular base; one end appears fat and the other sharpens to a point. But give the stick a quarter turn and suddenly the pointy end is fat and the wide end appears sharp, and therein lies the stick's secret. Although its shape is convex, the stick can act as a wedge on both ends, so it can be stuck solidly into place. With six such sticks, Snoeyink built the configuration shown at left. Unless you twist as you pull, you can't slide any stick out. The ends all wedge against their neighbors.
To prove that no piece could be removed, no matter which way you pulled, Snoeyink had to demonstrate that each piece would run into resistance in all possible directions. He therefore examined all the surfaces where a piece was in contact with its neighbors. Each surface marked a boundary, like the wall of a prison cell, and thus a direction in which the piece was blocked. Snoeyink expanded these boundary surfaces into planes. If the planes intersected to form a fully enclosed space--a sealed prison cell--then he knew that the piece was trapped. But if the intersecting planes left an opening, then a piece could be pulled free like a prisoner lifted from a roofless jail cell. After examining the boundary surfaces for all his pieces, Snoeyink found that everything was indeed trapped. No individual stick could be moved without disturbing the others.
Snoeyink had proved the folk theorem wrong, but he wasn't satisfied yet. Even mathematicians have some respect for reality, and he knew that in real life, you can take things apart not just by pulling on the pieces but also by twisting them as you pull. Sometimes you can also remove them in combinations: there may be cases where one stick can't be moved without resistance but two together can. Snoeyink wondered whether it would be possible to build a structure that could withstand these additional manipulations. Teaming up with fellow geometer Jorge Stolfi from the University of Campinas in Brazil, he took five of his six-stick configurations and interlocked them into the 30-stick cluster shown at right. (Each six-stick model is color-coded so it's clear that there are five identical models within the larger cluster.) To enable the old sticks to fit perfectly in this more complex structure, Snoeyink and Stolfi made them 12-sided, thereby allowing each piece to rest snugly against its many neighbors. The new sticks also behave like wedges.
The problem with a 30-stick cluster is that there are more than a billion combinations of pieces that can be removed from the whole, and calculating whether each could be pulled out or twisted away would take more time than any mortal mathematician has available. To make the problem easier, Snoeyink and Stolfi reasoned that the 30-stick cluster has many symmetries, meaning that many of the pieces throughout the structure fit together in the same way. By determining that one group of sticks couldn't be removed from the whole, they could conclude that identical groups all around the cluster were also unremovable, thus eliminating redundant calculations.
This reduced the number of combinations to about 120,000--a difficult but not unmanageable number. Snoeyink's computer performed the calculations and delivered the verdict: the 30-stick object apparently remains stuck no matter which way you push, pull, or twist with two hands.
Snoeyink's stuck sticks don't merely satisfy mathematical curiosity; they also have practical applications. Since taking things apart is just the flip side of putting them together, Snoeyink's work is important for manufacturing. When a robot puts together a complex machine like a jet engine, it needs to know in what order to assemble the many interacting pieces. Currently computers have to calculate all the different assembly sequences and discard the bad ones. Snoeyink's puzzles, however, can lead to general rules about what can't be put together, ruling out certain sequences so a computer wouldn't even have to try them.
In Snoeyink's office stands a bookcase displaying a collection of puzzles: funky cubes and spheres with slotted pieces, models of his own six- and 30-stick configurations, and of course, sets of plain old pickup sticks. Hanging in the atrium of the computer science department is the giant 450-pound, brightly painted aluminum model he built of his 30-stick puzzle. "In some ways, doing any research is like doing a puzzle," says Snoeyink, "puzzles like 'How does a virus work?' or 'What's the latest particle in particle physics?' I just do the puzzles more literally than most researchers."
