## Crossing the Parallelepiped

*Another fine puzzle submitted by Bilbao!*

A parallelepiped (rectangular box) measures 150 x 324 x 375 and is built of 1 x 1 x 1 cubes. A diagonal crosses the solid from one corner to the opposite corner. The diagonal passes through the interior of how many of these cubes?

Bobo The Bear| PUZZLE MASTER | Profile May 26th, 2010 - 11:23 pmAfter some trial and error on some smaller examples, I think the general formula for a LxWxH parallelepiped is a form of the “inclusion/exclusion” counting principle:

#cubes = L + W + H – gcd(L,W) – gcd(L,H) – gcd(W,H) + gcd(L,W,H)

In this case, with L=375, W=324, and H=150, I get

#cubes = 375 + 324 + 150 – 3 – 75 – 6 + 3 = 768 individual cubes.

Thanks, Bilbao, for giving my math mind another solid workout!

Falwan| Profile May 27th, 2010 - 6:46 amsqrt(324*324+375*375+150*150)/sqrt3 = 89367 cubes

Falwan| Profile May 27th, 2010 - 6:54 amLarge diagonal passing thru:

89387 – 2 = 89385 cubes

Shawn| PUZZLE GRANDMASTER | Profile May 27th, 2010 - 2:41 pmI’m getting 786, should be close but this is a tough one, might not be exact.

brianu| Profile May 28th, 2010 - 9:20 pm847?

Jimmy Anders| PUZZLE MASTER | Profile May 30th, 2010 - 12:04 amI get 768.

Hex| PUZZLE MASTER | Profile June 2nd, 2010 - 7:50 amThe idea is to divide each of the x, y, and z directions into planes at integer intervals that the diagonal crosses.

Equation of diagonal: x/324=y/375=z/150 where x in [0,324], y in [0,375], and z in [0,150]

Planes are of the form: x=Kx, y=Ky, and z=Kz

Solving for the x planes yields 325 intersections, 3 of which have x,y, and z as integers

Solving for the y planes yields 375 intersections, 3 of which have x,y, and z as integers

Solving for the z planes yields 150 intersections, 3 of which have x,y, and z as integers

Common intersections to x, y, and z: 4

Common intersections only to y and z: 72

Common intersections only to x and y: 0

Common intersections only to x and z: 0

Total number of distinct intersections=325+375-4-72+150-4=770

APEX.JP| Profile June 2nd, 2010 - 5:46 pmNot so much much a difficult puzzle but certainly challenging.

I used vector graphics to map the projected path through three views looking for a repeatable pattern.

It was necessary to accurately map 1/3rd of the full path to calculate the total result.

Mapping:

(X)axis = 150

(Y)axis = 324

(Z)axis = 375

Based on the X-Y view I verified repeatable quantities from two distinct patterns:

Pattern 1 3*3cubes projected = 15cubes total

Pattern 2 1*4cubes + 2*3cubes projected = 16cubes total

Quantities (1/3rd):

P1 15*11 = 165

P2 16*6 = 96

Tot(1/3rd) = 261

Quantities (Full)

Tot = 261*3

TOTAL = 783

Hex| PUZZLE MASTER | Profile June 3rd, 2010 - 4:04 amIt seems I missed the conclusion in my above post:

The last common intersection (324,375,150) should be excluded as it is an exit without re-entry.

So the number of cubes is 669.

deepside0058| Profile June 5th, 2010 - 4:00 amI’m pretty sure it’s 375. :-B

bilbao| Profile June 8th, 2010 - 3:19 amThe solution I have for this one is 768.

The mathematical way of solving it is the one followed by Bobo The Bear.

Since I didn’t know function ‘gcd’ could be used for this, I solved it with the help of excel:

Common intersections only to x and y: 0 –> (-0 cubes)

Common intersections only to y and z: 72 –> (-72 cubes)

Common intersections only to x and z: 3 –> (-3 cubes)

Common intersections to x, y, and z: 3 –> (-6 cubes)

Thus: #cubes = 375 + 324 + 150 – 0 – 72 – 3 – 6 = 768 cubes

Hex| PUZZLE MASTER | Profile June 8th, 2010 - 7:05 amI must have been high when I posted:

“Total number of distinct intersections=325+375-4-72+150-4=770

The last common intersection (324,375,150) should be excluded as it is an exit without re-entry.

So the number of cubes is 669.”

I used 325 instead of 324, and assumed 770-1=669

The correct solution is:

Total number of distinct intersections=324+375-4-72+150-4=669

Less (324,375,150) which should be excluded as it is an exit without re-entry: 669-1=668

Good puzzle Bilbao. I used excel too >:>

Hex| PUZZLE MASTER | Profile June 8th, 2010 - 7:07 amI do need a vacation.

The correct solution is:

Total number of distinct intersections=324+375-4-72+150-4=769

Less (324,375,150) which should be excluded as it is an exit without re-entry: 769-1=768

suineg| PUZZLE MASTER | Profile June 8th, 2010 - 9:15 amThis problem was far beyond my mathematical wisdom, very very hard, congrats to the ones that got it right.

@Bobo the Bear: without using Excel how do you get the intersections between the planes, and what gdc stands for, thanks, cool

suineg| PUZZLE MASTER | Profile June 8th, 2010 - 9:28 amNevermind, I google it, nice, especially this:

In a Cartesian coordinate system, gcd(a, b) can be interpreted as the number of points with integral coordinates on the straight line joining the points (0, 0) and (a, b), excluding (0, 0).

Far beyond of what I knew, cool!!

Jimmy Anders| PUZZLE MASTER | Profile June 8th, 2010 - 11:14 pmI’m having a problem visualizing this problem so that the formula:

#cubes = L + W + H – gcd(L,W) – gcd(L,H) – gcd(W,H) + gcd(L,W,H)

makes sense directly. I get the same thing, but for me it takes a lot of work to show. My argument was, as the line goes, if it never passes through any edges, then it follows some path using only moves between adjacent cubes, i.e, moves in one dimension at a time. This number is

L + W + H – 2.

But then if instead the line traveled through an edge, but no vertices, then it would make a move in 2 dimensions at once, which is like skipping one of the 1st kind of moves, except for the last time it happens, because the line ends and makes no further moves. So the number of cubes you have to deduct if the the line crosses through an edge in the direction of the H dimension would be gcd(L,W) – 1. Making our total:

L + W + H – 2 – [gcd(L,W) – 1 + gcd(L,H) – 1 + gcd(H,W) – 1]

= L + W + H – gcd(L,W) – gcd(L,H) – gcd(H,W) + 1.

Then, if the line does pass through a vertex, then it makes a move in all 3 directions at once, which is like skipping 2 of the regular moves, which it does for every vertex but the last. So we need to discount 2*[gcd(L,W,H) – 1]. But last time when we counted what we thought were only egdes there were really vertices in there, so we already subtracted out 3*[gcd(L,W,H) – 1] and to get our correct answere we need to add back in a gcd(L,W,H) – 1, just so that we’re subtracting only 2. This gives

L + W + H – gcd(L,W) – gcd(L,H) – gcd(H,W) + 1 + gcd(L,W,H) – 1

= L + W + H – gcd(L,W) – gcd(L,H) – gcd(H,W) + gcd(L,W,H).

Granted, you could divide everything by gcd(L,W,H), stop at step 2, and then multiply the result back by gcd(L,W,H), but apart from that, did you guys follow a simpler reasoning to arrive at your formulas?

Bobo The Bear| PUZZLE MASTER | Profile June 11th, 2010 - 9:14 amHere’s how the inclusion/exclusion formula “evolved” for me:

You can count the number of unit cubes by counting the number of planes the diagonal passes through. (The phrase “passes through” is a bit inexact when it comes to the endpoints of the diagonal, though. For counting purposes, it helps to say that the diagonal doesn’t pass through the first endpoint, and does pass through the final endpoint.)

The diagonal will pass through a total of L planes along its length (which I will call “length planes), W planes along the width (“width planes”), and H planes along its height (“height planes”). So the counting formula includes the values L, W, and H:

#cubes = L + W + H

By doing this, some cubes get counted twice, when the diagonal passes through an edge (an intersection of two planes). For example, when the diagonal passes through a length plane and a width plane at the same time, it gets counted twice, but only accounts for one new unit cube. To make up for this, we exclude the unit cubes that get double-counted.

For the length and width, we would exclude a total of gcd(L,W) cubes, the greatest common divisor of L and W. (It was much easier to visualize this by working in just two dimensions. My example was the diagonal of a 15×10 rectangle, which crossed through an edge 15+10 times, but crossed through a corner 5 times). For length and height, we exclude gcd(L,H), and for width and height, we exclude gcd(W,H). The counting formula is now:

#cubes = L + W + H – gcd(L,W) – gcd(L,H) – gcd(W,H)

When the diagonal passes through a vertex (an intersection of three planes), it accounts for one unit cube. So far, we’ve included this cube 3 times (one for each of L, W, and H) and excluded it 3 timed (once for each of the gcd functions), so we need to include it in the count again. The diagonal will do this a total of gcd(L,W,H) times, so we end up with our final count:

#cubes = L + W + H – gcd(L,W) – gcd(L,H) – gcd(W,H) + gcd(L,W,H)

@Jimmy Anders: I’m not sure if this is all that much simpler than what you reasoned, it sure looks like you understand the idea in much the same way I did, except for considering the edge/corner cubes (your “-2” and “-1″ factors” earlier on, rather than excluding them later.

Bobo The Bear| PUZZLE MASTER | Profile June 11th, 2010 - 9:19 amSorry about the inadvertent “auto-smiley” there.

Yehuda Groden| Profile September 15th, 2010 - 4:19 pm#cubes = 375 + 324 + 150 – 0 – 72 – 3 – 6 = 768 cubes

deepside0058| Profile March 12th, 2011 - 7:01 ambukas na lang ako sasagot!!