Au trimis soluţii corecte Aurel Ionescu şi Zoltan Szabo.

Cea a lui Aurel Ionescu este elegantă, dar – datorită figurii ataşate - nu am putut să o reproduc  într-un fişier vizibil pe acest site.

De aceea rămâne de prezentat soluţia (şi generalizarea) lui Zoltan Szabo:

        Să considerăm că paralelipipedul dreptunghic de dimensiuni 150 x 324 x 375 este așezat într-un sistem cartezian OXYZ cu un vârf  în punctul de origine (0,0,0) și vârful diagonal opus în punctul de coordonate (150,324,375).

        Vom număra toate cuburile de latură 1 ce sunt străpunse de diagonală pornind din origine către vârful cel mai îndepărtat. Să considerăm șirul cuburilor în ordinea în care ele se intersectează cu diagonala. Ele vor avea tendința să se îndepărteze de punctul (0,0,0) și să se apropie de punctul (150,324,375). Fiecare cub va fi identificat cu coordonata celui mai îndepărtat vârf față de origine. Astfel primul cub are coordonata (1,1,1) , iar ultimul cub are coordonata  (150,324,375).

        Fie coordonatele a două cuburi de pe poziții succesive din acest șir (i1,j1,k1) respectiv (i2,j2,k2). Atunci întotdeauna valorile  i2 - i1 , j2 - j1 , k2 - k1  sunt în mulţimea {0,1}.

        Dacă toate cele trei diferențe sunt egale cu 1, atunci cele două cuburi au un colț comun și avem numerele (i1,j1,k1) direct proporționale cu numerele (150, 324, 375).

       Dacă doar două diferențe sunt egale cu 1, atunci cele două cuburi au o latură comună și avem proporționalitate directă la numai două coordonate (i1,j1) cu (150, 324) sau (i1,k1) cu (150,375) sau (j1,k1) cu (324,375), iar raportul al treilea este mai mare.

       Dacă doar o singură diferență este egală cu 1, atunci cele două cuburi au o față comună iar raportul cel mai mic este unic și are valoarea min(i1/150, j1/324,  k1/375). 

       Cu ajutorul unui program C++ am calculat numărul cuburilor de latură 1 și am obținut numărul 768.

int main()
{
    long long i,j,k,m,n,p,nr,min1,min2;
    cin>>m>>n>>p;
    nr=0;
    i=0;j=0;k=0;
    while (i<m or j<n or k<p)
    {
        min1=i;
        min2=m;
        if(min1*n>min2*j)
            min1=j,min2=n;
        if(min1*p>min2*k)
            min1=k,min2=p;
        if(min1*m==min2*i) i++;
        if(min1*n==min2*j) j++;
        if(min1*p==min2*k) k++;
        nr++;
    }
    cout<<nr<<"\n";
    return 0;
}

 

Generalizare:

Pentru cazul general M*N*P observăm că la fiecare pas avansăm cu o poziție pe cel puțin o axă Ox, Oy sau Oz. În conformitate cu metoda interclasării, algoritmul de numărare are limita superioară M+N+P. Această valoare suferă modificări în cazul în care două sau trei dintre dimensiunile paralelipipedului admit un cmmdc diferit de 1. Astfel la fiecare caz de proporționalitate am  numărat păatrate în plus, deci trebuie să scădem acele cazuri care admit cmmdc diferit de1. 

Folosindu-ne de principiul includerii și excluderii obținem formula:

        M+N+P - cmmdc(M,N) - cmmdc(M,P) - cmmdc(N,P) + cmmdc(M,N,P)

(Notă: găsită şi de Aurel Ionescu)

Aplicăm pe cazul nostru particular și obținem: cmmdc(150,324)=6, cmmdc(75), cmmdc(324,375)=3, cmmdc(150,324,375)=3.

       Soluția finală va fi: 150 + 324 + 375 - 6 - 75 - 3 + 3 = 768

 

Am mai primit răspunsuri de la Lucian Niţă, cu 375 cuburi, şi Cristian Bălănoiu cu 847 cuburi.