# Matchsticks and n-dimensional hypercubes

Here’s an addictive maths challenge for you to try.

It’s separated into four stages:

• blue (easy);
• green (medium);
• yellow (hard); and
• orange (very hard).

k = 3 in each example.

## 14 thoughts on “Matchsticks and n-dimensional hypercubes”

1. Giomini says:

In the first one the increment of matchsticks to add a layer is 2 for each match on the side, plus 4 to fill the corner. there are 2 sides. So, considering the existing structure to be of width (N-1), to add a layer you have to add ((N-1)*(2+2))+4=N*4.
This has to be repeated for each layer added up to the Nth. Building the structure results in growing a sum like this: Matchsticks= 4* sum x for x=1 to N= 4*(N(N+1))/2.

Matchsticks=2*(N(N+1)).

Tomorrow I’ll try the other ones.

Like

1. James Kennedy says:

That’s correct for two dimensions 🙂

Have you solved three, four and n dimensions?

Like

1. Giomini says:

Not yet, i’m busy studying for exams, but I think the same aufbau-like method could be applied to 3D, and then it should be possible to extract information about nD generic case.

Like

2. James Kennedy says:

How is this similar to aufbau?

Like

3. Giomini says:

You’re right, probably aufbau is not the best word, I meant layer by layer… onion-like will do 🙂

Like

4. Torben Pasucha says:

Just as an aside to the aufbau-argument, it was used correctly in so far as the meaning of the original German loan word is concerned.

I didn’t know this was a loan word in English. Pretty cool.

Like

2. Elio says:

In the same way Giomini says, a square is the extrusion of a line, a cube, a extrusion of a square… every time you make that extrusion, the previous number of sticks is repeated, but you have to add the new sticks that appear (those wich connect between them the slides that forms the new structure, minus one, because the last slide doesn’t have a slide to connect to), so naming:
k -> Width, but I use the number of “dots” instead the number of sticks (a stick connect two dots)… so the width in dots is the width in sticks plus one… I think this simplify the problem.
N -> Number of dimensions (N-D cube)
S -> Number of sticks

S(k,N) = S(k,N-1)*k+k^N-k^(N-1)

where:
S(k,N-1)*k -> Number of previous sticks, plus the width of the hypercube
k^N -> Number of dots of the hypercube. We have to add a stick for each one.
k^(N-1) -> Number of dots of the previous hypercube, those are not neccesary.

And working that in order to get a equations you find the solution…
S= N*k^N–N*k^(N-1)

The example of a square (2 dimensions) of 3 sticks (4 dots):
S = 2*4^2-2*4^1 = 32-8= 24

Cube (3 dimensions) of 3 sticks (4 dots):
S = 3*4^3-3*4^2 = 144 Sticks

Hypercube (4 dimensions) of 3 sticks (4 dots):
S = 4*4^4-4*4^3 = 768 sticks

I couldn’t check the last one, I couldn’t get hypersticks anywhere, blame it on this 3D word… 🙂

Like

1. James Kennedy says:

Well done! It can be simplified a little more, actually.

S = nk(k+1)^(n-1)

The number of matchsticks along in each dimension is always equal to k(k+1)^(n-1). For example, a 3x3x3 cube always has 48 vertical sticks, 48 horizontal and 48 along the z-axis because a cube has equal height, width and depth.

Next question: 6 matchsticks can be used to make a minus-3-dimensional cube of width minus-2. What does that mean? 😛

Like

3. winewithcats says:

Blue
The matches are oriented either horizontally or vertically. Looking at just the vertically oriented matches, there are 3 rows with 4 matches per row. Since this is a square lattice, symmetry doubles that amount. That gives a total of 2*3*4 matches, which can be expressed as

M(k,n|n=2) = nk(k+1)

Also worth noting is the number of points where the matches meet. There are 4 per row, and 4 rows; in this particular example, that gives us

P(k,n|n=2) = (k+1)2 = (k+1)n

Both of these formulas work for any value of k when n=2. It’s worth trying out various other values for k to convince yourself that n and k are used appropriately.

Green
To build a 3D lattice of width k, we just start with the 2D lattice of width k and extend it k times into the third dimension, giving us a stack of (k+1) 2D lattices, each joined to its neighbors by adding extra matches between corresponding pairs of points. The number of points is easy: it’s just (k+1) times the number of points in the 2D lattice, or

P(k,n|n=3) = (k+1)P(k,n-1) = (k+1)(k+1)2 = (k+1)3 = (k+1)n

The number of matches is also (k+1) times the matches in the 2D lattice, plus the number of matches required to join each lattice to its neighbors. The second term is k times the number of points in the 2D lattice. That gives

M(k,n|n=3) = (k+1)M(k,n-1) + kP(k,n-1) = (k+1)2k(k+1) + k(k+1)2 = 3k(k+1)2 = nk(k+1)(n-1)

Both of these formulas are the same for 3D as for 2D when expressed in terms of k and n; note that the exponent in the formula for M(k,2) is 1.

Yellow
The k-width tesseract is built in the same way as the k-width cube. We start with the cube and copy it k times into the fourth dimension, giving us a k-width hyperstack(?) comprising (k+1) k-width cubes, each one joined to its neighbors by adding matches between corresponding pairs of points. As before,

P(k,n|n=4) = (k+1)P(k,n-1) = (k+1)(k+1)3 = (k+1)4 = (k+1)n

Similarly,

M(k,n|n=4) = (k+1)M(k,n-1) + kP(k,n-1) = (k+1)3k(k+1)3 + k(k+1)3 = 4k(k+1)3 = nk(k+1)(n-1)

Orange
Since I have difficulty visualizing tesseracts, I’ve accidentally already answered this one in the process of trying to come up with an answer to the previous one.

The formulas are

M(k,n) = nk(k+1)(n-1) and
P(k,n) = (k+1)n

for any n and k.

For fun: do these formulas work for 0D and 1D? M(k,0) = 0 and P(k,0) = 1, for any k. This makes sense; we can imagine a 0D match lattice to be just a single point, and its width is meaningless in 0D.

If we extend that into 1D, using the same construction rule as described for 3D, then we should end up with M(k,1) = k = 3 matches and P(k,1) = (k+1) = 4 points. It’s trivial to check this with various values of k.

Similarly, the construction rule can be used to answer the 2D question in terms of 1D.

Like

1. winewithcats says:

Note: trailing n and (n-1) in the formulas should be read as superscripts.

Like

2. James Kennedy says:

Fascinating answer! I’d never considered the number of points (of intersection) before. The formula is beautifully simple. (Agreed — the last n and (n-1) should be superscript!)

Another interesting formula to figure out would be the number of faces–interior and exterior–in the whole object. Or a general formula for the volume of an n-dimensional ‘sphere’.

Or: “How many colours do you need to colour a chessboard (k=8) so that no two adjacent squares have the same colour on them?”

Followed by: “How many colours do you need to shade each external face of an n-dimensional ‘cube’ of width k so that no two adjacent squares have the same colour on them?”

Maybe I’ll save those for later 🙂

Like

4. winewithcats says:

I posted a longish answer yesterday, but wordpress seems to have eaten it 😦

Like

1. James Kennedy says:

Found it!

Like

5. Eric Smith says:

With width k=3, in three dimensions it’d take 192, correct?

Like