     
P 46 (2018/2019) 48
Koliko stane zbiranje sličic?
B̌ K
Nogometna mrzlica svetovnega prvenstva v Ru-
siji 2018 se je zdaj že povsem polegla, nekateri
navdušenci pa morda še vedno zbirajo in menja-
vajo zadnje manjkajoče sličice s podobami igral-
cev nogometnih reprezentanc. V albumu, ki je bil
naprodaj v Sloveniji, je prostora za 600 različnih
sličic. Te so se prodajale v paketkih s po 3 sliči-
cami s ceno 0,70 EUR za paket. Zlahka torej iz-
računamo, da je treba za poln album kupiti vsaj
200 paketkov, kar nas stane najmanj 140 EUR (oz.
skoraj 7 let naročnine na Presek). Seveda pa bo
končni strošek višji, ker so paketki in sličice v
njih bolj ali manj naključno premešane, vendar ga
lahko po drugi strani zmanjšamo z menjavanjem
sličic z drugimi zbiralci.
Preden nadaljujete z branjem, poskusite podati
svojo grobo oceno, koliko naključnih sličic je treba
kupiti, da bi brez menjavanja zbrali vseh 600 različ-
nih. Je to morda 1000, 2000, 3000 ali celo več sličic?
Koliko denarja bi torej tako porabili za poln album?
Ocena povprečnega števila kupljenih sličic, ki jih
potrebujemo za napolnitev albuma brez menjavanja,
predstavlja matematični problem s področja verje-
tnosti, ki je v angleščini znan tudi pod imenom Co-
upon collector’s problem [1]. Preden se lotimo nje-
govega reševanja po teoretični poti, lahko oceno po-
skusimo dobiti eksperimentalno. Bralke in bralci, ki
poznate osnove programiranja, boste zlahka napisali
ustrezno programsko simulacijo poskusa, pri kateri
program naključno izbira števila med 1 in 600, do-
kler ne zbere vseh različnih vrednosti.
Za šolsko rabo pa je zanimiva tudi poenostavljena
verzija eksperimenta zbiranja 6 različnih sličic, ki ga
lahko izvedemo s pomočjo običajne igralne kocke.
Igralno kocko vržemo večkrat zapored in si zapisu-
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
Povprečno število metov 15,1 1,0 1,2 1,9 2,5 2,6 5,9
10. 4211243624625 13 1 1 1 4 1 5
9. 133664442262616231133246265 27 1 1 2 2 3 18
8. 662563163364 12 1 2 1 2 1 5
7. 626662463652565332261 21 1 1 5 2 2 10
6. 124255444224663 15 1 1 1 2 8 2
5. 2152221535614 13 1 1 1 6 2 2
4. 6163452 7 1 1 2 1 1 1
3. 4666633142664335 16 1 1 4 2 2 6
2. 5424113356 10 1 1 1 2 2 3
1. 66343143353153312 17 1 2 1 2 4 7
Št. Zaporedje padlih vrednosti Št. metov T1 T2 T3 T4 T5 T6
TABELA 1.
Rezultati desetih ponovitev poskusa s kocko. Z modro je obarvana prva pojavitev posamezne vrednosti v zaporedju.
     
P 46 (2018/2019) 4 9
jemo zaporedje padlih vrednosti. Ko se v zaporedju
pojavi vseh 6 različnih vrednosti, preštejemo število
potrebnih metov in poskus ponovimo. Pri dovolj ve-
likem številu ponovitev bo aritmetična sredina meri-
tev predstavljala oceno iskanega povprečja za album
s 6 sličicami. Pri 10 ponovitvah poskusa, kot so zapi-
sane v tabeli, smo denimo dobili povprečno vrednost
151/10 oz. 15,1.
Pa si oglejmo, kako bi povprečno število potreb-
nih metov izračunali matematično. Pri posameznem
metu poštene kocke je matematična verjetnost šesti-
ce enaka p = 1/6, saj je ugoden le eden od šestih
enako verjetnih izidov. Statistično to pomeni, da bo
pri velikem številu metov delež padlih šestic enak
1/6, ali, povedano drugače, v povprečju bo šestica
padla vsak šesti met. Torej bo od začetka poskusa
do prve šestice potrebnih v povprečju 6 metov. Po-
dobno velja tudi pri neodvisnih zaporednih pono-
vitvah poskusa, pri katerem se ugoden dogodek
zgodi z verjetnostjo p > 0. Povprečno število po-
novitev poskusa do prvega uspeha je tedaj enako
1/p.
Od te ugotovitve ni več daleč do izračuna povpreč-
nega števila potrebnih metov, s katerimi bi zbrali vse
različne vrednosti. Razmišljamo namreč takole. Prvo
od šestih vrednosti bomo zagotovo dobili v prvem
metu. Ko eno vrednost že imamo, bo v naslednjem
metu z verjetnostjo 5/6 padla ena od vrednosti, ki je
še nimamo, torej bomo za drugo vrednost v povpre-
čju potrebovali še 6/5 = 1,2 meta kocke. Ob tem smo
seveda upoštevali, da so zaporedni meti med seboj
neodvisni, torej predhodni meti na naslednjega ne
vplivajo. Zdaj imamo že dve različni vrednosti, zato
bo naslednja manjkajoča padla z verjetnostjo 4/6 v
posameznem metu, oz. v povprečju po 6/4 = 1,5
meta, in tako dalje. Za zadnjo manjkajočo vrednost
bomo potrebovali v povprečju kar 6 metov, saj je
njena verjetnost v posameznem metu le 1/6. Na ta
način pridemo do števila
1+ 6
5
+ 6
4
+6
3
+6
2
+6
1
=6
(
1
6
+ 1
5
+ 1
4
+ 1
3
+ 1
2
+ 1
1
)
= 14,7.
To število predstavlja povprečno število metov oz.
kupljenih sličic pri velikem številu ponovitev zbira-
nja šestih različnih vrednosti. Izračunana vrednost
se približno ujema tudi z našo eksperimentalno me-
ritvijo. Prav tako se vrednosti členov v vsoti pribli-
žno ujemajo z izmerjenimi povprečnimi vrednostmi
števil Ti iz tabele 1, ki pomenijo število metov od
(i− 1) do i-te nove vrednosti.
SLIKA 1.
Za zadnjo manjkajočo vrednost je v povprečju potrebnih kar 6
metov od skupnega povprečja 14,7 meta.
Morda bi kdo iz tega prenagljeno sklepal, da je za
album s 600 različnimi sličicami treba kupiti okoli
1470 sličic. To seveda ne velja, povprečno število
kupljenih sličic je v tem primeru precej večje. S po-
snemanjem gornjega izračuna lahko ustrezni izraz
zdaj zlahka zapišemo in s pomočjo računalnika tudi
seštejemo:
600
(
1
600
+ 1
599
+ 1
598
+ . . .+ 1
1
)
.= 4184,987.
Če zaokrožimo navzgor, brez menjavanja sličic bi
morali torej za napolnitev albuma s 600 sličicami v
povprečju kupiti 4185 sličic. To pomeni 1395 pa-
ketkov, za katere bi odšteli skupaj kar 976,50 EUR.
Precej denarja, kaj ne?
Zadnji izračun velja ob predpostavkah, da so pa-
ketki in sličice v njih enakomerno in neodvisno po-
razdeljeni, torej, da so pri nakupu nove sličice vse
številke enako verjetne ne glede na predhodno ku-
pljene sličice ali druge sličice v istem paketku. Če
so denimo paketki treh sličic oblikovani tako, da v
njih ni podvajanja sličic, potem zadnja domneva ne
velja. Številni zbiralci tudi sumijo, da so nekatere
sličice redkejše od drugih, torej, da porazdelitev ni
enakomerna, a v to se ne bomo spuščali.
     
P 46 (2018/2019) 410
Če torej zaupamo proizvajalcu, da natisne enako
število vseh različnih sličic, ki so dobro premešane in
neodvisno razporejene v paketke na prodajnih me-
stih, potem je splošna rešitev problema zbiralca sli-
čic pri zbiranju n različnih sličic ob zgornjih pred-
postavkah enaka nHn, kjer je
Hn =
1
1
+ 1
2
+ . . .+ 1
n
t. i. n-to harmonično število. Kot je razvidno iz ne-
kaj vrednosti v tabeli, naraščanje števila nHn v od-
visnosti od n ni linearno. Bralcem z nekaj več ma-
tematičnega znanja omenimo, da je število nHn ve-
likostnega reda O(n logn), kar je posledica znanih
lastnosti harmoničnih števil.
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
nHn 14,70 280,80 4185,99 55660,88
n 6 60 600 6000
TABELA 2.
Nekaj vrednosti števila nHn
Pozorni bralec je iz dosedanje razprave verjetno
razbral, da je nadražje predvsem zbiranje zadnje pe-
ščice manjkajočih sličic. Samo za pridobitev zadnje
manjkajoče sličice v albumu za nogometno prven-
stvo 2018 bi jih morali v povprečju kupiti še 600,
kar bi stalo 140 EUR. Zato je zanimivo omeniti, da
založnik albuma omogoča, da zbiralec neposredno
naroči 100 izbranih sličic po ceni 0,25 EUR za sličico.
Za zadnjih 100 sličic bi sicer z naključnim kupova-
njem potrebovali v povprečju
600H100 = 600
(
1
100
+ 1
99
+ . . .+ 1
1
)
.= 3112,43
naključnih sličic, oz. zaokroženo navzgor, 1038 pa-
ketkov, kar znese 726,60 EUR. Z neposrednim naro-
čilom zadnjih 100 manjkajočih sličic tako zbiralec
v povprečju prihrani več kot 700 EUR in za napol-
nitev albuma porabi »le« 274,90 EUR (brez stroška
pošiljanja sličic). Že samo z neposrednim naroči-
lom zadnjih 20 manjkajočih sličic pa bi celotni stro-
šek zmanjšali za približno polovico, kar lahko bralec
premisli sam.
Pa si postavimo še nekoliko drugačno vprašanje.
Denimo, da imate 210 EUR, ki jih boste porabili za
nakup 300 paketkov s skupaj 900 sličicami. Koliko
različnih sličic za vaš album lahko v tem primeru pri-
čakujete?
Zdaj je razmislek nekoliko drugačen. Verjetnost,
da naključno kupljena sličica ni sličica številka 1, je
enaka 599600 . Verjetnost, da nobena od 900 kupljenih
sličic ni sličica številka 1, pa je enaka
(
599
600
)900 .=
0,22313. Zato je verjetnost, da je med 900 kuplje-
nimi tudi sličica številka 1, približno enaka 0,77687,
kar lahko tolmačimo tudi kot povprečno število sličic
številka 1 med 900 naključno kupljenimi. Da bi do-
bili povprečno število vseh različnih sličic med njimi,
pa lahko seštejemo povprečno število sličic številka
1, številka 2, in tako dalje vse do 600. Zato izraz
600 · 0,77687 .= 466,12
predstavlja povprečno število različnih sličic med
900 naključno kupljenimi izmed skupaj 600 različ-
nih. Za menjavo nam v tem primeru torej ostane v
povprečju 434 sličic, s katerimi bomo ob dovolj veli-
kem številu drugih zbiralcev v soseščini najbrž brez
težav zbrali manjkajočih 134 za poln album.
V vsakem primeru pa je zbiranje sličic precej drag
konjiček. Radovedna bralka in bralec lahko svoje ra-
zumevanje dosedanjih izračunov preizkusita z na-
slednjo nalogo.
Naloga. Izračunaj in primerjaj povprečni števili
različnih sličic, ki jih pri prej navedenih cenah do-
biš za 175 EUR, če:
vseh 175 EUR porabiš za nakup paketkov,
porabiš 140 EUR za nakup paketkov, od preostan-
ka pa porabiš 25 EUR za neposredno naročilo 100
manjkajočih sličic in 10 EUR za poštnino.
Rešitev. V prvem primeru kupiš 750 sličic, med ka-
terimi bo v povprečju približno 428 različnih. V dru-
gem primeru pa kupiš 700 sličic, med katerimi bo v
povprečju približno 479 različnih.
Literatura
[1] Coupon collector’s Problem, dostopno
na en.wikipedia.org/wiki/Coupon_
collector\%27s_problem, ogled 14. 1. 2019
[2] Harmonic number, dostopno na en.
wikipedia.org/wiki/Harmonic_number,
ogled 14. 1. 2019.
×××