[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?

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!)

Tweet

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

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

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:

-

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?