sycraN_N

Bunic - Tata - Fiu

eddierwalker

Ecuatia ax + by + cz =  n aare o infinitate de solutii. Pentru  x  + 2y + 4z =  100 , considerand ca x,y,z € |N şi nu |N* , gasim 351 de solutii.

wmutex

Hmm... pentru problema cealalta, cu numarul de solutii naturale al ecuatiei diofantice  ax + by + cz =  n cand a, b, si c sunt primi intre ei e mai greu. Ma duc sa visez solutia, ca de gandit nu-mi iese. :D

donvalee

Spune cineva ca sunt 4 persoane ??? Unul poate sa fie si tata pt fisu' si fiu pt tasu' :))

wmutex

Trebuie gasit numarul N(a,b,c,n) de solutii naturale ale ecuatiei in x, y, z:

ax + by + cz = n

unde a, b, c sunt prime intre ele. O sa merg pe aceeasi idee ca si la problema anterioara:


1. Valoarea maxima a lui z nu poate depasi n/c (pentru x, y zero), si valoarea minima este 0:

z=0..[n/c]

unde [p] este partea intreaga a lui p.


2. Pentru fiecare valoare posibila fixata a lui z ecuatia se rescrie:

ax + by = n - cz

iar valorile posibile ale lui y se situeaza intre zero si valoarea maxima (atunci cand x este minim):

y=0..[(n - cz)/b]


3. Pentru valori fixate ale lui z si y ecuatia se scrie simplu:

ax = n - by - cz

si are solutie naturala doar daca a divide membrul drept:

   exista x <=> a | n - by - cz


4. Definind functia:

   f(a, b, c, n, y, z) = 1  daca a | n - cz - by;
   f(a, b, c, n, y, z) = 0  altfel.

atunci numarul de solutii naturale ale ecuatiei este:

N(a,b,c,n) =  suma[z=0..[n/c]] (  suma[y=0..[(n - cz)/b]]  (  f(a, b, c, n, y, z)  )  )

Functia f(a, b, c, n, y, z) nu-i chiar usor de calculat (cel putin asa mi se pare mie) in afara de cazul in care a = 1 (si atunci functia este 1 peste toate valorile), cum a fost in cealalta problema. Daca vrea cineva sa ridice manusa si sa caute o forma inchisa pentru f(a, b, c, n, y, z), sau o evaluare a sumei...

lucipet

Da, sunt  3 -  bunic,tata si fiu.

Titlul problemei m-a dus   la  urmatoarea definitie :

BARBAŢI CARE ... COBOARA LA BUŞTENI . (Solutia cu  8 litere)

knowing

Stiind ca a1a2a3=145
iar          a1+a2+a3=27

aflati a5008

wmutex

(continuare la evaluarea lui N(a, b, c, n))

E clar ca:

f(a, b, c, n, y, z) ≤ 1

deci:

N(a, b, c, n) ≤  suma[z=0..[n/c]] (  suma[y=0..[(n - cz)/b]  (  1  )  ) =
                       = suma[z=0..[n/c]] (  [(n - cz)/b] + 1  ) ≤
                       ≤ suma[z=0..[n/c]] (  (n - cz)/b + 1  ) =
                       = suma[z=0..[n/c]] (  n/b + 1  )  -  (c/b)suma[z=0..[n/c]] (  z  ) =
                       = (n/b + 1)([n/c] + 1)  -  (c/b)([n/c])([n/c] + 1)/2

Deci, in final, se obtine o limita superioara pentru numarul de solutii naturale:

N(a, b, c, n) ≤ (n/b - (c/b)[n/c]/2 + 1)([n/c] + 1)

care este mai precisa decat evaluarea initiala:

N(a, b, c, n) ≤ (n+1)³/(abc)


Obs. (n+1)³/(abc) este de fapt numarul de solutii naturale ale inecuatiei:

ax + by + cz ≤ n

ale carei solutii cuprind, se intelege, si solutiile ecuatiei asociate.