Enigma 1711

Spoiler for New Scientist Enigma 1711:

In our town square is a piece of installation art consisting of 300 rods of equal length arranged in a cubic lattice. The whole structure balances on a single vertex, with the diagonally opposite vertex at the top. Each rod contains an LED strip light, which can be independently switched on and off. A microprocessor controls this, lighting up the rods that form the shortest continuous path between the bottom and top vertices.

Each combination of rods (meeting the shortest continuous path criterion) is lit up for 10 seconds, then another and so on, until all combinations have been displayed, when the cycle starts again.

How long does it take to complete a full cycle?

In a cubic lattice n cubes on a side, there are n3 small cubes which if separated would have 12n3 edges. In the lattice 12n of these edges lie on the edge of the big cube; each contributes 1 rod to the total. There are 4n2 edges lying in the each of the 6 faces of the big cube, of which 4n2–4n in each face are not on an edge of the big cube, or in total 24(n2n) such edges; each coincides with another such edge so each contributes 1/2 rod to the total. Left over are 12n3–12n–24(n2n) edges which lie in the interior of the big cube; each coincides with three other such edges so each contributes 1/4 rod to the total. Therefore there are 12n+12(n2n)+3n3–3n–6(n2n) = 3n3+6n2+3n = 3n(n+1)2 rods. For n = 1, 2, 3, 4… this is 12, 54, 144, 300… rods. So the installation art cube is 4 rods on a side.

So now how many ways can you draw the shortest path between diagonally opposite vertices? If we label the three mutually perpendicular edge directions as north/south, east/west, and up/down, then each such path starting from the south/west/downwardsmost vertex must contain exactly four steps to the north, four to the east, and four upwards. That is, 12 steps, four of each of three kinds. Or more generally, 3n steps, n of each of three kinds. The number of possibilities is (3n)!/(n!)3. For n = 1, 2, 3, 4… this is 6, 90, 1680, 34650… possible paths. So a full cycle for an n=4 cube at 10 seconds per path is 346500 minutes seconds or 240 4 days, 15 hours minutes.