Cuántas $1\times 1\times 1$ cubos hace la diagonal interna pasar a través de un $150\times 400\times 660$ prisma rectangular?

Question

Problema:

Un $150\times 400\times 660$ prisma rectangular se corta en $39600000$ $1\times 1\times 1$ los cubos. Un interno de la diagonal del prisma pasa a través de cómo muchas de las $1\times 1\times 1$ cubos?

Insight:

En lugar de mirar a un $150\times 400\times 660$ prisma rectangular, miré a un

$$ \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$ avión, pero que me hizo nada bien. Cualquier ayuda es muy apreciada.

Answer 1

Considerar la línea de tener un principio y un final. Por cada cubo que pasa a través de, asociar ese cubo con la cara, arista o esquina donde la línea que sale del cubo (que está en la esquina en el último cubo).

• La línea tiene que pasar por $150$ planos paralelos a la $yz$-plano.
• La línea tiene que pasar por $400$ planos paralelos a la $xz$-plano.
• La línea tiene que pasar por $660$ planos paralelos a la $xy$-plano.

Si agregamos estos cruces juntos, ingenuamente, que sería el doble de contar un poco. A veces un cruce de la $yz$-plano coincide con un cruce de la $xz$-plano, y la línea se cruce en un $z$-paralelo borde. De manera similar en las otras dos direcciones. Y luego hay algún que otro rincón de cruces.

Pero esto es clásico de la inclusión-exclusión. $\gcd$ nos dirá donde la coincidencia cruces, y usted puede contar de esta manera:

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