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.

how many matchsticks are required to make a cube matchsticks 3 matchsticks 2 matchsticks 1

If you know the solutions to any of them, write them in the comments section below.

13 thoughts on “Matchsticks and n-dimensional hypercubes

  1. 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. 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. 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. 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

    That leads to:
    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. 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. 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. 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

Talk to me

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s