Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory senior

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
Consider a point travelling across the internal diagonal, and let the internal diagonal have a length of . The point enters a new unit cube in the dimensions at multiples of respectively. We proceed by using PIE. The point enters a new cube in the dimension times, in the dimension times and in the dimension, times. The point enters a new cube in the and dimensions whenever a multiple of equals a multiple of . This occurs times. Similarly, a point enters a new cube in the dimensions times and a point enters a new cube in the dimensions times. The point enters a new cube in the and dimensions whenever some multiples of are equal. This occurs times. The total number of unit cubes entered is then
Final answer
768