School-Safe Puzzle Games

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

### 20 Comments to “Crossing the Parallelepiped”

1. Bobo The Bear | PUZZLE MASTER | Profile

After 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!

2. Falwan | Profile

sqrt(324*324+375*375+150*150)/sqrt3 = 89367 cubes

3. Falwan | Profile

Large diagonal passing thru:

89387 – 2 = 89385 cubes

4. Shawn | PUZZLE GRANDMASTER | Profile

I’m getting 786, should be close but this is a tough one, might not be exact.

5. Jimmy Anders | PUZZLE MASTER | Profile

I get 768.

6. Hex | PUZZLE MASTER | Profile

The 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

7. APEX.JP | Profile

Not 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

8. Hex | PUZZLE MASTER | Profile

It 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.

9. deepside0058 | Profile

I’m pretty sure it’s 375. :-B

10. bilbao | Profile

The 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

11. Hex | PUZZLE MASTER | Profile

I 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 >:>

12. Hex | PUZZLE MASTER | Profile

I 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

13. suineg | PUZZLE MASTER | Profile

This 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

14. suineg | PUZZLE MASTER | Profile

Nevermind, 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!!

15. Jimmy Anders | PUZZLE MASTER | Profile

I’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?

16. Bobo The Bear | PUZZLE MASTER | Profile

Here’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.

17. Bobo The Bear | PUZZLE MASTER | Profile