0
$\begingroup$

Problem:A $150\times 324\times 375$ rectangular solid is made by gluing together $1\times 1\times 1$ cubes. An internal diagonal of this solid passes through the interiors of how many of the $1\times 1\times 1$ cubes?

I tried it and I had no clue of approaching. Then I saw solution on AOPS but didn't find it satisfactory. The solution went like this

$150+324+375- gcd(150,324)-gcd(150,375)-gcd(324,375)+gcd(150,324,375)= 768$.

Link is artofproblemsolving.com/community/c4h46950p315374

I think they have used PIE but I don't know how it solved the problem. Anybody can explain me??

$\endgroup$
4
  • 1
    $\begingroup$ Can you provide a link to the AOPS solution you saw? $\endgroup$
    – John Omielan
    Apr 19, 2020 at 7:02
  • $\begingroup$ @John Omielan artofproblemsolving.com/community/c4h46950p315374 $\endgroup$
    – Mathematical Curiosity
    Apr 19, 2020 at 7:24
  • 1
    $\begingroup$ Thanks. Please add that to your question text. $\endgroup$
    – John Omielan
    Apr 19, 2020 at 7:24
  • 1
    $\begingroup$ @MathematicalCuriosity Have you seen the 2-D version of this problem? It has the same ideas (though is much easier to approach / visualize). $\endgroup$
    – Calvin Lin
    Apr 20, 2020 at 4:53

1 Answer 1

Reset to default
1
$\begingroup$

Consider this cuboid on a graph.

Now mark planes, for each dimension in the following way.

$$x=1,x=2,...,x=150$$ $$y=1,y=2,...,y=324$$ $$z=1,z=2,...,z=375$$

Now the internal diagonal passes through all such planes.

Now it is equivalent to count intersections of the diagonal with the planes, which can be easily counted with the inclusion-exclusion principle.

For clarity: Now the part that why is it $\gcd(a,b)$: Consider starting from $(0,0,0)$. Imagine the internal diagonal as a vector. This vector has direction vector $(150,324,375)$. When you move in the direction of the positive $x$ axis, you also move $324/150$ units in the $y$ direction and similarly $375/150$ in the $z$ direction. When for example, $x$ and $y$ will be integers? Can you relate $\gcd(x,y)$ to this?

$\endgroup$
5
  • $\begingroup$ Why the no. of intersection with $x=k_1$ and $y=k_2$ is exactly $gcd(150,324)$?? $\endgroup$
    – Mathematical Curiosity
    Apr 19, 2020 at 11:30
  • 1
    $\begingroup$ There are intersectuons with only 1 integer coordinate, there are intersections with only 2 integer coorsinates and finally there are intersections with all 3 integer coordinates. $\endgroup$
    – h-squared
    Apr 19, 2020 at 14:45
  • 1
    $\begingroup$ You add $150+324+375$, thats intersections with points that have only $1$ of $x,y,z$ as integer. But then points which have $2$ of $x,y,z$ as integers are overcounted so you subtract those. Then you add again the case when all $3$ of $x,y,z$ are integers. $\endgroup$
    – h-squared
    Apr 19, 2020 at 14:48
  • 1
    $\begingroup$ Now the part that why is it $\gcd(a,b)$: Consider starting from $(0,0,0)$. Imagine the internal diagonal as a vector. This vector has direction vector $(150,324,375)$. When you move in the direction of the positive $x$ axis, you also move $324/150$ units in the $y$ direction and similarly $375/150$ in the $z$ direction. When for example, $x$ and $y$ will be integers? Can you relate $\gcd(x,y)$ to this? $\endgroup$
    – h-squared
    Apr 19, 2020 at 14:53
  • $\begingroup$ @h- squared Thanks $\endgroup$
    – Mathematical Curiosity
    Apr 20, 2020 at 12:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .