i
i
“Petkovsek-naloga” — 2010/5/31 — 15:00 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 15 (1987/1988)
Številka 3
Strani 172–173
Marko Petkovšek:
NAGRADNA NALOGA
Ključne besede: naloga, razvedrilo.
Elektronska verzija: http://www.presek.si/15/884-Petkovsek.pdf
c© 1987 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
NAGRADNA NALOGA (v počastitev Ramanujanove stoletnice)
Zapis naravnega števila n v obliki vsote pozitivnih naravnih štev il imenujmo
razčlenitev števila n. Primer: 3 + 1 + 1 je razčlenitev števila 5 . Poiščimo vse
razčlenitve števila 5. Pri tem vzemimo, da zapisi , ki se razlikujejo le v vrstnem
redu členov, predstavljajo isto razčlenitev . Člene v zapisu uredimo po velikosti,
od največjega do najmanjšega:
5 5
4+1
3+2
3 + 1 + 1
2+2+1
2+1+1+1
1 + 1 + 1 + 1 + 1
Naj bo R(n) število razčlenitev števila n . Pravkar smo ugotovili, da je R(5) = 7.
Podobno kot R(5) poiščimo prvih nekaj števil R(n):
n O 1 2 3 4 5 6 7 8 9 10
R(n) 1 1 2 3 5 7 11 16 22 30 42
Vrednost R(O) = 1 se zdi morda nenavadna, toda število O zares ima natanko
eno razčlenitev, namreč prazno (brez členov) .
Matematični svet slavi letos stoletnico rojstva genialnega indijskega mate-
matika Srinivase Ramanujana (1887 - 1920) . O njem ste lahko predlani bra li
v rubrik i Bistrovidec (V. Batagelj: Taksi št. 1729, Presek 13 (1985/86) 4,
st r. 226). Med drugim je Ramanujan (skupaj z angleš kim matematikom
G.H. Hardyjem) odkril tudi točno formu lo za števila R(n) . Razumevanje
formule je zahtevno, zato je ne bomo navedli, pač pa vas vabimo k rač u nanj u
teh števil s pomočjo računalnika.
S tvorbo vseh razčlenitev ne pridemo daleč, tudi z rač u na l n i kom ne, saj
ima npr . število R(100) devet desetiških mest , R( 1000) pa že dvain trideset.
Poizkusimo nalogo rešiti tako, da jo posplošimo - včasih je namreč splošnejši
problem lažji od posebnega primera. Naj bo torej R(k, n) število vseh t ist ih
razčlenitev števila n, pri katerih največji člen ni večji od k . Kako bi raču nali
števila R(k, nj? Če nam to uspe, bomo lahko rač u na li tudi števila R(nl. saj
je pri k ~ nočitno R(k, n) = R(n).
172
Razčlenitve , kate rih največji člen ne presega števila k, lahko razdelimo na
tiste, pri katerih je največji člen enak k, in tiste, pri katerih je največji člen
manjši od k . Če pr i prv ih največji člen izpustimo, dobimo razčlenitev števi la
n - k, pri kateri je največji člen spet manjši ali enak k . Torej je prvih ravno
R(k, n - k). Pri drugih pa največji člen ne presega števila k - 1, torej j ih je
R(k - 1, nj . Dobili smo rekurzivno fo rmu lo
R(k, n) = R(k, n - k) + R(k - 1, n)
ki velja za n ;;;;. k ;;;;. 1. Ker vemo, da je R(O, n) = O, če je n;;;;' 1, in R(O, O) = 1,
lahko začnemo rač unati . Na poti do cilja je še precej težav - a ker je naloga
nagradna, prepuščamo nadaljevanje vam.
NALOGA: Izračunajte R(n) za karseda velik n. Pri tem hočemo točno
vrednost, torej vse cifre. Poslani izdelek naj vsebuje:
1. števili n in R(n)
2. kratko razlago uporabljenega postopka
3. program
4. podatke o računalniku (tip, velikost pomnilnika)
5. podatke, koliko časa je računalnik porabil za računanje števila R (n)
iz 1. točke
Pri ocenjevanju prav i ln ih odgovorov bomo upoštevali:
1. velikost števila n (glede na tip in vel ikost računalnika)
2. kakovost uporabljenega postopka
3. ličnost programa.
Tudi če se vaš izdelek odl ikuje le ven i od teh treh kategorij (np r. n iste
prišli daleč z n-jem, ste se pa potrudili in napisali l i č en program; ali pa ste
izračunali R(n) za velik n , medtem ko je program pravo sračje gnezdo), nam
ga vsekakor pošljite. Najboljši triji reševalci bodo dobili knjižne nagrade.
Izvirno rešitev bomo objavili .
Rok za pošiljanje izdelkov: 1.111 . 1988. Na ovojnico poleg naslova prip i-
šite: (za Ramanujan).
Pripomba o terminologiji: S tujo besedo rečemo zapisu števila v oblik i vsote
particija. Nekate r i uporabljajo izraz razbitje, ki pa ima rahel prizvok nečesa
nasilnega. Ker sestavnim delom aritmetičnega izraza, k i ima obliko vsote,
rečemo členi (prim . izraze enočlenik, dvočlenik ipd.),se mi zdi morda še naj-
pr imernejši izraz razčlenitev.
Marko Petkovšek
173