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

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

Count the coordinate-plane crossings of the space diagonal

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

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}