Problem:
A rectangular solid is made by gluing together cubes. An internal diagonal of this solid passes through the interiors of how many of the cubes?
Solution:
Let the rectangular solid have width , length , and height , where , and are positive integers. We will show that the diagonal passes through the interiors of
of the cubes.
Orient the solid in -space so that one vertex is at and another is at . Then is a diagonal of the solid. Let be a point on this diagonal. Exactly one of is an integer if and only if is interior to a face of one of the small cubes. Exactly two of are integers if and only if is interior to an edge of one of the small cubes. All three of are integers if and only if is a vertex of one of the small cubes. As moves along the diagonal from to , it leaves the interior of a small cube precisely when at least one of the coordinates of is a positive integer. Thus the number of interiors of small cubes through which the diagonal passes is equal to the number of points on the diagonal with at least one positive integer coordinate. Points with positive coordinates on the diagonal have the form
The first coordinate, , will be a positive integer for values of , namely for the values . The second coordinate will be an integer for values of , and the third coordinate will be an integer for values of . The sum doubly counts the points with two integer coordinates, however, and it triply counts the points with three integer coordinates. The first two coordinates will be positive integers precisely when has the form , for some positive integer between 1 and , inclusive. A similar argument shows that the second and third coordinates will be positive integers for values of , the third and first coordinates will be positive integers for values of , and all three will be positive integers for values of . By the inclusion-exclusion principle, will have one or more positive integer coordinates
times, which gives when .
The problems on this page are the property of the MAA's American Mathematics Competitions