Question

Un sólido rectangular de $150\times324\times375$ está formado al pegar cubos de $1\times1\times1.$ ¿Por el interior de cuántos cubos de $1\times1\times1$ pasa una diagonal interior de este sólido?

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

Respuesta

Respuesta: 768

Conceptos:prisma rectangular inclusión-exclusión máximo común divisor

Nivel de dificultad: 2270

Pista pequeña:

Cuenta los cruces de la diagonal espacial con los planos coordenados de la cuadrícula

Count the coordinate-plane crossings of the space diagonal

Pista grande:

Corrige los cruces simultáneos de dos o tres planos de la cuadrícula mediante máximos divisores comunes

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

Solución:

En un arreglo de $a\times b\times c,$ la diagonal cruza $a-1,$ $b-1,$ y $c-1$ planos internos de la cuadrícula de las tres orientaciones. Los cruces de dos orientaciones coinciden $\gcd(a,b)-1,$ $\gcd(a,c)-1,$ y $\gcd(b,c)-1$ veces, y los cruces triples ocurren $\gcd(a,b,c)-1$ veces. Al añadir uno por el cubo inicial y aplicar inclusión-exclusión se obtiene $\begin{gathered}a+b+c-\gcd(a,b)\\-\gcd(a,c)-\gcd(b,c)\\+\gcd(a,b,c).\end{gathered}$ Los máximos divisores comunes por pares son $6,$ $75,$ y $3,$ y el máximo divisor común triple es $3.$ Por lo tanto, el número de interiores de cubos atravesados es $\begin{gathered}150+324+375\\-6-75-3+3=768.\end{gathered}$

For an $a\times b\times c$ array, the diagonal crosses $a-1,$ $b-1,$ and $c-1$ internal grid planes of the three orientations. Crossings of two orientations coincide $\gcd(a,b)-1,$ $\gcd(a,c)-1,$ and $\gcd(b,c)-1$ times, and triple crossings occur $\gcd(a,b,c)-1$ times. Adding one for the initial cube and applying inclusion-exclusion gives $\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,$ $75,$ and $3,$ and the triple gcd is $3.$ Thus the number of cube interiors met is $\begin{gathered}150+324+375\\-6-75-3+3=768.\end{gathered}$

1996 AIME Problema 14

Respuesta: 768

Nivel de dificultad: 2270

Pista pequeña:

Pista grande:

Solución:

El Problema 14 en otros años