Home > Uncategorized > The Traversal Problem (3 dimensions)

The Traversal Problem (3 dimensions)

[This problem is related to the easier 2-dimensional “Diagonal Problem” – click here for a full solution to the 2d problem]

1. Imagine a cuboid made up of lots of little cubes.

2. Imagine a straight line (or “traversal”) connecting two opposite vertices of the cuboid

3. How many little cubes does the line pass through?

cuboid_colour2 Diagram 1

Note: Cubes are only counted if the traversal passes through them, so if your traversal goes exactly through a vertex or an edge separating cubes within the cuboid, then it is not considered to pass through the adjacent cubes.  In the 2×3×4 example shown, the traversal actually passes through an edge in the centre of the cuboid.

Problem: How many cubes does a traversal pass through in a 60×120×156 cuboid?  (Hint: Start small!)

Recap of Solution in 2 dimensions

In the 2d situation, when the diagonal passes from one row to the next, it either passes through a ‘vertex’ of a square or through a ‘side’ of a square.  Sides are easy – we effectively ignore them.  Vertices (corners) are more complicated – we effectively lose a square when the diagonal passes from one row to the next via a vertex.   The number of times this occurs in a rectangle is equal to the highest common factor of the two lengths, so we must subtract the highest common factor from the sum of the two lengths.

(Note: in the US, ‘highest common factor’ is popularly called ‘greatest common divisor’)

So the solution in 2 dimensions, algebraically, is

Solution in 2 dimensions

(This just means: length of one side, plus length of the other side, minus the highest common factor of the two lengths.

Solution in 3 dimensions

Visualising the 3-d problem is a nightmare.  Consider this graphic, which shows only the traversed cubes in some different types of cuboid, and how they look if you view them ‘down the line’.

In the 3d situation, without worrying about what goes on inside the cuboid, the simplest model is to simply add together the length x, the width y and the depth z.

Incorrect formula stage 1

But this model isn’t accurate enough for us.  It’s not wrong, it just needs refining!  So we have a bit of work to do.

When the line passes from one row to another, it either passes through a ‘face‘ of a cube, an ‘edge‘ of a cube, or a ‘vertex‘ of a cube.

Faces are easy – we can effectively ignore them, just as we ignored sides of squares in the 2-d problem.  Adding together x, y and z takes care of faces.  Edges and vertices are where we need to focus next.

Edges

To get our head around edges, let’s consider the 2x3x4 cuboid.  We can observe the image from 3 different perspectives:

We can treat each of these as a 2d problem, remembering that when the diagonal appears to pass through a vertex of a square, it is actually passing through an edge of a cube.

In the 2d problem we subtract the highest common factor of the length and the width of a rectangle, so in each of these three elevations – top, front and side – we can do the same, and combine them into one formula:

Incorrect formula stage 2

Are we there yet?

Almost.  Let’s substitute into this formula the values of x, y and z from the original example at the top of the page.

The answer we’re after is 6 cubes, but this formula delivers the answer 5.  Alarm bells are ringing, because clearly we need to add something back on if we’re to upgrade this formula further.

Vertices

Vertices seem, at first, a littler easier to deal with.  The number of times the traversal passes through a vertex is equal to the highest common factor of all three lengths.

The issue is how to incorporate this into our formula.  Up to this moment, including in the 2-d problem, we have had to subtract HCF’s to cater for times when the traversal passes from one row to another using the ‘shortcut’ of passing through a corner (of a square) or, in the 3-d problem, an edge or a vertex (of a cube).  Here, it’s still true that we ‘lose’ cubes when this happens, but actually we’ve already more than catered for them.

Think about the nature of a vertex of a cube.  What is it surrounded by?  Edges of course!  So when the line passes through a vertex, it is simultaneously passing through three edges, one in each of the orientations discussed above.  Therefore, when we subtracted the paired HCF’s, we were actually subtracting the triplet HCF too, but we did it twice!  (Look how many times x, y and z each appear in ‘Incorrect formula stage 2a’ above – each appears twice.)

Consequently we need to add one triplet HCF back on.

Our solution:

The original problem was: How many cubes does a traversal pass through in a 60×120×156 cuboid?

We just need to substitute x=60, y=120 and z=156 into the formula:

60 + 120 + 156
– HCF(60,120) – HCF(120,156) – HCF(60,156)
+ HCF(60,120,156)

= 336 – 60 – 12 – 12 + 12

= 264 cubes

Easy?

What about the 4-dimensional traversal problem?

What about the n-dimensional traversal problem?

  1. Saksham
    October 4th, 2010 at 13:54 | #1

    Yupp 😀

    Hope to see other nice questions.

  2. Micky
    October 3rd, 2010 at 10:17 | #2

    That’s the ticket. Nice work. Sorry for the insult!
    Notice the binomial sequences:

    2d solution: [1]HCF(0 at a time) + [2]HCF(1 at a time) – [1]HCF(2 at a time)
    3d: solution: [1]HCF(0 at a time) + [3]HCF(1 at a time) – [3]HCF(2 at a time) + [1]HCF(3 at a time)

    4d: [1]HCF(0 at a time) + [4]HCF(1 at a time) – [6]HCF(2 at a time) + [4]HCF(3 at a time) – [1]HCF(4 at a time)

    and so on…

  3. Saksham
    October 3rd, 2010 at 08:25 | #3

    And similar extension for 4 dimensions –
    x + y + z + a – (HCF taken 2 at a time) + (HCF taken 3 at a time) – (HCF taken 4 at a time)

  4. Saksham
    October 3rd, 2010 at 08:18 | #4

    Oh ya sorry 6, Haha don’t insult my mnetal maths by asking to check on excel :P.
    Nice 😀 resemblance to principle of inclusion-exclusion, and you demonstrate the solution very nicely!

  5. Saksham
    October 2nd, 2010 at 13:22 | #5

    Going by the 2D problem, can this be extended as
    l + b + h – hcf(l,b) – hcf(b,h) – hcf(h,l) + hcf(l,m,n) ?

    though for 2x3x4 it gives 7

    • Micky
      October 2nd, 2010 at 14:04 | #6

      That’s the right answer – excellent work.
      Check it again, it gives 6 not 7.
      In excel, type =2+3+4-GCD(2,3)-GCD(2,4)-GCD(3,4)+GCD(2,3,4)
      I’ve put the full solution up now
      Micky

  6. Rick
    September 26th, 2010 at 21:33 | #7

    Man it’s driving me bonkers! Would love to hear how it works!

  7. Rick
    September 24th, 2010 at 16:30 | #8

    Ok, thanks! Hope to hear soon!

  8. Rick
    September 21st, 2010 at 16:40 | #9

    What’s the full solution?

    • Micky
      September 21st, 2010 at 18:57 | #10

      give me a few days! busy part of the school term! micky

  9. June 24th, 2010 at 20:09 | #11

    You’re close Malley, I like what you’re doing with the -2 which considers the single node (or “vertex”) appearing at both ends of the line. But be careful as you may already have allowed for that. You’ve then considered the 90,120 pair and the 90,140 pair… what about the 120,140 pair?

    You’re very close

  10. Malley
    June 24th, 2010 at 18:53 | #12

    It’s got to be similar in that each block will be connected to 2 other blocks except for when passing through a node and at both ends of the line. so I recon start off with -2 for both ends then finding the nodes 90×120 = 30 nodes, 90×140 = 10, then for 3 dimensions 90+120+140-2-30-10=308?

  1. June 24th, 2010 at 09:45 | #1