Mince zajíma jí nejen numismatiky
(Coins
are of interest not only for numismatists)
L'ubomíra Dvoøáková, Marie Dohnalová, Praha
Abstrakt
V èlánku zmíníme pojmy týkající se platby mincemi, které souvisejí s optimalitou poètu pou¾itých mincí. V pøípadì problému platby (øíká se také rozmìòování { anglicky
change making problem),
tj. skládání èástky
z mincí bez mo¾nosti vracení, jsou úlohy spojené s optimalitou dobøe prozkoumané. Analogické úlohy zformulujeme pro smìnu, tj. skládání èástky z mincí s mo¾ností vracení. Zde zùstává naopak øada problémù otevøená.
Úvod U¾ jste nìkdy pøemý¹leli o výhodách a nevýhodách hodnot èeských mincí? Platíme ka¾dou èástku relativnì nízkým poètem mincí? Lze takové výhodné platby provádìt hladovým algoritmem? Nevyplatilo by se do èeského systému nìjakou minci pøidat? A bylo výhodné ukonèit v roce 2008 platnost padesátníku? A co kdy¾ porovnáme èeské koruny s americkými centy, eury nebo nìkterými exotickými mìnami? Budou v nìjakých ohledech èeské koruny výhodnìj¹í? Tyto a podobné otázky si klade J. Shallit a kol. v èlánku [4], který nás inspiroval ke studiu této problematiky, a také první z autorek v èlánku [1]. My se nyní ov¹em témìø odpoutáme od reálných systémù mincí a budeme studovat problematiku obecnìji. V první èásti de nujeme a prozkoumáme reprezentaci èástek pøi platbì a speciálnì optimální reprezentaci a s ní související optimální systémy mincí. Dále se budeme zabývat hladovou reprezentací a s ní spjatými optimálními hladovými systémy. Vy¹etøíme, jaký vztah mezi optimálními a hladovými reprezentacemi splòují obvykle reálné systémy mincí. Dále uvedeme známé výsledky týkající se slo¾itosti nejznámìj¹ích platebních problémù. Ve druhé èásti de nujeme smìnu a zformulujeme pro ni analogické pojmy jako pro platbu. Uvedeme, které problémy zùstávají v pøípadì smìny otevøené, a zmíníme, jaké výsledky z teorie numeraèních systémù by mohly pøi jejich øe¹ení pomoci.
1
Platba
Platbou rozumíme, vágnì øeèeno, skládání èástky pomocí daných mincí. De nice 1. Mìjme D ∈ N, e1 , e2 , . . . , eD ∈ N (mince), kde 1 = eP 1 < e2 < D . . . < eD , dále N ∈ N 1 a n ∈ {1, 2, . . . , N } (èástka). Pokud n = i=1 ai ei , kde ai ∈ N ∪ {0}, pak (aD , . . . , a2 , a1 ) nazveme reprezentací n (pøi platbì). 2 1 V reálných systémech mincí obvykle klademe N rovné hodnotì nejni¾¹í bankovky. Pro èeské mince je tedy N = 100, pro americké centy takté¾ N = 100 (kovový dolar je spí¹e raritou). 2 Èasto budeme pro jednoduchost nazývat reprezentací pøímo zápis ve tvaru PD a e . i=1 i i
1
Øíkáme, ¾e tato reprezentace je optimální (nebo minimální), pokud minimální mezi v¹emi reprezentacemi èástky n.
Pøíklad 1. Uva¾ujeme-li èeské koruny
20, e6 = 50, pak
PD
i=1
ai je
e1 = 1, e2 = 2, e3 = 5, e4 = 10, e5 =
30 = 1 · 20 + 1 · 10 = 30 · 1,
tedy (0, 1, 1, 0, 0, 0) a (0, 0, 0, 0, 0, 30) jsou pøíklady reprezentací èástky 30Kè, pøièem¾ první z nich je optimální. Jak uvidíme za chvíli, v pøípadì èeských korun má ka¾dá èástka jedinou optimální reprezentaci. Nemusí tomu tak ov¹em být v¾dy. Mìjme mince v hodnotách e1 = 1, e2 = 2, e3 = 3, e4 = 4, potom 5 = 1 · 4 + 1 · 1 = 1 · 3 + 1 · 2,
tedy optimální reprezentace 5 jsou (1, 0, 0, 1) i (0, 1, 1, 0).
Poznámka 1. Pro zaji¹tìní jednoznaènosti optimální reprezentace se obvykle
de nice doplòuje tak, ¾e optimání reprezentací rozumíme lexikogra cky nejvìt¹í 3 z reprezentací, které obsahují minimální poèet mincí. V pøedchozím pøíkladì je tedy optimální reprezentací 5 pøi takto roz¹íøené de nici reprezentace (1, 0, 0, 1). Pøirozenou úlohou je hledání systémù mincí, kde prùmìrný poèet mincí pou¾itých v optimálních reprezentacích je minimální. Zavedeme takové systémy formálnì.
De nice 2. Mìjme
D, N ∈ N. Pak systém e1 , e2 , . . . , eD ∈ N, kde 1 = e1 < e2 < . . . < eD , nazveme optimální (pro platbu), jestli¾e nabývá minimální hodnoty výraz (v tabulkách ho oznaèíme P (D, N )) 4 : N 1 X (poèet mincí v optimální reprezentaci n pro mince e1 , e2 , . . . , eD ). N n=1
Poznámka 2. Právì fakt, ¾e pro ètyøi mince a èástky 1−100 obsahuje optimální systém mince v hodnotách 1, 5, 18, 25 (viz tabulka 1), vysvìtluje název èlánku J. Shallita a kol.: What this country needs is an 18c piece [4]. V americkém systému centù v hodnotách 1, 5, 10, 25 by staèilo pro zaji¹tìní optimality nahradit desetník hodnotou 18c. Dá se ale oèekávat, ¾e k tomu nikdo jiný ne¾ matematici nebude svolný. Hledat optimální reprezentace èástek není obvykle jednoduchá úloha. K její slo¾itosti se zanedlouho dostaneme. Pøedstavme nyní typ reprezentací, které se hledají snadno. 3 Øíkáme, ¾e posloupnost (a , . . . , a , a ) je lexikogra cky vìt¹í ne¾ (b , . . . , b , b ), pokud 2 1 2 1 D D jsou rùzné a nejvy¹¹í index j , kde se li¹í, splòuje aj > bj . 4 Ètenáøi se mù¾e zdát nelogické, proè reprezentujeme èástky a¾ do hodnoty N , tedy do hodnoty nejni¾¹í bankovky vèetnì, místo aby poslední èástka byla N − 1. Vysvìtlení je jednoduché: pøi poèítání prùmìrù je hezèí dìlit hodnotou 100 ne¾ hodnotou 99.
2
poèet mincí D 3 4 5 6
hodnoty 1,12,19 1,5,18,25 1,5,16,23,33 1,2,7,19,29,33
P (D, 100)
5,21 3,93 3,33 3,01
Tabulka 1: Optimální systémy pro platbu èástek 1 − 100 (N = 100) pro poèet mincí D ∈ {3, 4, 5, 6} získané programem v Javì.
De nice 3. Mìjme D, N
∈ N, e1 , e2 , . . . , eD ∈ N, kde 1 = e1 < e2 < . . . < eD a n ∈ {1, 2, . . . , N }. Reprezentaci (aD , . . . , a2 , a1 ) nazveme hladovou reprezentací n (pøi platbì), pokud je získaná hladovým algoritmem. Tedy v prvním kroku klademe aD := k, kde k ∈ N ∪ {0}, n − keD ≥ 0 a n − keD je minimální. Pokud n = aD eD , pak jsme nalezli hladovou reprezentaci. Jinak podobnì pokraèujeme pro kladnou èástku n − aD eD . Tedy ve druhém kroku klademe aD−1 := j , kde j ∈ N∪{0}, n−aD eD −jeD−1 ≥ 0 a n−aD eD −jeD−1 je minimální. Analogicky postupujeme dále.
Poznámka 3. Hladová reprezentace je v¾dy jediná. Z hladového algoritmu je vidìt, ¾e hladová reprezentace je lexikogra cky nejvìt¹í ze v¹ech reprezentací.
Pøíklad 2. Uva¾ujeme-li èeské koruny, pak hladovým algoritmem dostaneme 30 = 1 · 20 + 1 · 10, tj. hladová reprezentace je rovna (0, 1, 1, 0, 0, 0) a splývá
s optimální reprezentací. Tato situace nastává pro v¹echny èástky. V jiných systémech mincí ale nemusí být optimální a hladová reprezentace ka¾dé èástky stejná. Napøíklad pro optimální systém ètyø mincí e1 = 1, e2 = 5, e3 = 18, e4 = 25 máme 36 = 2 · 18 = 1 · 25 + 2 · 5 + 1 · 1, pøièem¾ první reprezentace (0, 2, 0, 0) je optimální a druhá (1, 0, 2, 1) je hladová. Opìt se nabízí úloha hledat systémy mincí, kde prùmìrný poèet mincí pou¾itých v hladových reprezentacích je minimální. De nujme takové systémy formálnì.
De nice 4. Mìjme
D, N ∈ N. Pak systém e1 , e2 , . . . , eD ∈ N, kde 1 = e1 < e2 < . . . < eD , nazveme optimální hladový (pro platbu), jestli¾e nabývá mini-
mální hodnoty výraz:
N 1 X (poèet mincí v hladové reprezentaci n pro mince e1 , e2 , . . . , eD ). N n=1
Zajímavou úlohou je zkoumat systémy mincí, v nich¾ splývá optimální a hladová reprezentace ka¾dé èástky. V pøíkladu 2 jsme zmiòovaly, ¾e pro èeské koruny tomu tak je, ale uvádìly jsme zároveò pøíklad systému, kde tomu tak není. V dal¹ím textu pøedstavíme Pearsonùv algoritmus, který umo¾òuje tuto úlohu pro daný systém efektivnì øe¹it. Právì tento algoritmus nám umo¾nil prozkoumat chování reálných systémù mincí. Vy¹etøovaly jsme systémy mincí celkem 3
poèet mincí D 3 3 4 4 5 6 6 6 6 6 6
hodnoty 1,5,22 1,5,23 1,3,11,37 1,3,11,38 1,3,7,18,45 1,2,5,11,25,62 1,2,5,11,25,63 1,2,5,11,25,64 1,2,5,13,29,64 1,2,5,13,29,65 1,2,5,13,29,66
P (D, 100)
5,34 5,34 4,16 4,16 3,50 3,17 3,17 3,17 3,17 3,17 3,17
Tabulka 2: Optimální hladové systémy pro platbu èástek 1 − 100 (N = 100) pro poèet mincí D ∈ {3, 4, 5, 6} získané programem v Javì. ®ádný ze systémù není zároveò optimální. 195 státù (tìch, které USA uznávají za nezávislé státy) a zdá se, ¾e podmínka, aby optimální reprezentace ¹lo poèítat hladovým algoritmem, tj. aby optimální a hladové reprezentace v¹ech èástek splývaly, hraje dùle¾itou roli pøi volbì systémù mincí. K neshodì optimálních a hladových reprezentací dochází pouze pro: • západoafrický frank (Benin, Burkina Faso, Pobøe¾í slonoviny), • jamajský dolar, • malga¹ský ariar (Madagaskar), • somoni (Tád¾ikistán).
Neshodu zpùsobuje navíc v¾dy fakt, ¾e nejmen¹í mince mají hodnoty 1, 10, 25, proto¾e pak platí napø.: 30 = 3 · 10 = 1 · 25 + 5 · 1,
pøièem¾ první reprezentace je optimální a druhá je hladová. 1.1
Slo¾itost nìkterých platebních problémù
Hledat optimální reprezentace a optimální systémy mincí je èasovì nároèná úloha. O slo¾itosti je známo následující (detaily jsou k nalezení v [4]):
Otázka: Mìjme
D, N ∈ N, e1 , e2 , . . . , eD ∈ N, kde 1 = e1 < e2 < . . . < eD a n ∈ {1, 2, . . . , N }. Jak tì¾ké je najít optimální reprezentaci n? Odpovìï: Není znám algoritmus, který by provádìl polynomiálnì mnoho aritmetických operací v D s èísly velikosti O(eD ).
4
Otázka: Mìjme
D, N ∈ N, e1 , e2 , . . . , eD ∈ N, kde 1 = e1 < e2 < . . . < eD a n ∈ {1, 2, . . . , N }. Jak tì¾ké je rozhodnout, zda je stejná optimální a hladová reprezentace n? Odpovìï: Není znám algoritmus, který by provádìl polynomiálnì mnoho aritmetických operací v D s èísly velikosti O(eD ).
Otázka: Mìjme
D ∈ N, e1 , e2 , . . . , eD ∈ N, kde 1 = e1 < e2 < . . . < eD . Jak tì¾ké je zjistit, zda je stejná optimální a hladová reprezentace ka¾dé èástky n ∈ N? Odpovìï (pøekvapivì!): Existuje Pearsonùv algoritmus, který provádí O(D3 ) aritmetických operací s èísly velikosti O(eD ). Popi¹me si struènì, jak Pearsonùv algoritmus [5] funguje: • Pokud nesplývá pro ka¾dou èástku optimální a hladová reprezentace, pak existují i, j ∈ N, kde 1 ≤ j ≤ i < D, taková, ¾e optimální reprezentace
nejmen¹ího protipøíkladu je tvaru: n n
= (aj + 1)ej + aj+1 ej+1 + . . . + ai ei = (aj + 1)ej P kde hladová reprezentace ei+1 − 1 = ik=1 ak ek .
pro j < i, pro j = i,
(1)
• Testujeme tedy v¹echna i, j pøipadající v úvahu a hledáme nejmen¹í n
ve tvaru (1), pro které poèet mincí v hladové reprezentaci je vìt¹í ne¾ poèet mincí v reprezentaci (1), tj. ne¾ (aj + 1) + aj+1 + . . . + ai . Pokud takové n najdeme, pak jde o nejmen¹í èástku, její¾ optimální a hladová reprezentace nesplývá. Pokud takové n nenajdeme, pak splývají optimální a hladové reprezentace v¹ech èástek.
Pøíklad 3. V pøíkladu 2 jsme ukazovaly, ¾e optimální systém ètyø mincí e1 = 1, e2 = 5, e3 = 18, e4 = 25 nesplòuje, ¾e by splývala optimální a hladová reprezentace ka¾dé èástky. Konkrétnì jsme jako protipøíklad uvádìly èástku 36 centù. Nyní vy¹etøíme Pearsonovým algoritmem, zda je tento protipøíklad minimální. Máme 1 ≤ j ≤ i < 4, tedy je tøeba uva¾ovat uspoøádané dvojice (j, i) ∈ {(1, 1), (1, 2), (2, 2), (1, 3), (2, 3), (3, 3)}. Kandidáti na protipøíklad (vlevo èástka n, vpravo eventuální optimální reprezentace) jsou pak: 5 18 22 25 29 42
= = = = = =
5 · 1, 3 · 1 + 3 · 5, 2 · 1 + 4 · 5, 2 · 1 + 1 · 5 + 1 · 18, 1 · 1 + 2 · 5 + 1 · 18, 1 · 1 + 1 · 5 + 2 · 18.
Pouze v pøípadì èástky 29 pou¾ívá hladová reprezentace více mincí ne¾ reprezentace z vý¹e uvedeného seznamu kandidátù. Hladová reprezentace je toti¾ rovna 29 = 4·1+1·25, tedy pou¾ívá pìt mincí, zatímco reprezentace 29 = 1·1+2·5+1·18 pou¾ívá ètyøi mince a je optimální. Èástka 29 je tudí¾ nejmen¹í èástkou, pro ni¾ hladová a optimální reprezentace nesplývají. 5
Pøíklad 4. Uka¾me si vyu¾ití Pearsonova algoritmu k zodpovìzení otázky, zda
splývají optimální a hladové reprezentace v¹ech èástek pro systém mincí v hodnotách 1, b, b2 , . . . , bD−1 , kde b > 1. Podle Pearsonova algoritmu, pokud by existovala èástka, pro ni¾ jsou rùzné optimální a hladová reprezentace, pak by nejmen¹í takový protipøíklad mìl tvar: n n
= bej + (b − 1)ej+1 + . . . + (b − 1)ei = bej
pro j < i, pro j = i,
(2)
i−1 i proto¾e hladová reprezentace ei+1 −1 = bi −1 = k=0 (b−1)bk = k=1 (b−1)ek . Není tì¾ké si rozmyslet, ¾e n = ei+1 . Odtud ale plyne, ¾e hladová (i optimální) reprezentace n obsahuje jedinou minci, a to ei+1 , co¾ je ménì ne¾ b+(b−1)(i−j) (poèet mincí v reprezentaci (2)). Proto optimální i hladové reprezentace v¹ech èástek splývají.
P
2
P
Smìna
Obvyklým problémem pøi placení mincemi je také smìna, kdy pøipou¹tíme i mo¾nost vracení.
De nice 5. Mìjme D ∈ N, e1 , e2 , . . . , eD ∈ N, kde P 1 = e1 < e2 < . . . < eD , dále N ∈ N a n ∈ {1, 2, . . . , N }. Pokud n = D i=1 ai ei , kde ai ∈ Z, pak (aD , . . . , a2 , a1 ) nazveme reprezentací n (pøi smìnì). Øíkáme, ¾e tato repreP zentace je optimální, pokud D i=1 |ai | je minimální mezi v¹emi reprezentacemi èástky n. Pøíklad 5. Optimální reprezentace dané èástky pøi smìnì pou¾ívá samozøejmì ménì nebo stejnì mincí jako optimální reprezentace této èástky pøi platbì. Napø. pro èeské koruny máme: 8 = 1 · 5 + 1 · 2 + 1 · 1 = 1 · 10 + (−1) · 2,
pøièem¾ první reprezentace je optimální pøi platbì a potøebuje tøi mince a druhá je optimální pøi smìnì a potøebuje jen dvì mince. Jistì opìt není optimální reprezentace jednoznaèná. Jednak mù¾e nejednoznaènost plynout u¾ z nejednoznaènosti pøi platbì. Navíc mù¾e nejednoznaènost vzniknout pøipu¹tìním ¹ir¹í mno¾iny koe cientù. Napø. pro èeské mince je optimální reprezentace ka¾dé èástky pøi platbì jednoznaèná, ale optimální reprezentace èástky 15 pøi smìnì má dvì mo¾né podoby: 15 = 1 · 20 + (−1) · 5 = 1 · 10 + 1 · 5.
Navíc u¾ není jasné, proè upøednostnit mezi v¹emi optimálními reprezentacemi lexikogra cky nejvìt¹í. Proè by napø. pro mince 1, 2, 98, 100 mìla mít pøednost reprezentace 2 = 1·100+(−1)·98 pøed 2 = 2·1? Poznamenejme, ¾e pro optimální i hladovou reprezentaci pøi platbì platí tvrzení [5]: Pokud (aD , . . . , a2 , a1 ) a (bD , . . . , b2 , b1 ) jsou posloupnosti s èleny z N ∪ {0} a zároveò ai ≥ bi pro ka¾dé 6
poèet mincí D 3 3 4 5 5 6 6
hodnoty 1,18,25 1,20,28 1,21,30,35 1,11,34,40,49 1,26,30,40,47 1,5,26,34,45,48 1,5,26,37,46,49
P (D, 100)
4,01 4,01 3,16 2,77 2,77 2,53 2,53
Tabulka 3: Optimální systémy pro smìnu èástek 1 − 100 (N = 100) pro poèet mincí D ∈ {3, 4, 5, 6} získané programem v Javì. i ∈ {1, 2, . . . , D}, potom platí implikace: je-li (aD , . . . , a2 , a1 ) optimální, resp. hladová reprezentace, potom (bD , . . . , b2 , b1 ) je také optimální, resp. hladová re-
prezentace. Tato vlastnost se pøi smìnì nezachovává a není ani známá nìjaká jí podobná.
Analogicky jako v pøípadì platby nás mohou zajímat systémy mincí, kde prùmìrný poèet mincí pou¾itých v optimálních reprezentacích je minimální.
De nice 6. Mìjme
D, N ∈ N. Pak systém e1 , e2 , . . . , eD ∈ N, kde 1 = e1 < e2 < . . . < eD , nazveme optimální (pro smìnu), jestli¾e nabývá minimální
hodnoty výraz:
N 1 X (poèet mincí v optimální reprezentaci n pro mince e1 , e2 , . . . , eD ). N n=1
Opìt platí, ¾e pro hledání optimální reprezentace nemáme k dispozici efektivní algoritmus, proto se pokusíme najít jednoduchou reprezentaci, která se nabízí jako analogie hladové reprezentace.
De nice 7. Mìjme D, N
∈ N, e1 , e2 , . . . , eD ∈ N, kde 1 = e1 < e2 < . . . < eD a n ∈ {1, 2, . . . , N }. Reprezentaci (aD , . . . , a2 , a1 ) nazveme hladovou reprezentací n (pøi smìnì), pokud je získaná jistým zobecnìným hladovým algoritmem, kdy v ka¾dém kroku bereme nejbli¾¹í vìt¹í èi men¹í minci. Tedy v prvním kroku najdeme j ∈ {1, . . . , D − 1} tak, ¾e ej ≤ n ≤ ej+1 . Pokud n − ej ≤ ej+1 − n, pak pí¹eme n = ej + z a zbytek z reprezentujeme dále analogicky (dokud není nulový). Pokud n − ej ≥ ej+1 − n, pak pí¹eme n = ej+1 − z a zbytek z reprezentujeme dále analogicky (dokud není nulový).
Pøíklad 6. Hladová reprezentace pøi smìnì u¾ nemusí být jednoznaèná. Uva¾ujemeli napøíklad èeské koruny, pak hladové reprezentace èástky 35 jsou hned ètyøi: 35 = 1 · 20 + 1 · 10 + 1 · 5, 35 = 2 · 20 + (−1) · 5, 35 = 1 · 50 + (−1) · 10 + (−1) · 5, 35 = 1 · 50 + (−1) · 20 + 1 · 5.
7
Ètenáø si ale snadno doká¾e (tøeba pomocí indukce), ¾e pro danou èástku obsahuje ka¾dá hladová reprezentace stejný poèet mincí.
Poznámka 4. Zatímco ka¾dá reprezentace pøi platbì je zároveò reprezentací pøi
smìnì, a tudí¾ optimální reprezentace dané èástky pøi smìnì pou¾ívá maximálnì tolik mincí, kolik optimální reprezentace této èástky pøi platbì, pro hladovou reprezentaci u¾ toto není pravda. Existují systémy mincí takové, ¾e nìkteré èástky obsahují v hladové reprezentaci pøi smìnì více mincí ne¾ v hladové reprezentaci pøi platbì. Napø. pro systém mincí e1 = 1, e2 = 3, e3 = 5, e4 = 10 máme: 8 = 1 · 5 + 1 · 3, 8 = 1 · 10 + (−2) · 1 = 1 · 10 + (−1) · 3 + 1 · 1,
pøièem¾ první reprezentace obsahuje dvì mince a je hladová pøi platbì a druhé dvì obsahují tøi mince a jsou hladové pøi smìnì. Opìt jsme vy¹etøovaly systémy mincí, kde prùmìrný poèet mincí pou¾itý v hladových reprezentacích pøi smìnì je minimální.
De nice 8. Mìjme
D, N ∈ N. Pak systém e1 , e2 , . . . , eD ∈ N, kde 1 = e1 < e2 < . . . < eD , nazveme optimální hladový (pro smìnu), jestli¾e nabývá mini-
mální hodnoty výraz:
N 1 X (poèet mincí v hladové reprezentaci n pro mince e1 , e2 , . . . , eD ). N n=1
Podobnì jako v pøípadì platby by nás mohlo zajímat, kdy splývá optimální a hladová reprezentace pøi smìnì. Proto¾e nyní není ani optimální ani hladová reprezentace dána jednoznaènì, je nejprve tøeba upøesnit, co budeme vlastnì vy¹etøovat. Uva¾ujme D, N ∈ N, systém e1 , e2 , . . . , eD ∈ N, kde 1 = e1 < e2 < . . . < eD , a èástku n ∈ {1, . . . , N }. Shròme si, co víme, a závìrem z poznatkù odvodíme otázky ke zkoumání. • Je zøejmé z de nice 6, ¾e ka¾dá optimální reprezentace n pøi smìnì obsahuje stejný poèet mincí, oznaème jej K . • Zmiòovaly jsme, ¾e ka¾dá hladová reprezentace n pøi smìnì obsahuje stejný poèet mincí, oznaème jej M . • Pokud K = M , potom ka¾dá hladová reprezentace n je zároveò optimální. • Pokud K < M , potom ¾ádná hladová reprezentace n není optimální.
Nyní mù¾eme zkoumat, který z následujících pøípadù pro èástku n platí: 1. K = M a existuje optimální reprezentace, která není hladová (øekneme, ¾e optimální a hladové reprezentace èástky n splývají èásteènì ).
8
poèet mincí D 3 4 4 5 5 5 6 6 6 6 6 6
hodnoty 1,6,33 1,4,13,48 1,4,15,48 1,2,7,22,71 1,2,7,23,74 1,2,7,23,75 1,2,7,12,41,70 (71, 80, 81) 1,2,7,12,42,81 1,2,7,12,51,80 (81) 1,2,7,12,52,81 1,2,7,13,44,85 1,2,7,13,54,85
P (D, 100)
4,18 3,34 3,34 2,96 2,96 2,96 2,73 2,73 2,73 2,73 2,73 2,73
Tabulka 4: Optimální hladové systémy pro smìnu èástek 1 − 100 (N = 100) pro poèet mincí D ∈ {3, 4, 5, 6} získané programem v Javì. Kdy¾ existuje více optimálních hladových systémù a li¹í se pouze v nejvy¹¹í minci, uvádíme hodnotu rùzných variant nejvy¹¹í mince v závorce. 2. K = M a navíc mno¾ina optimálních reprezentací a mno¾ina hladových reprezentací jsou stejné (optimální a hladové reprezentace èástky n splývají zcela ). 3. K < M (optimální a hladové reprezentace èástky n nesplývají ).
Pøíklad 7. Uva¾ujme mince e1 = 1, e2 = 3, e3 = 5, e4 = 10. Potom 8 = 1·5+1·3
je optimální reprezentace pøi smìnì, která není hladová pøi smìnì. Dále 8 = 1·10+(−2)·1 je hladová reprezentace pøi smìnì, která není optimální pøi smìnì. Proto v takovém systému nesplývají reprezentace èástek, nastává tedy pøípad 3.
Pøíklad 8. Uva¾ujme mince e1 = 1, e2 = 2, e3 = 3, e4 = 5, e5 = 8. Potom 7 = 1·5+1·2 je optimální reprezentace pøi smìnì, která není hladová pøi smìnì. Dále 7 = 1 · 8 + (−1) · 1 je hladová reprezentace pøi smìnì, která je zároveò
optimální pøi smìnì. Proto v takovém systému nesplývají zcela reprezentace èástek. Nastává tudí¾ buï pøípad 1, nebo 3. 2.1
Otevøené problémy pro smìnu
Èlánek zakonèíme shrnutím otázek týkajících se smìny, na nì¾ nám nejsou známy odpovìdi. 1. Existuje analogie Pearsonova algoritmu pro smìnu? Tedy existuje efektivní algoritmus, který pro daný systém rozhodne, zda splývají optimální a hladové reprezentace v¹ech èástek (a» u¾ zcela, nebo èásteènì)? 2. Splývá optimální a hladová reprezentace ka¾dé èástky pøi smìnì: 9
(a) v systému mincí 1, b, b2 , . . . , bD−1 , kde b > 1 (a» u¾ zcela, nebo èásteènì)? Algoritmus pro hledání jedné optimální reprezentace ka¾dé èástky je známý [3]. (b) v systému mincí v hodnotách Fibonacciho èísel 1, 2, 3, 5, 8, . . . (a to èásteènì, proto¾e zcela nesplývají, viz pøíklad 8)? Algoritmus pro hledání jedné optimální reprezentace ka¾dé èástky je známý [2]. 3. Lze de novat hladovou reprezentaci pøi smìnì lépe? Tedy tak, aby v¾dy pou¾ívala men¹í nebo stejný poèet mincí jako hladová reprezentace pøi platbì dané èástky.
Reference [1] Balková L'., ©»astná A., Jsou èeské mince optimální?, Rozhledy matematicko{fyzikální 90 (1{2) (2015), 14{22. [2] Heuberger C., Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms, Periodica Mathematica Hungarica 49 (2004), 65{89. [3] Heuberger C., Prodinger H., On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing 66 (2001), 377{ 393. [4] Kleber M., Shallit J., Vakil R., What this country needs is an 18c piece, Mathematical Intelligencer 25 (2003), 20{23. [5] Pearson D., A polynomial-time algorithm for the change-making problem, Operations Research Letters 33 (3) (2005), 231{234.
doc. Ing. L'ubomíra Dvoøáková, Ph.D. Katedra matematiky FJFI ÈVUT v Praze Trojanova 13 Praha 2, 120 00 lubomira.dvorakova@fj .cvut.cz
10
Marie Dohnalová gymnázium EDUCAnet Praha Roztylská 1 Praha 4, 14000
[email protected]
