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

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

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

–

Yupp 😀

Hope to see other nice questions.

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…

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)

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!

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

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

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

Ok, thanks! Hope to hear soon!

What’s the full solution?

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

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

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?