1996 AIME Problem 14

Attempt Problem 14 of the 1996 AIME below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 1996 AIME solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

14.

A 150×324×375150\times324\times375 rectangular solid is made by gluing together 1×1×11\times1\times1 cubes. An internal diagonal of this solid passes through the interiors of how many of the 1×1×11\times1\times1 cubes?

Answer: 768
Concepts:rectangular prisminclusion-exclusiongreatest common divisor
Difficulty rating: 2270
Small Hint:

Count the coordinate-plane crossings of the space diagonal

Big Hint:

Correct for crossings of two or three grid planes at once using greatest common divisors

Solution:

For an a×b×ca\times b\times c array, the diagonal crosses a1,a-1, b1,b-1, and c1c-1 internal grid planes of the three orientations. Crossings of two orientations coincide gcd(a,b)1,\gcd(a,b)-1, gcd(a,c)1,\gcd(a,c)-1, and gcd(b,c)1\gcd(b,c)-1 times, and triple crossings occur gcd(a,b,c)1\gcd(a,b,c)-1 times. Adding one for the initial cube and applying inclusion-exclusion gives a+b+cgcd(a,b)gcd(a,c)gcd(b,c)+gcd(a,b,c).\begin{gathered}a+b+c-\gcd(a,b)\\-\gcd(a,c)-\gcd(b,c)\\+\gcd(a,b,c).\end{gathered} Here the pairwise gcds are 6,6, 75,75, and 3,3, and the triple gcd is 3.3. Thus the number of cube interiors met is 150+324+3756753+3=768.\begin{gathered}150+324+375\\-6-75-3+3=768.\end{gathered}

← Problem 13#13
Full Exam

Problem 14 in Other Years