Parmalat

1. 1000monede de cate 1 ban si gata; Restul e CAN-CAN

catanedelcu

brutal attack  :)

mie mi-au iesit 70529 de moduri plus bancnota intreaga de 10 lei.  Daca vrea cineva si codul...desi nu cred, fiindca e banal.

sper ca e corect.  As fi curios daca are cineva vreo abordare "pe hartie"... :D

wmutex

Ok, poate ar trebui sa explic solutia, pentru ca mie mi se pare foarte frumoasa. Ideea de mai jos apartine de fapt lui Euler, si sta la baza asa-numitelor polinoame generatoare de partitii.

Sa presupunem ca nu avem decat o singura moneda: 1 ban. Sumele posibil de construit cu 1 ban, si numarul de moduri in care pot fi construite, sunt exponentii si coeficientii urmatorului polinim in u:

P1(u) = 1 + u + u^2 + u^3  + u^4...

De exemplu, suma de 4 bani poate fi constituita intr-un sigur mod din monede de 1 ban, si asta poate fi vazut uitandu-ne la coeficientul lui u^4 (care e 1).


Daca n-am avea decat monede de 10 bani, atunci sumele posibil de construit cu ele, si numarul de moduri in care pot fi construite sumele, sunt exponentii si coeficientii polinomului infinit in u:

P10(u) = 1 + u^10 + u^20 + u^30  + u^40...

De exemplu, suma de 4 bani nu poate fi construita in nici un fel din monede de 10 bani, fiindca coeficientul lui u^4 este 0 in P10(u). Dar suma de 20 de bani poate fi construita in mod unic, coeficientul lui u^20 in polinomul de mai sus fiind 1.
(continua mai jos)

wmutex

(continuare)
Pana aici toate par complicatii inutile: pentru ce trebuie bagate polinoame infinite,  u-uri si alte balarii pt. a spune chestii atat de simple? Fiindca, in cazul mai complicat cand avem atat monede de 1 ban cat si monede de 10 bani, sumele posibil de construit, cat si numarul de moduri in care pot fi construite, sunt date de coeficientii polinomului-produs, relativ usor de calculat:

P1(u)P10(u) =  [1 + u + u^2 + u^3  + u^4...] x [1 + u^10 + u^20 + u^30  + u^40...]

De exemplu, suma de 24 de bani poate fi construita in 3 moduri, fiindca coeficientul lui u^24 in polinomul de mai sus este 3:

3u^24 = u^24 + (u^14)(u^10) + (u^4)(u^20)

iar dezvoltarea respectiva explica si cum se obtine suma:
- 24 de monede de 1 ban, sau
- 14 monede de 1 ban si o moneda de 10 bani, sau
- 4 monede de 1 ban si 2 monede de 10 de bani.

Si, astfel, problema relativ complicata a gasirii posibilitatilor de partajare a unei sume in "bucati" standard mai mici se reduce la problema relativ simpla de-a inmulti 2 polinoame si-a calcula coeficientul de un anume ordin.
(continua mai jos)

wmutex

(continuare)
Generalizand, sumele de bani posibil de construit, si numarul posibilitatilor, cand utilizam unitati monetare de 1 ban, 10 bani, 50 de bani, 1 leu=100 bani, 5 lei=500 bani, sunt date de exponentii si coeficientii polinomului-produs:

P1(u)P10(u)P50(u)P100(u)P500(u) =
   = [1 + u + u^2 + u^3  + u^4...] x
      [1 + u^10 + u^20 + u^30  + u^40...] x
      [1 + u^50 + u^100 + u^150  + u^200...] x
      [1 + u^100 + u^200 + u^300  + u^400...] x
      [1 + u^500 + u^1000 + u^1500  + u^2000...].

Deci, pentru a calcula numarul de moduri in care poate fi construita suma de 10 lei=1000 de bani, trebuie calculat coeficientul lui u^1000 din produsul de mai sus.
(continua mai jos)

wmutex

(continuare)
Calculul coeficientului pomenit mai sus poate fi dus la capat, cu atentie, de orice elev care stie ceva despre polinoame si are rabdare (clasa a 6-a? a 7-a? nu mai tin minte). Dar cu instrumente analitice calculul poate fi mult simplificat. Seriile de puteri, inventate tot de Euler, permit exprimarea concisa, print-o functie nepolinomiala, a polinoamelor de grad infinit. Dezvoltarea Taylor in jurul unui punct e o astfel de serie de puteri.

Se poate vedea "cu ochiul liber" (si cu definitia dezvoltarii seriei Taylor in fata) ca:

P1(u) = 1 + u + u^2 + u^3  + u^4...

este dezvoltarea Taylor a functiei

P1(u) = 1/(1-u)

in jurul lui u=0.


La fel:

P10(u) = 1/(1-u^10)
P50(u) = 1/(1-u^50)
P100(u) = 1/(1-u^100)
P500(u) = 1/(1-u^500)

deci numarul de moduri in care poate fi schimbata bancnota de 10 lei = 1000 bani este coeficientul de ordin 1000 al dezvoltarii Taylor in jurul u=0 a functiei-produs:

P1(u)P10(u)P50(u)P100(u)P500(u) =
   = 1/[(1-u)(1-u^10)(1-u^50)(1-u^100)(1-u^5000)]

Cu binecunoscutul de-acum Wolfram|Alpha se gaseste coeficientul respectiv ca fiind 4908 (imi cer scuze cu ocazia asta pentru valoarea gresit calculata pe care am postat-o in solutie).

catanedelcu

Moneda de 5 bani ai uitat-o ...

wmutex

Desigur, valoarea coeficientului propusa de mine ar fi corecta daca n-ar exista si moneda de 5 bani. :)) Cu multumiri lui catanedelcu pentru atentionare: http://bit.ly/uuqSov

eddierwalker

Am invatat lucruri noi astazi! :)