Welcome to NRICH.

 
Diagonal of a cuboid: how many unit cubes does it pass through?
By Louise (P4118) on Thursday, March 22, 2001 - 10:13 am:

I've got this problem to solve and I haven't the first clue how to get in to it... Can someone please help me!

Take some 1 unit cubes and construct a rectangle or cube whatever with them with dimensions x by y by z. Now taking the leading diagonal of your 3D rectangle...how many cubes does it intersect?

I realise with a cube the answer is trivial but what about conjectures for any x, any y and any z?
Thankyou
Louise 18.

By James Lingard (Jchl2) on Thursday, March 22, 2001 - 10:28 am:

Louise,

Try thinking first about the 2D case, i.e. if you have an x by y rectangle, how many of the unit squares does a diagonal intersect? This is considerably easier to visualise, and I think that the answer to this problem is very similar to the 3D case.

James.

By Louise (P4118) on Thursday, March 22, 2001 - 12:02 pm:

Thank you for your quick reply.

I have investigated the 2D case and come up with several conjectures. However am finding it extremely difficult to apply to a 3D case. Does the z-dimension of it all upset all the conjectures proven in the 2D case? Is there any arithmetic to apply to this problem?

In the 2D case gradients were used to aid an explanation, as well as whether the leading diagonal cut any grid points. Any suggestions?

Louise x

By James Lingard (Jchl2) on Thursday, March 22, 2001 - 12:10 pm:

OK, what exactly is your understanding of what's going on in the 2D case? What have you worked out so far?

You mention "whether the leading diagonal cuts any grid points" - this is indeed the key to this problem. The question is, what exactly are the conditions under which the leading diagonal passes through a grid point, and, if it does, how do you calculate how many grid points the leading diagonal will pass though?

James.

By Louise (P4118) on Thursday, March 22, 2001 - 12:26 pm:

Take a mxn grid. If m=n the f(m,n)=m obviously.
If m=2n then f(m,n)=m, eg. For m=6,n=3 the diagonal is crossing a 2x1 rectangle 3 times!
Thinking in terms of co-ordinates and equation of diagonal. m=kn when k is some integer. eg. (9x3) the diagonal y=1/3x, so cuts (3,1),(6,2) or the 3x1 grid 3 times. Therefore f(9,3)=3x3=9.

So in general for m=kn grid pts crossed are; (n,1),(2n,1),(3n,1),([k-1]n),(k-1). Ie the nx1 grid k times. And finally it appears that if m,n have no commmon facors the diagonal does not go through any internal grid points. Where next?

Again thankyou for you super quick reply.
Louise x

By James Lingard (Jchl2) on Thursday, March 22, 2001 - 12:43 pm:

OK, you're almost there.

I think you meant to say that if m = kn, the grid points crossed are

(n,1), (2n,2), (3n,3), ..., ([k-1]n,[k-1])

So how many grid squares will the diagonal pass through in this case?

You've also correctly pointed out that if m and n have no common factors then the diagonal doesn't pass through any internal grid points. (Can you prove this?) So in this case, how many squares does the diagonal pass through?

Once you've worked out these two, think about the general case. You might find it helpful to write m = ha and n = hb, where h is the highest common factor of m and n, and so a and b have no common factor.

James.

By Louise (P4118) on Thursday, March 22, 2001 - 06:50 pm:

Could I prove that if m and n have no common factors then the daigonal doesn't pass through any internal grid points by induction. If so could you show me how to do it?
Thankyou
Louise x

By James Lingard (Jchl2) on Friday, March 23, 2001 - 01:23 am:

I suppose you might be able to use induction, but that would be overkill really.

I'd argue something along the lines of:

If the diagonal passes through the grid point (x,y) then the gradient of the line is y/x.

So y/x = n/m. But then my = nx, and so dividing by m gives y = nx/m. But since hcf(m,n) = 1, x/m must be an integer, and so x ³ m, which means that the grid point the diagonal passed through must actually be just the corner of the rectange, not an internal grid point.

I hope that makes some sense - it's a bit late for total coherence on my part I'm afraid...

James.