**From New Scientist #2878, 18th August 2012** [link]

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?

[enigma1711]

### Like this:

Like Loading...

The following Python program recursively enumerates all shortest paths. It runs in 100ms

Solution:A complete cycle takes 96 hours and 15 minutes.The On-line Encyclopedia of Integer Sequences, has a formula that lets you calculate the answer directly.

Although another way of looking at it is that a minimal path from (0, 0, 0) to (x, y, z) has

x+y+zsteps (as there arexsteps in the x-direction,ysteps in the y-direction andzsteps in the z-direction). So, considering the path as being a sequence ofx+y+zslots each to be filled with the direction of travel, we can see that for the x-direction there are C(x+y+z,x) ways of filling these out (where C(n,k) is the standard combinatorial choice function), then for the y-direction we can chooseyslots from the remainingy+z, so C(y+z,y), and then all the remaining slots are in the z-direction.Hence the number of minimal paths is:

So for paths from (0, 0, 0) to (

n,n,n) this simplifies to (3n)!/(n!)^3.By generalising the construction of Pascal’s triangle to 3 dimensions (and using memoization):

My solution was so similar to Jim’s that I wasn’t going to publish but Arthur’s use of caching reminded me of just how powerful this technique can be. To test this, here is a version of the code to enumerate the number of shortest paths in a 100 x 100 x 100 cubic lattice:

It enumerates the paths in the cube in around 1 second to give:

376523493564631064367712071965768747782444205128669798396168767743500485766630075466163294008566118208045715304490994009624725072511252178400