June 16, 2019

Averting Instant Insanity

MSRI Journal
The Mark of Zeta
The Return of Zeta
Solitaire-y Sequences
A Song About Pi
Row Your Boat
Juggling By Design

Averting Instant Insanity

Once called "The Great Tantalizer," the puzzle looks innocuous and seems quite simple. It consists of a set of four cubes with one of four colors on each of their six faces. Your goal is to arrange the four cubes in a row so that all four colors appear on each of the rows four long sides. The order of the cubes doesn't matter.

That simplicity is deceptive. There are 41,472 different ways of arranging the four cubes in a row. A trial-and-error approach to solving the puzzle would be hopelessly impractical.

Indeed, the puzzle's current incarnation bears the trade name "Instant Insanity." Marketed under various aliases, this tantalizer has been around for more than a century.

Here are the layout plans for the four cubes, colored red (R), green (G), blue (B), and yellow (Y).

It turns out that representing the colored faces of the cubes in terms of a mathematical construct called a graph allows you to solve the puzzle quite efficiently.

In general, a graph consists of an array of points, or nodes, joined by line segments, which are often called edges. Such an array can be very useful for visualizing relationships among various objects and attributes of those objects.

You can start by representing each cube by a graph of the colors that appear on opposite pairs of faces. Four nodes stand for the four colors of the puzzle, and edges link nodes corresponding to two colors on opposite faces. If a pair of opposite sides has the same color, you draw a loop connecting the node to itself.

Because a cube has three pairs of opposite faces, the graph representation of each cube has three edges linking four nodes, one for each color. Each edge has a numerical tag corresponding to the number of the cube on which that pair of colors resides.

In the first cube, for example, one edge would link G and Y, another edge would link G and B, and the third edge would be a loop beginning and ending at R. Each edge would be labeled 1.
The four graphs can then be combined into one representation, which shows the color relationship of the 12 pairs of opposite sides of the puzzle's four cubes. Because the puzzle's solution requires that the cubes be arranged in a row, eight of the 12 numbered edges give you the colors of each of the row's four sides.
To solve the puzzle, you need to find in this combined graph two separate subgraphs that each use all four nodes just once and each of the four edges, numbered from 1 to 4. Moreover, each node would have only two edges (or the two ends of a loop) emanating from it. One subgraph would represent the four front-back pairings, and the other would represent the four top-bottom configurations.

It turns out there is only one way of selecting two such systems without using any edge twice. (A given edge cannot represent both front-back and top-bottom at the same time.)

Look at the combined graph. Suppose you pick as your starting point the loop tagged 1, which is at R. You then need to pick edges tagged 2, 3, and 4, linking nodes Y, G, and B. That can't be done without violating the requirements.

If, instead, you start with the edge tagged 1 and joining B and G, you end up having to select edge 4 between R and B, edge 2 between R and Y, and edge 3 between G and Y. As required, all four colors and all four cubes are represented in the subgraph. It's easy then to work out the second subgraph.
Those subgraphs can then be used to arrange the cubes and solve the puzzle. Wei Zhang explained the details of how to do that in an entertaining book titled Exploring Math Through Puzzles: Step-by-Step Instructions for Making Over 50 Puzzles. It's largely a matter of following the edges in the right order along a particular circuit of the subgraph.

All this may look somewhat cumbersome, but the graph approach is surely more efficient than trying thousands of combinations with no guarantee of success. Those familiar with graph theory can typically work out the solution in minutes. Indeed, the puzzle serves as a neat lesson in logical thinking.

"Puzzles are problems done for fun. They are a form of entertainment, but also a form of exercise—a way to get your mind into shape," puzzle collector Stan Isaacs wrote in the preface of Exploring Math Through Puzzles. "They can excite students, stimulate thought, point to research, and involve students in their own educational process."

Originally posted August 9, 1999.

Matrices, Circles, and Eigenthings
Lunar Shadows
MSRI Reflections

No comments: