Aflati cate numere naturale de 5 cifre nu neaparat distincte au suma cifrelor cel mult 10.
Problema este pentru clasa a patra )

Eu stiu ca am vazut intr-o carte de combinatorica o formula ptr nr de solutii in numere naturale ptr o ecuatie de forma
a_1+a_2+...+a_k=n, parca era ceva de genul
Combinari de n-1 cate k-1.
Dar aceasta problema trebuie explicata la clasa a patra, deci nu pot folosi asa ceva.

[Citat] Aflati cate numere naturale de 5 cifre nu neaparat distincte au suma cifrelor cel mult 10. Problema este pentru clasa a patra ) Eu stiu ca am vazut intr-o carte de combinatorica o formula ptr nr de solutii in numere naturale ptr o ecuatie de forma a_1+a_2+...+a_k=n, parca era ceva de genul Combinari de n-1 cate k-1. Dar aceasta problema trebuie explicata la clasa a patra, deci nu pot folosi asa ceva.

Numărul de soluții în numere naturale ale ecuației x_1+x_2+...+x_n=k este C_{n+k-1}^{k-1}. Ce ați scris dv. e numărul de soluții în numere naturale nenule.

Oricum, formula trebuie adaptată, pentru că prima cifră a numărului nu poate fi 0, și, pe de altă parte, nu există cifra "10" (în timp ce ecuația x_1+x_2+...+x_5=10 admite și soluții gen 10+0+0+0+0).

Îmi vine greu să cred că se poate face așa ceva la clasa a 4-a... Nici la a 10-a nu e simplu.

Oricum, răspunsul este 2001.

Cel mai simplu mod de rezolvare la nivel de clasa a patra este sa ii invatam pe copii sage si sa tiparim "programul de o linie" (one-liner):


sage: len( [ n for n in [10000..99999] if sum(n.digits()) <= 10 ] )
2001


Pentru a vedea care este dificultatea problemei,
dificultate care nici macar nu poate fi intrezarita la nivel de clasa a patra,
iata solutiile numarate dupa cum apar cifrele in ele:

Cum poate un copil de clasa a patra să facă ordine în posibilităţile de mai sus?

Faptul că un număr de cinci cifre nu poate să înceapă cu $0$ (sau $00$ sau\dots)
fiind o şicană în plus din partea celui ce propune problema.
(El putea sa spuna ca luam doar numerele cu cifre diferite, dar problema lui era ca nu mai nimeream revelionul anului 2001.)
(În acest mod, problema nu mai este una ``homogenă din punctul de vedere al combinatoricii''.)

Fiecare linie este o problemă de clasa a patra.

Am incercat sa vad daca problema poate fi cumva sau altcumva atacabila la nivel de clasa a patra, dar trebuie sa regret.

(Singurul caz in care as putea accepta ca aceasta problema sa fie de clasa a patra este ca test de trecerea clasei a patra pentru inspectorii judeteni de invatamant. Atunci aflam imediat verdictul adevarat din partea lor. Un alt test ar fi ca cel ce a propus problema sa faca "cealalta" problema de clasa a patra: Câte numere de cinci cifre scrise in baza zece au produsul cifrelor mai mic sau egal cu zecz. Este o problema mai usoara, anume incomparabil de mai usoara, dar sa ii dam hartie si creion si sa o rezolve in fata noastra in conditii de olimpiada de clasa a patra! Desigur ca - tinand cont si de depunctarile eventuale din cauza lezarilor de gramatica - are sanse bune sa faca rost de un scor negativ.)

Iata mai intai cod care ne imparte solutiile in tipuri:

COD SAGE

Şi obţinem:

Elevul de clasa a patra trebuie doar sa identifice tipurile de mai sus.

Eu trebuie sa explic desigur (facând si eu greseli de exprimare - 20% din vina mea si 80% din vina "simplitatii" problemei de clasa a patra) ce este tipul unei solutii.

Incerc plecând de la un exemplu.
Am ales exemplul...

Tipul (1, (2, 2))
... Cele 4 chei ale tipului sunt:
...... (0, 1, 1, 2, 2) --> 24 realizari

si asa mai departe.
Acel 1 din (1,(2,2)) arata ca ne legam de numere n ce contin o singura data cifra 0.

Apoi vin cifrele nenule.
Acestea au "subtipul" (2,2) - pe româna: mai sunt si cifre nenule in numar, una apare de doua ori, cealalta tot de doua ori.
(Nu stiu cum sa fac propozitiile ca sa nu induc in eroare (combinatorica)...)

Pe si mai româna ne intrebam acum:
Ce numere de cinci cifre (numere de numere, nu numere de telefon) putem forma folosind cifrele 0, 1, 1, 2, 2 ?

(Daca stim raspunsul pentru aceasta "realizare" a tipului, atunci il stim si pentru celelalte, care sunt:

(0, 1, 1, 2, 2) --> 24 realizari
(0, 1, 1, 3, 3) --> 24 realizari
(0, 1, 1, 4, 4) --> 24 realizari
(0, 2, 2, 3, 3) --> 24 realizari

si atât.)
Din cele de mai sus stim ca trebuie sa dam de 24.
Putem rationa asa:

Pentru 0 avem exact 4 pozitii.
Indiferent de alegerea pozitiei lui 0, mai raman patru pozitii.
Exista "combinari de patru luate câte doua" modalitati de a plasa 1,1 pe ele.
Raman doua pozitii, pe ele plasam obligatoriu 2,2.
Asa am dat de aceste 24 de realizari.

"Tipului" ( 1, (2,2) ) ii corespun astfel
-> patru realizari cu cifre, anume 01122, 01133, 01144, 02233, pentru care trebuie sa mai gasim ordinea buna,
-> si pentru fiecare 0aabb de mai sus avem 24 de realizari valide.

Pe scurt, pentru "tipul" ( 1, (2,2) ) avem 4 x 24 solutii.

Nu sunt prea multe tipuri.
Calculatorul le-a scris "cu mana sigura" mai sus.

Mai ramâne sa facem operatia...

Si iata in sfarsit problema de clasa a patra...

Ar trebui să întrebăm, mai întâi, care e sursa problemei. Poate că enunțul original cerea numărul de numere cu 2 cifre și propunătorul pe site s-a gândit să fie creativ...

Nu, n-am modificat eu problema, asa am primit-o de la altcineva, care spyne ca a primit-o de la un elev. Eram si eu de parere ca nu se poate face la a-4-a, fiind prea multe cazuri, dar am zis ca poate-mi scapa mie ceva. In ultimul timp se exagereaza cu dificultatea problemelor in concursuri la clasele mici. Dar la a zecea cred ca ar putea fi data. E vorba de nr solutii in nr naturale ale unei ecuatii, in primul post intr-adevar formula era ptr solutii nenule si tehnica e cunoscuta sub numele ,,stars and bars combinatorics". Pentru nenule mi se pare ca se aduna 1 la fiecare necunoscuta, etc si se reduce la tipul precedent.

[Citat] Nu, n-am modificat eu problema, asa am primit-o de la altcineva, care spyne ca a primit-o de la un elev. Eram si eu de parere ca nu se poate face la a-4-a, fiind prea multe cazuri, dar am zis ca poate-mi scapa mie ceva. In ultimul timp se exagereaza cu dificultatea problemelor in concursuri la clasele mici. Dar la a zecea cred ca ar putea fi data. E vorba de nr solutii in nr naturale ale unei ecuatii, in primul post intr-adevar formula era ptr solutii nenule si tehnica e cunoscuta sub numele ,,stars and bars combinatorics". Pentru nenule mi se pare ca se aduna 1 la fiecare necunoscuta, etc si se reduce la tipul precedent.

Numele "stars and bars" nu ne ajuta prea mult,
ne ajuta insa foarte repede idea de trecere de la

( a1, a2, ... , ak )
(cu componentele nenule)

la

a1 < a1+a2 < ... < a1+a2+...+ak = n

si apoi la submultimea lui { 1,2,...,(n-1) } cu componentele (in numar de (k-1))

a1 si a1+a2 si ... (pana la penultima)

si astfel avem o bijectie intre multimi... trebuie doar sa scriem care multimi.
La noi avem de vazut cand o suma de cateva cifre este mai mica sau egala cu zece.

Solutia de clasa a zecea "este simpla", ar merge cam asa: