4

Problem:

A $150\times 400\times 660$ rectangular prism is cut into $39600000$ $1\times 1\times 1$ cubes. An internal diagonal of the prism passes through how many of the $1\times 1\times 1$ cubes?

Insight:

Instead of looking at a $150\times 400\times 660$ rectangular prism, I looked at a

$$ \dfrac{150}{\gcd(150,400,660)} \times \dfrac{400}{\gcd(150,400,660)} \times \dfrac{660}{\gcd(150,400,660)} \implies 15\times 40\times 66$$ rectangular prism. However, these numbers were still too large to compute the problem manually. Are there any elegant solutions to this problem? I also tried putting the prism on the $xyz$ plane, but that got me nowhere as well. Any help is appreciated!

Albus Dumbledore
  • 409
  • See if you can find the pattern for some small rectangles—and if you have luck with that, see if you can then generalize your solution for small cubes. – Peter Kagey Dec 17 '16 at 07:11

1 Answers1

3

Consider the line to have a beginning and an end. For each cube it passes through, associate that cube with the face, edge, or corner where the line exits the cube (which is in the corner at the last cube).

  • The line has to pass $150$ planes parallel to the $yz$-plane.
  • The line has to pass $400$ planes parallel to the $xz$-plane.
  • The line has to pass $660$ planes parallel to the $xy$-plane.

If we just added these crossings together naively, we would be double counting a bit. Sometimes a crossing of the $yz$-plane coincides with a crossing of the $xz$-plane, and the line is crossing at a $z$-parallel edge. Similarly in the other two directions. And then there are occasional corner crossings.

But this is classic inclusion-exclusion. $\gcd$ will tell us where the coincidental crossings are, and you can count thusly:

$$150+400+660-\big(\gcd(150,400)+\gcd(150,660)+\gcd(400,660)\big)+\gcd(150,400,660)=1120$$

2'5 9'2
  • 54,717