cubes

[bugzpodder]

if we have a 25x20x15 box made up of 1x1x1 cubes, and we connect two opposite vertices with a line, how many cubes does that line go through? provide justification

[riis]

My answer is 50.

A 25x20x15 box can be split in 125 5x4x3 box, since all lengths are dividable by 5. The diagonal goes through only 5 of those 5x4x3 box, which are connected by opposite points. As you said as you wanted to know the number of small 1x1x1 cubes it goes through, it is safe to ignore the cubes the diagonal just touches.
The diagonal goes into three directions, x, y and z. For x the distance is 5 cubes, for y it is 4 and for z it is 3. Since x is the longest distance, I take that as the base. t is the distance traveled along the x axis.
At t = 1, 2, 3 and 4 the diagonal will hit a new cube.
For the y direction the diagonal will hit a new cube at 5/4, 10/4 and 15/4.
For the z direction the diagonal will hit a new cube at 5/3 and 10/3.

We start at a cube in one of the corners of the box, and then travel to the opposite cube.
The following list mentions t, the distance and the total sum of cubes.

0, n/a, 1
1, x, 2
5/4, y, 3
4/3, z, 4
2, x, 5
10/4, y, 6
3, x, 7
10/3, z, 8
15/4, y, 9
4, x, 10

Multiply the count by 5 (see above) and the total sum is 50.

I've attached an image which shows what I mean.
The upper left image shows x (left to right) and y (top to bottom). The double cubes indicate changes in z.
The upper right image shows y and z. The double cubes indicate changes in x.
The upper left image shows x and z. The double cubes indicate changes in y.
The red lines in all three images show the diagonal in the 5x4x3 box, projected on a plane.

[kedaman]

its possible for the line to pass trough a certain amount of boxes in a plane of boxes before entering another plane of boxes. The amount of boxes would depend on how many times the line crosses a side of a box, ideally (or maybe unideally?) if the line always crosses one side at a time you'd have 25+20+15=60 boxes to cross. However the line could though cross two (an edge) or three sides (a vertex) at a time but only enter one box (a box avoided in a edge, two boxes avoided in a vertex). If you factor the dimensions of the box: 5*5, 5*2*2, 5*3 you can determine the amount of crossed vertexes: 5-the common factor, there are no crossed edges though (no factor common to two dimensions) 2*5=10 boxes are avoided with these ideal conditions, thus 60-10=50 boxes are crossed.

[sql_lall]

I know that in 2D rectangles a x b, that the # of squares the diagonal goes through is [a + b - gcd(a,b)]

Perhaps for 3D it is [a+b+c-gcd(a,b)-gcd(b,c)-gcd(a,c)+gcd(a,b,c)]
However I haven't checked this.

[bugzpodder]

that formula sounds good to me!

obviously these cubes passes through integer coordinates.

so basically we want to find the number of coordinates with at least one integer coordinate it passes through from (0,0,0) to (15,20,25)(discounting (0,0,0))

as everyone else stated, it is 25+20+15.

however, there is a case where at least two of the coordinates are integral. subtracting the gcd would do the trick.

since 25=5*5, 20=4*5 and 15=3*5

gcd(25,20)=5 gcd(20,15)=5, gcd (25,15)=5

ie the coordinates are: (3,4,5) (6,8,10), (9,12,15) (12,16,20) and finally (15,20,25)

of course, since these coordinates are subtracted twice, adding on gcd(15,20,25)=5 would help