Va propun sa ne mai distram, dar intr-un fel in care sa punem si mintea sa lucreze.
Plecam de la premisa ca exista monede de cate 1, 5, 10, 25 si 50 de bani. Si vrem sa vedem in cate moduri poate fi platita o anumita suma de bani. Un mod de a plati este determinat daca stim cate monede de fiecare fel sunt folosite. De exemplu: Suma de 4 bani poate fi platita intr-un singur mod - cu patru monede de cate 1 ban. Suma de 5 bani poate fi platita in doua moduri - cu o moneda de 5 bani sau cu cinci de cate 1 ban. Suma de 10 bani, in patru moduri - cu o moneda de 10; cu doua de 5; cu una de 5 si cinci de 1; cu zece de 1. Suma de 15 bani, in sase moduri. Suma de 20, in noua moduri. Suma de 25, in 13 moduri...
Acestea fiind zise, puteti spune in cate moduri poate fi platita suma de 1 leu?

2 monede de 50 de bani, 4 de 15, 10 de 10, 20 de 5, 100de 1.Cred.

4 de 25 scuze, dar cred ca se poate face si din una de 5 + 4+1 et, deci cred ca sunt solutii infinite.

"deci cred ca sunt solutii infinite" - Chiar infinite?

Nu sunt posibilităţi infinite, fiindcă exerciţiul de logică impune un număr limitat: 1 leu. Nu impune un infinit. Este doar o mulţime ce are ca elemente multe posibilităţi.

Atunci daca nu-s infinite, cate posibilitati sunt?

Un anume număr limitat de posibilităţi. Dar nu ţine de infinit.

Daca acest anume numar nu se poate defini se mai poate chema "indefinit" "infinit" chiar daca nu e imposibil de stabilit.

Mie imi pare ca numarul se poate defini. Adica calculezi acele posibilitati. Evident, dureaza foarte mult calculul lor.

Exact.

In cazuri particulare simple, cum sunt cele mentionate de mine (sume: 1, 5, 10, 15, 20, 25) se pot afla raspunsuri prin incercari. Se poate insa gasi o metoda prin care sa aflam raspunsul si in cazul sumelor mai mari.

O regula generala este destul de greu.
Insa niste reguli tot se pot observa.
De exemplu ce am gasit eu (nu stiu cat de corect):

1.) Pentru fiecare numar exista cel putin o modalitate "m" de a fi scris, cea care implica numarul 1.

2.) Pentru un numar X, exista x/5 moduri 'm' in care poate fi scris cu numere ce implica valoarea 5. (Cu conditia ca numarul sa se imparta exact.)
Ex: Pentru 5. m=5/5=1.
Intr-adevar singurul mod in care 5 poate fi scris, folosind cel putin o valoare de 5, este 1.
Pentru 10.
m=10/5=2
Intr-adevar,exista doar doua moduri ce implica valoarea 5:
a.) 10=5+5
b.) 10+5+1+1+1+1+1

Pentru 15.
m=15/5=3

a.) 25=5+5+5
b.) 25=5+5+1+1+1+1+1
c.) 25=5+1+1+1+...+1


3.) Pentru un numar X, exista (3* X/10)-2 moduri "m" in care poate fi scris, cu conditia sa se imparta exact la 10.

Exemplu:
Pentru 10.

m=3*10/10-2=3-2=1

Pentru 20.

m=3*20/10-2=6-2=4

1. 20=10+10
2. 20=10+5+5
3. 20=10+5+1+...1
4. 20=10+1+1+...+1

Analog, am gasit pentru 25:
m=8*X/25-7

Mi se pare un inceput bun. Keep going. Trebuie sa aflam in cate moduri se poate plati leul.

Vreo idee ceva?
Trebuie creata o mica teorie. Plecam de la probleme analoge. In cate feluri se poate plati o suma "n" folosind doar monede de 1 ban; in cate feluri se poate plati aceeasi suma "n" folosind doar monede de 1 si de 5; dar folosind 1, 5 si 10; dar 1, 5, 10 si 25; si in final toate cele cinci feluri de monede. Niste notatii: An - nr. de moduri de plata folosind doar monede de 1 ban; Bn - doar monede de 1 si 5 bani; Cn - monede de 1, 5 si 10 bani; Dn - 1, 5, 10 si 25; En - 1, 5, 10, 25 si 50.
Daca nu am folosi monede de 50, prin definitie numarul modurilor de plata este Dn. Acum, dupa ce prima moneda de 50 a fost pusa pe masa, mai raman de platit (n - 50) bani, ceea ce se poate face exact in E(n-50) moduri. Avem deja niste formule: En = Dn + E(n-50); Dn = Cn + D(n-25); Cn = Bn + C(n-10) si Bn = An + B(n-1). Se observa ca formulele raman valabile daca punem A0 = B0 = C0 = D0 = Eu = 1. Raman valabile si daca consideram fiecare din cantitatile An, Bn,..., En ca fiind egala cu 0, cand indicele ei este negativ (de exemplu E25 = D25, si asta concorda cu prima formula, pentru ca E(25-50) = E(-25) = 0.
Formulele astea permit sa calculam recursiv, prin recurenta, cantitatile considerate, adica mergand inapoi spre valori mai mici ale lui n sau spre litere anterioare ale alfabetului.

Bn-- nr de moduri in care "n" poate fi platit doar cu monede de 1 si 5 bani.
An --nr de moduri in care "n" poate fi platit doar cu monede de un ban.

Intre cele doua exista relatia:
Bn=An+B(n-1)

Pai sa spunem ca n=23.

Bn ar fi 5. Ca exista doar cinci moduri in care suma de 23 poate fi platita cu monede de 1 si 5 bani. Iata care sunt:

I) 1+1+1+...+1=23
II) 5+5+5+5+1+1+1=23
III) 5+5+5+1+1+...+1=23
IV) 5+5+1+1+...+1+1=23
V) 5+1+1+1+...+1+1=23

Deci Bn=5.


An ar fi egal cu 1, ca exista doar o singura modalitate in care suma de 23 poate fi platita cu monede de 1.
Iata:

I) 1+1+1+...+1=23

Deci An=1


Iar B(n-1) ar fi 5, caci exista cincimoduri in care sum de 22 poate fi platita cu monede de 1 si 5. Iata care sunt:

I) 1+1+1+...+1=22
II) 5+5+5+5+1+1=22
III) 5+5+5+1+1+...+1=22
IV) 5+5+1+1+...+1=22
V) 5+1+1+1+...+1=22

Deci B(n-1)=5


Sa recapitulam.
Stim ca Bn=5
An=1
B(n-1)=5

Numai ca astea nu verifica formula ta Bn=An+B(n-1)
5=6.



Unde am gresit?

Oricum,cred ca
An=1, ∀ n∈ℕ
si probabil ca
Bn=[n/5]+1, ∀ n∈ℕ, unde [x] reprezinta partea intreaga a lui x.

Am gasit 282 moduri. Sper sa nu fi gresit la vreun calcul.
Am calculat mai intai sumele An, Bn,..., En pentru primele n = 50, din 5 in 5. Si am facut un tabel. Pe orizontala sumele An, Bn,..., En si pe verticala "n" din 5 in 5. Tabelul arata cam asa:
An Bn Cn Dn En
0 1 1 1 1 1
5 1 2 2 2 2
10 1 3 4 4 4
15 1 4 6 6 6
20 1 5 9 9 9
25 1 6 12 13 13
30 1 7 16 18 18
35 1 8 20 24 24
40 1 9 25 31 31
45 1 10 30 39 39
50 1 11 36 49 50
Prima linie si prima coloana contin numai numere egale cu 1. Plecand de la numerele astea le calculam pe celelalte prin recurenta, prin simpla adunare: fiecare numar din tabel este egal fie cu numarul din stanga lui, fie cu suma a doua numere: cel din stanga lui si un altul situat la o distanta corespunzatoare, mai sus. De exemplu: C30 = B30 + C20 = 7 + 9 = 16.
Mergand in continuare pe modelul asta am dat de E100 = 282
In postarea anterioara am gresit formula lui Bn; trebuia Bn = An + B(n-5), nu + B(n-1).

Cu ce formule ai facut tabelul asta?
Le-ai calculat pur si simplu?

"Prima linie si prima coloana contin numai numere egale cu 1. Plecand de la numerele astea le calculam pe celelalte prin recurenta, prin simpla adunare..." - Plecand de la acel "1" de pe prima linie si prima coloana am aplicat formulele pe care le-am mentionat in postarea precedenta. Bn se vede usor ca urmeaza sirul numerelor naturale: 1; 2; 3;...; 11

Sabin,abordarea ta este cea mi buna pentru a rezolva problema cu1 leu. Insa pentru o 100 de lei, de exemplu, ne-ar trebui minute bune ca sa ajungem la rezultat.

Eu sunt ferm convins ca se poate gasi o formula generala, desi e mult mai complicat de gasit.

Am gasit ca An=1.
Daca stai sa gandesti logic posibilitatile noi introduse de numarul 5, constati ca sunt egale cu multiplii de 5 ai numarului n. Mai exact.
Bn=[n/5]+An=[n/5]+1


Daca introduci si numarul 10 in ecuatie se constata ca:
Un 10 introduce inca o varianta. Deci: 1
Doi de 10 introduc varianta de mai sus, plus inca trei ale celuilalt 10 (Ce poate fi scris ca 5+5, 5+(1+1.+1),sau (1+1+...+1)+(1+1+...+10) Deci 1+3
Pentru trei de 10, este introdusa varianta 1, plus inca cele 3 variante, plus inca 5 (atat iti da daca le iei in parte) Adica 1+3+5

Deci avem:
Un zece - 1
Doi de zece 1+3
Trei de zece 1+3+5

Asta e o progresie aritmetica cu ratia doi si primul termen 1. Generalizarea e valabila pentru toate numerele din lista ta, am verificat.
Am facut calcule si mi-a dat ca numarul 10 mai introduce inca [(n/10)^2] valori unde [x] e partea intreaga.
Adunate si cu celelalte ar fi ca:
Cn=Bn+[(n/10)^2]

Deci am ajuns cuformulele matematice pana la Cn(cu conditia sa fie corect ce am spus pana acum).Mai il am pe Dn si En.

Sunt curios daca ajungi la E100 = 282

Pentru 5 si 10 era mult mai usor, ca aveam suficienti multipli i de 5 si 10 pentru a imi da seama de regula respectiva. (progresie aritmetica cu ratia 1, respectiv cu ratia 2)
Pentru 25 nu am decat doua variante: pe 25 si pe 50.
Iar pentru 50 un singur termen.
Am presupus ca si pentru ei trebuie sa existe o progresie, si fara sa mai simplific am ajuns la asta:
http://i.imgur.com/U6uYVZu.png

Formulele par sa verifice. Am luat la intamplare cazul lui n = 50 si am gasit Dn = 36 + 13 = 49, ceea ce e adevarat. Iar En = 49 + 1 = 50; bun si asta.
Great! Ingenioasa analiza ta!

Sa vedem pentru n = 100.
A100 = 1
B100 = 1+ 100/5 = 1 + 20 = 21
C100 = 21 + [100/10]^2 = 121
D100 = 121 + 1/2[11*4 - 9]*4 = 121 + 70 = 191
E100 = 191 + 1/2[2 + 178 - 89]*2 = 191 + 91 = 282

Sabin, le-am dat la plesneala pe ultimele doua. Am presupus ca termenii sunt tot intr-o progresie aritmetica. Pentru primele 3 era evident acest lucru. Pentru ultimele doua e doar o premisa.

Formulele (ultimele)par sa verifice numai in cazul in care n se imparte exact cu 50. Daca n nu se imparte exact cu 50 ultima formula(En) introduce erori. Iar daca n nu se imparte cu 25, atunci Dn introduce erori si ea.

Pentru n