Diagonal of a Grid

We need

so

Let $d=\gcd(m,24)$

Then $m=d+6$

Since $d=\gcd(d+6,24)$, we have $d\mid d+6$, so $d\mid6$

Therefore, $d=1,2,3,6$

For $d=1$, $\gcd(7,24)=1$, so $m=7$

For $d=2$, $\gcd(8,24)=8$, so this does not work

For $d=3$, $\gcd(9,24)=3$, so $m=9$

For $d=6$, $\gcd(12,24)=12$, so this does not work

Therefore, $m=7$ or $9$

Let $d=\gcd(m,n)$ and write $m=dm'$, $n=dn'$ where $\gcd(m',n')=1$

Since the grid contains 120 cells

so

Therefore, $d^2\mid120$

Also, the diagonal passes through 25 cells, so

Substituting $m=dm'$ and $n=dn'$

Therefore, $d\mid25$

We need both $d\mid25$ and $d^2\mid120$

The only possibility is $d=1$

Hence

Together with

we get $(m,n)=(6,20)$ up to order

But $\gcd(6,20)=2$, which contradicts $d=1$

Therefore, no such rectangular grid exists.

Consider an $a\times b\times c$ grid and draw the space diagonal from $(0,0,0)$ to $(a,b,c)$

We want to find how many unit cubes the diagonal passes through.

The diagonal intersects $a-1$ interior planes perpendicular to the $x$-axis, $b-1$ interior planes perpendicular to the $y$-axis, and $c-1$ interior planes perpendicular to the $z$-axis

So at first we have

intersections.

However, some of these intersections occur at the same point.

Intersections of Two Families of Planes

The diagonal intersects an $x$-plane and a $y$-plane at the same point exactly when the corresponding point has both $x$- and $y$-coordinates integers

The number of such interior points is $\gcd(a,b)-1$

Similarly, the numbers of simultaneous intersections are $\gcd(a,c)-1$ and $\gcd(b,c)-1$

Therefore, we subtract

But now a point where all three families of planes meet has been subtracted too many times.

The number of interior points where all three coordinates are integers is $\gcd(a,b,c)-1$

so by inclusion-exclusion, we add these back.

Therefore, the number of distinct interior intersection points on the diagonal is

which simplifies to

These intersection points divide the diagonal into one more part than the number of intersections.

Therefore, the number of cubes crossed is