UNIVERZA V LJUBLJANI FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika – 1. stopnja Luka Šinkovec Problem razmene denarja Delo diplomskega seminarja Mentor: izr. prof. dr. Aleš Vavpetič Ljubljana, 2021

(1)

UNIVERZA V LJUBLJANI

FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika – 1. stopnja

Luka Šinkovec

Problem razmene denarja

Delo diplomskega seminarja

Mentor: izr. prof. dr. Aleš Vavpetič

Ljubljana, 2021

(2)

Kazalo

1. Uvod 4

2. Preprosti problem nahrbtnika in njegove variacije 4

3. Posebni problem razmene denarja 12

3.1. Primer, ko je t = 2 15

3.2. Primer, ko je t = 3 16

4. Zaključek 28

5. Zahvala 28

Slovar strokovnih izrazov 28

Literatura 29

(3)

Problem razmene denarja

Povzetek

Posebni problem razmene denarja je le ena od variacij klasičnega problema razmene denarja, ki pa je prav tako le ena od variacij najširšega optimizacijskega problema v tej zgodbi – preprostega problema nahrbtnika. Najožja izmed teh variacij, posebni problem razmene denarja, sprašuje po vrednostih kovancev a₁, a₂, . . . , a_t, za katere obstaja natanko ena razmena z najmanjšim možnim skupnim številom kovancev teh vrednosti, ki jih uporabimo za razmeno, za vsako vsoto denarja, ki se jo s kovanci teh vrednosti da razmenjati. Predstavili bomo rešitev problema v primeru dveh kovancev različnih vrednosti ter nekaj metod za iskanje (oz. preverjanje ustreznosti) rešitev v primeru treh kovancev različnih vrednosti, ki ustrezajo določenim pogojem.

Money-changing problem

Abstract

The special money-changing problem is only one of the many variations of the classical money-changing problem, which is also only one of the many variations of the widest optimisation problem in this story – the knapsack problem. The narrowest of these variations, the special money-changing problem, asks for what denominations of money a₁, a₂, . . . , a_t, is there exactly one way to make change, using the fewest number of coins possible, for every amount for which change can be made using only coins of these denominations. We will provide a solution to this problem in the case of coins with two different denominations and a few methods for finding (or testing the correctness of) solutions in the case of coins with three different denominations, which all meet certain conditions.

Math. Subj. Class. (2020): 11D04

Ključne besede: preprosti problem nahrbtnika, problem poštnih znamk, klasični problem razmene denarja, problem kovancev, Frobeniusova formula, totalna razmena, optimalna razmena, posebni problem razmene denarja

Keywords: knapsack problem, postage stamp problem, classical money-changing problem, coin problem, Frobenius formula, denumerant (total change), optimal change, special money-changing problem

(4)

1. Uvod

Posebni problem razmene denarja je v resnici le variacija nekega splošnejšega problema – klasičnega problema razmene denarja, ki pa je prav tako le variacija še bolj splošnega problema – preprostega problema nahrbtnika. Slednji je znan optimizacijski problem, ki se je v literaturi prvič pojavil že davnega leta 1897, čeprav so se z nekaterimi njegovimi variacijami matematiki ukvarjali že mnogo prej. Ime mu je kasneje dodelil ameriški matematik Tobias Dantzig (1884–1956), ki se je v svojih zgodnjih delih ukvarjal s sorodnim problemom, kako v nahkrbtnik z omejeno prostornino spraviti čim bolj vredne predmete.

Kmalu za tem se je pojavilo mnogo različnih variacij preprostega problema nahrbtnika, med katerimi sta najbolj znani problem poštnih znamk in klasični problem razmene denarja. Ker za večino teh problemov ne obstajajo (ali pa še ne poznamo) konkretne metode oz. formule za iskanje rešitev, se je s pojavom računalnikov te probleme začelo reševati z razno raznimi numeričnimi algoritmi in metodami – s tem pa so problemi postali računalniški in ne več toliko optimizacijski. Še zmeraj pa obstaja nekaj problemov, ki so jih do sedaj uspeli rešiti na teoretični ravni. Najbolj znani izmed njih sta dve variaciji klasičnega problema razmene denarja – to sta problem kovancev in pa posebni problem razmene denarja, s katerim se bomo v nadaljevanju najpodrobneje ukvarjali. Prva izmed teh dveh variacij je problem kovancev, katerega posebni primer je znan tudi kot Frobeniusov problem oz. Frobeniusov problem kovancev, saj se je nemški matematik Ferdinand Frobenius (1849–1917) največ ukvarjal z njim. Po njem se imenuje tudi rešitev tega problema v tem posebnem primeru – Frobeniusova formula, čeprav jo je dejansko prvi formuliral in pa dokazal že angleški matematik James Sylvester (1814–1897). Kasneje se je s tem področjem nekoliko še ukvarjal Frobeniusov študent Issai Schur (1875–1941), ki je izpeljal tudi nekatere pomembne rezultate navezujoč se na to temo, med drugim Schurov izrek (ki se po njem tudi imenuje), ki govori o obstoju Frobeniusovih števil.

V prvem poglavju tega dela bomo definirali in na primerih predstavili vse zgornje probleme, razen posebnega problema razmene denarja, s katerim se bomo ukvarjali v drugem poglavju. Na koncu bomo še dokazali Frobeniusovo formulo in pa Sylvestrov izrek, saj bomo oba v nadaljevanju še potrebovali.

V drugem poglavju bomo najprej definirali posebni problem razmene denarja, ga ponazorili na primeru in nato še dokazali lemo, ki nam bo pomagala v nadaljevanju.

Drugo poglavje je naprej razdeljeno še na dva razdelka, pri katerih se bomo ukvarjali le še z dvemi konkretnimi primeri posebnega problema razmene denarja. V prvem razdelku bomo dokazali trditev, ki nam bo dala globalno rešitev tega problema v primeru dveh kovancev. V drugem razdelku pa bomo najprej dokazali še dve trditvi, ki nam med drugim tudi data konkretni metodi za preverjanje ustreznosti rešitev v primeru treh kovancev. Na koncu pa bomo, kot posledico teh dveh trditev, dokazali še zadnji in pa najpomembnejši rezultat tega dela – izrek, ki nam bo dal najpreprostejšo računsko metodo za preverjanje ustreznosti rešitev. Vse rezultate bomo seveda tudi ponazorili na primerih.

2. Preprosti problem nahrbtnika in njegove variacije

V tem poglavju si bomo ogledali preprosti problem nahrbtnika in nekaj njegovih najbolj znanih (oz. za nas najbolj relevantnih) variacij. Vsako imed njih bomo definirali in ponazorili na enostavnem primeru. Na koncu poglavja bomo navedli ter dokazali še nekaj trditev in izrekov, ki se navezujejo na določene variacije tega

(5)

problema. Rezultati v tem poglavju so povzeti po [4], [6] in [7], razen na mestih, kjer je posebej označeno drugače. Začnimo sedaj z naslednjim primerom.

Primer 2.1. Recimo, da imamo neskončno zalogo predmetovA, B, C in D, ki imajo vsak svojo vrednost in prostornino:

• A= (9 $, 4l),

• B = (4 $, 2l),

• C = (4 $,3 l),

• D= (3 $, 2l).

Zanima nas, katere in pa koliko primerkov posameznih predmetov moramo vzeti, da bo v nahrbtniku s prostornino 11 l, kamor predmete pospravljamo, vsota njihovih vrednosti največja možna. Najprej vzamemo po dva primerka predmeta A, saj ima ta navišje razmerje med vrednostjo in prostornino, hkrati pa je v nahrbtniku dovolj prostora kvečjemu za dva primerka tega predmeta, zato vzamemo toliko primerkov kolikor se da – torej dva. Nato pa ostane v nahrbtniku prostora le še za natanko en predmet izmed preostalih treh, zato gotovo ne vzamemo predmeta D, saj ima ta izmed preostalih predmetov najmanjšo vrednost. Vseeno pa je ali vzamemo po en primerek predmeta B ali pa po en primerek predmeta C, saj imata oba enako vrednost. Rešitvi sta torej dve, največja skupna vrednost predmetov, ki jih lahko pospravimo v nahrbtnik, pa je 22$. Ni pa pomembno, če v nahrbtniku ostane še kaj odvečnega prostora (ki ga ne moremo porabiti) ali ne. Važno je le, da skupna prostornina predmetov v nahrbtniku ni večja od 11l, vsota njihovih vrednosti pa je največja možna (torej 22$), hkrati pa v nahrbtniku ni več prostora za noben

predmet. ♢

Problem je bil torej v tem, da v nahrbtnik z določeno prostornino (načeloma končno, v nekaterih variacijah problema pa lahko imamo tudi neskončno) pospravljamo predmete z različnimi vrednostmi in različnimi prostorninami. Zanima nas, katere in pa koliko primerkov posameznih predmetov moramo pospraviti v nahrbtnik, da bo vsota vrednosti vseh predmetov v njem največja možna. Matematično lahko ta problem formuliramo z naslednjo definicijo.

Definicija 2.2 (Preprosti problem nahrbtnika). Imamo neskončno zalogo predmetov z vrednostmi a₁, a₂, . . . , a_t ∈Nin s pripadajočimi prostorninami v₁, v₂, . . . , v_t∈ N. Predmete pospravljamo v nahrbtnik s prostornino V. Naj bo množica S₁ definirana kot

S₁ ={a₁c₁+a₂c₂+· · ·+a_tc_t ∈N⁰ |v₁c₁+v₂c₂ +· · ·+v_tc_t≤V; c₁, c₂, . . . , c_t∈N⁰}.

Iščemo največji element množice S₁ (maxS₁) oziroma koeficiente c₁, c₂, . . . , c_t njegove faktorizacije na vrednosti a₁, a₂, . . . , a_t. Očitno je množica S₁ za vsako izbiro predmetov z vrednostmi a₁, a₂, . . . , a_t in pripadajočimi prostorninami v₁, v₂, . . . , v_t končna, zato maksimum zmeraj obstaja.

Če v preprostemu problemu nahrbtnika vzamemo predmete vse s prostorninami enakimi 1 – torej, da jev_i = 1za vsaki∈ {1,2, . . . t}, je vprašanje o največji skupni vrednosti predmetov, ki jih lahko pospravimo v nahrbtnik, trivialno. Zato lahko z drugačnim vprašanjem pridemo do prve izmed dveh najbolj znanih variacij preprostega problema nahrbtnika – problema poštnih znamk. Oglejmo si torej naslednji primer.

(6)

Primer 2.3. Recimo, da imamo neskončno zalogo poštnih znamk enakih velikosti, z vrednostmi 1c, 4c, 7 c in 15c. Na ovojnici, na katero jih želimo prilepiti, je prostora za največ tri znamke. Zanima nas, katera je najmanjša vsota vrednosti poštnih znamk, ki jo ne moremo prilepiti na ovojnico. Odgovor je 10c, saj se očitno vse vsote vrednosti od 1 c do9c da dobiti s seštevanjem do treh znamk z zgornjimi

vrednostmi. ♢

Problem je bil torej v tem, da na ovojnico lepimo poštne znamke različnih vrednosti, med katerimi je ena od vrednosti nujno enaka 1 (to iz primera sicer ni bilo očitno, vendar je to zahteva, ki smo jo dodali, saj bi odgovor v nasprotnem primeru zmeraj bil enak 1). Prav tako pa je na ovojnici prostora le za končno mnogo znamk.

Zanima nas torej, katera je najmanjša vsota vrednosti poštnih znamk, ki jo na ovojnico ne moremo prilepiti. Matematično lahko ta problem formuliramo z naslednjo definicijo.

Definicija 2.4 (Problem poštnih znamk). Imamo neskončno zalogo poštnih znamk enakih velikosti, z vrednostmi a₁, a₂, . . . , a_t∈ N, za katere dodatno velja: 1 = a₁ <

a₂ <· · ·< a_t. Želimo jih prilepiti na ovojnico, na kateri je prostora za največh∈N znamk. Naj bo množica S₂ definirana kot

S₂ ={a₁c₁+a₂c₂+· · ·+a_tc_t∈N0 |c₁ +c₂+· · ·+c_t≤h;c₁, c₂, . . . , c_t∈N0}.

Iščemo najmanjši element množice N\S₂ (min N\S₂). Ta seveda obstaja, saj je množica Nnavzdol omejena ter ima tako najmanjši element (in sicer 1), množicaS₂ (katere elemente odštejemo od množice N) pa je očitno, za vsako izbiro elementov z vrednostmi a₁, a₂, . . . , a_t, končna.

Če pa zdaj pri preprostem problemu nahrbtnika ponovno vzamemo vse predmete s prostorninami enakimi 1 – torej, da je v_i = 1 za vsak i∈ {1,2, . . . , t}, dodatno pa je še prostornina nahrbtnika neskončna, je vprašanje o največji vrednosti tokrat celo nesmiselno. Lahko pa z drugačnim vprašanjem pridemo še do druge od dveh najbolj znanih variacij tega problema – klasičnega problema razmene denarja. Poglejmo si torej naslednji primer.

Primer 2.5. Imamo neskončno količino kovancev po 4 c, 5c in 7 c. Katere so vse vsote denarja, ki jih lahko razmenjamo s kovanci teh treh vrednosti? Izkaže se, da je odgovor vse vsote denarja, razen 1 c,2 c,3 c in 6 c. Namreč, z enim kovancem po 7 c in skkovanci po4 c, lahko razmenjamo vsako vsoto denarja oblike1·7 c+k·4 c= (7 + 4k)c. S k+ 2 kovanci po 4 c, lahko razmenjamo vsako vsoto denarja oblike (k+ 2)·4 c= (8 + 4k)c. Z enim kovancem po 5 c in s k+ 1kovanci po 4c, lahko razmenjamo vsako vsoto denarja oblike 1·5 c+ (k+ 1)·4 c= (9 + 4k) c. In z dvema kovancema po 5 c ter s k kovanci po 4 c, lahko razmenjamo vsako vsoto denarja oblike 2·5 c+k·4 c = (10 + 4k)c. Torej lahko res s kovanci teh treh vrednosti razmenjamo vsako vsoto denarja večjo od 6 c, med vsotami denarja, ki so manjše ali enake 6 c, pa očitno lahko razmenjamo le 4 c in 5c, seveda z uporabo enega

kovanca dotične vrednosti. ♢

Problem je bil torej v tem, da imamo kovance različnih vrednosti, zanima pa nas, katere vse vsote denarja lahko tvorimo s kovanci teh vrednosti oz. z drugimi bese- dami, katere so vse vsote denarja, ki jih lahko razmenjamo s kovanci teh vrednosti.

Matematično lahko ta problem formuliramo z naslednjo definicijo.

(7)

Definicija 2.6 (Klasični problem razmene denarja). Imamo neskončno količino kovancev z vrednostmi a₁, a₂, . . . , a_t∈N. Naj bo množica S definirana kot

S ={a₁c₁+a₂c₂+· · ·+a_tc_t∈N0 |c₁, c₂, . . . , c_t∈N0}.

(1)

Zanima nas, katere vsote denarja s ∈ N⁰ se da razmenjati s kovanci teh vrednosti.

Torej iščemo elemente množice S. Ta množica je seveda neskončna, imenovali pa bi jo lahko tudi množica vseh linearnih kombinacij vrednosti a₁, a₂, . . . , a_t ∈ N v množici naravnih števil N0 vključno z 0.

Naj bo od zdaj naprej za poljubne vrednosti kovancev a₁, a₂, . . . , a_t∈N množica S zmeraj kot v (1), za te vrednosti pa bosta od zdaj naprej vedno dodatno veljali še dve predpostavki:

0< a₁ < a₂ <· · ·< a_t in gcd(a₁, a₂, . . . , a_t) = 1, (2)

kjer funkcija gcd poda največji skupni delitelj števil a₁, a₂, . . . , a_t. Iz teh dveh po- gojev sledi naslednji izrek.

Izrek 2.7 (Schurov izrek). Naj za vrednosti kovanceva₁, a₂, . . . , a_t ∈Nveljata zgor- nji dve predpostavki. Potem obstaja neka vsota denarja s₀ ∈N∪ {−1}, tako da za vsako vsoto denarja s∈N0, za katero velja s > s₀, sledi s ∈S.

Dokaz izreka lahko najdemo v [3, Theorem 3.15.2 (Schur’s theorem)]. V tem delu ga bomo izpustili, saj zahteva vpeljavo mnogih pojmov, ki niso na noben drug način povezani z našo temo.

Če v klasičnem problemu denarja vzamemo le kovance z vrednostmi, ki zadoščajo predpostavkama (2), potem po Schurovem izreku (izrek 2.7) vemo, da obstaja neka vsota denarja, za katero velja, da se vsaka vsota denarja večja od nje da razmenjati s kovanci teh vrednosti. Zato nas zanima, katera je najmanjša taka vsota denarja in kako jo najti. Na ta način pridemo do najbolj znane variacije klasičnega problema denarja – problema kovancev. Matematično lahko ta problem formuliramo z naslednjo definicijo.

Definicija 2.8 (Problem kovancev). Imamo neskončno količino kovancev z vrednostmia₁, a₂, . . . , a_t ∈N, ki ustrezajo pogoju (2). Po Schurovem izreku (izrek 2.7) vemo, da obstaja taka vsota denarja s₀ ∈ N∪ {−1}, da za vsako vsoto denarja s ∈N0, za katero velja s > s₀ sledi s ∈ S. Iščemo funkcijo g :=g(a₁, a₂, . . . , a_t), ki nam da najmanjši tak s0, za vrednosti kovanceva1, a2, . . . , at.

Opomba 2.9. Funkcijo g imenujemo Frobeniusova funkcija, vrednost, ki jo poda, pa Frobeniusovo število (oboje za vrednosti kovancev a₁, a₂, . . . , a_t).

Primer, ko jet = 1, je trivialen, za primere, ko jet≥3, pa še ne poznamo nobene Frobeniusove funkcije, obstajajo le določene zgornje in spodnje meje za Frobeniusova števila za vrednosti kovancev a₁, a₂, . . . , a_t.

Primer, ko je t = 2, pa se imenuje Frobeniusov problem (kovancev) in zanj Fro- beniusovo funkcijo poznamo – njeno definicijo imenujemo Frobeniusova formula.

Formulirajmo in pa dokažimo sedaj naslednji izrek, ki podaja to formulo, hkrati pa še eno njeno dodatno lastnost.

Izrek 2.10 (Frobeniusova formula in Sylvestrov izrek). Če imamo neskončno koli- čino kovancev z vrednostma a₁, a₂ ∈ N, ki ustrezata pogoju (2), potem je največja vsota denarja, ki je ne moremo razmenjati s kovanci teh dveh vrednosti, enaka

g(a1, a2) = a1a2−a1−a2.

(8)

Dodatno pa za vsako vsoto denarja s ∈ N0, za katero je s ≤ g(a₁, a₂), velja, da lahko s kovanci teh dveh vrednosti razmenjamo natanko eno izmed vsot denarja s in g(a₁, a₂)−s.

Opomba 2.11. V resnici je Sylvester dokazal le t. i. Sylvestrovo lemo, ki pravi, da je med vsotami denarja s ∈ N⁰, za katere je s ≤ g(a₁, a₂), natanko polovica takih, ki se jih s kovanci teh dveh vrednosti da razmenjati, in natanko polovica takih, ki se jih s kovanci teh dveh vrednosti ne da razmenjati. Zadnji del prejšnjega izreka – Sylvestrov izrek – torej podaja še natančnejšo klasifikacija za te vsote denarja kot jo podaja Sylvestrova lema, za katero pa se izkaže, da dejansko niti ni potrebna pri dokazu Sylvestrovega izreka. V resnici je Sylvestrova lema le trivialna posledica Sylvestrovega izreka, zato je ni niti potrebno dokazovati. Je pa izrek, ki ga Sylvester sicer niti ni poznal, kaj šele, da bi ga dokazal, zaradi zgodovinskih razlogov kljub temu pripisan njemu.

Opomba 2.12. Po Sylvestrovi lemi bi torej moralo biti med vsotami denarjas∈N0, za katere je s ≤g(a₁, a₂), zmeraj sodo mnogo teh vsot, ne glede na izbiro vrednosti kovanceva₁ina₂. Izkaže se, da je to res, če med te vsote prištevamo še vsoto denarja 0. Frobeniusovo število g(a₁, a₂) =a₁a₂−a₁−a₂ je namreč zmeraj liho število.

Dokaz opombe 2.12. Ker je gcd(a1, a2) = 1, sta torej vrednosti a1 in a2 bodisi obe lihi, bodisi je ena soda in ena liha. V prvem primeru je toreja₁ = 2k−1ina₂ = 2l−1, za neka k, l∈N. Torej je

g(a1, a2) =g(2k−1,2l−1)

= (2k−1)(2l−1)−(2k−1)−(2l−1)

= 4kl−2k−2l+ 1−2k+ 1−2l+ 1

= 4kl−4k−4l+ 3

= 4(kl−k−l) + 3,

kar je očitno liho število. V drugem primeru pa je, brez škode za splošnost, a1 = 2k in a2 = 2l−1, za nekak, l ∈N. Torej je

g(a₁, a₂) =g(2k,2l−1)

= 2k(2l−1)−2k−(2l−1)

= 4kl−2k−2k−2l+ 1

= 4kl−4k−2l+ 1

= 2(2kl−2k−l) + 1,

kar je prav tako liho število. □

Dokaz Frobeniusove formule je povzet po [8] ter po rezlutatih iz [5]. Frobeniusovo formulo pa lahko dokažemo tudi na geometričen način – primer tega je [2]. Dokažimo sedaj prejšnji izrek.

Dokaz izreka 2.10. Najprej dokažimo veljavnost Frobeniusove formule. Dokazati moramo, da se vsako vsoto denarja s∈N0, za katero velja

s > a₁a₂−a₁−a₂, s ≥a₁a₂−a₁−a₂ + 1

= (a1−1)(a2−1),

(9)

da razmenjati s kovanci z vrednostma a₁, a₂ ∈N, ki ustrezata pogoju (2). Torej, da velja s=xa₁+ya₂, za neka x, y ∈N0, oziroma, da iz s≥(a₁−1)(a₂−1) sledi, da je s ∈S.

Vzemimo sedaj neko poljubno vsoto denarja s ∈ N0, za katero velja s ≥ (a₁ − 1)(a₂−1). Ker sta po (2) vrednosti kovanceva₁, a₂ tuji si števili, sledi, da obstajata nekax₀, y₀ ∈Z, za katera velja1 =x₀a₁+y₀a₂. Če to enačbo sedaj na obeh straneh pomnožimo s s, dobimo

s=sx₀a₁+sy₀a₂ =x₁a₁+y₁a₂, kjer sta x₁(=sx₀), y₁(=sy₀)∈Z.

Naj bo zdaj x = x1 −ta2 in y = y1 +ta1, kjer je t ∈ Z parameter. S kratkim računom vidimo, da velja

xa1+ya2 = (x1−ta2)a1+ (y1+ta1)a2

=x₁a₁−ta₂a₁+y₁a₂+ta₁a₂

=x₁a₁+y₁a₂

=s,

za vsak t ∈ Z. Naj bo t₀ najmanjši tak t, za katerega je še zmeraj y ≥ 0. Torej t₀ = min{t ∈ Z | y = y₁ +ta₁ ≥ 0}. Torej je y₂ = y₁+t₀a₁ ≥ 0. Pokažimo, da je potem v tem primeru tudi x₂ =x₁−t₀a₂ ≥0.

S protislovjem najprej pokažimo, da je y₂ < a₁. Pa recimo, da to ni res in da je y₂ ≥a₁. Iz tega potem sledi

y₁+t₀a₁ ≥a₁, y₁+t₀a₁−a₁ ≥0, y₁ + (t₀−1)a₁ ≥0.

To pa je protislovje, saj smo predpostavili, da je t₀ najmanjši tak t, za katerega je y₁+ta₁ ≥0. Torej je res y₂ < a₁ oziroma

y₂ ≤a₁−1,

−y₂ ≥ −(a₁−1).

Iz zgornjih enakosti, neenakosti in predpostavk pa zdaj sledi s ≥(a₁−1)(a₂−1),

x₂a₁+y₂a₂ ≥(a₁−1)(a₂−1), x2a1 ≥(a1−1)(a2−1)−y2a2

≥(a₁−1)(a₂−1)−(a₁−1)a₂

= (a₁−1)(a₂−1−a₂)

= (a₁−1)(−1)

=−a₁+ 1, to pa nam da

x₂a₁ >−a₁, x₂ >−1, x2 ≥0,

(10)

kar smo želeli pokazati. Našli smo torej nekax₂, y₂ ∈N0, za katera jes=x₂a₁+y₂a₂. Vsota denarja s se torej res da razmenjati s kovanci z vrednostma a₁ in a₂.

Zdaj smo dokazali, da je g(a₁, a₂) = a₁a₂−a₁−a₂ taka vsota denarja, ki ustreza pogojem Schurovega izreka (izrek 2.7). Moramo pa dokazati še, da je to najmanjša taka vsota denarja – torej, da se vsota denarja g(a₁, a₂) =a₁a₂−a₁−a₂ več ne da razmenjati s kovanci z vrednostma a₁ ina₂. To bomo storili tako, da bomo najprej dokazali še drugi del našega izreka – t. i. Sylvestrov izrek, ki pravi, da se za vsako vsoto denarja s ∈ N⁰, za katero velja s ≤ g(a1, a2), s kovanci teh dveh vrednosti da razmenjati natanko ena izmed vsot denarja s ing(a₁, a₂)−s. Iz tega bo potem sledilo tudi to, da, ker se vsoto denarja 0 vedno da razmenjati s kovanci poljubnih dveh vrednosti (in sicer kot 0 = 0·a₁ + 0·a₂), se zato, za poljubni taki vrednosti kovancev, vsote denarjag(a₁, a₂) =g(a₁, a₂)−0ne da razmenjati. S tem pa bo tudi prvi del našega izreka – Frobeniusova formula – dokončno dokazana in tako tudi celoten izrek. Dokažimo torej zdaj še Sylvestrov izrek.

Če je ena izmed dveh vrednosti kovancev enaka 1, po pogoju (2) mora to biti a₁, je potem g(1, a₂) = 1·a₂ −1−a₂ = −1, torej se vsako vsoto denarja s ∈ N0

da razmenjati s kovanci teh dveh vrednosti. Zato lahko brez škode za splošnost predpostavimo, da sta a₁, a₂ ∈ N\{1} in je posledično g(a₁, a₂) ∈ N. Naj torej za neko vsoto denarja s ∈ N0 velja s ≤ g(a₁, a₂) = a₁a₂ −a₁ −a₂ in naj bo izjava A= (∃x, y ∈N0 :s=xa₁+ya₂)ter izjavaB = (∃x, y ∈N0 : (a₁a₂−a₁−a₂)−s= xa1 +ya2). Dokazati moramo, da pri teh pogojih za vsoto denarja s zmeraj velja bodisi A bodisi B, nikdar pa ne oba hkrati ali pa nobeden izmed niju. Govorimo torej o logičnem vezniku ekskluzivni ali (⊕). Pokažimo najprej s pomočjo logične tabele, da je dokazovanje izjaveA⊕B ekvivalentno dokazovanju izjaveA ⇐⇒ ¬B.

A B ¬B A ⇐⇒ B A ⇐⇒ ¬B A⊕B

1 1 0 1 0 0

1 0 1 0 1 1

0 1 0 0 1 1

0 0 1 1 0 0

Torej moramo res dokazati ekvivalenco A ⇐⇒ ¬B.

( =⇒ ) Recimo, da velja izjava A, torej, da se vsoto denarja s da razmenjati s kovanci z vrednostma a₁ in a₂, oziroma da je s =x₁a₁+y₁a₂ za neka x₁, y₁ ∈ N0. Dokažimo sedaj, da potem ne velja izjavaB, oziroma, da velja izjava¬B. Torej, da se vsote denarja (a₁a₂−a₁−a₂)−sne da razmenjati s kovanci teh dveh vrednosti, oziroma, da ∄x, y ∈ N0 : (a₁a₂ −a₁ −a₂)−s = xa₁ +ya₂. Pa recimo, da to ni res in da ne velja izjava ¬B, oziroma, da velja izjavaB. Torej, da se vsoto denarja (a1a2 −a1 −a2)−s da razmenjati s kovanci teh dveh vrednosti, oziroma, da je (a1a2 −a1 −a2) −s = x2a1 +y2a2, za neka x2, y2 ∈ N⁰. Poskusimo sedaj priti v protislovje s to predpostavko. Če nam to uspe, smo implikacijo v desno stran dokazali.

Iz zgornjih predpostavk sledi, da je

a₁a₂ =x₂a₁+y₂a₂+a₁+a₂+s

= (x₂+ 1)a₁+ (y₂+ 1)a₂ +x₁a₁ +y₁a₂

= (x₁+x₂+ 1)a₁ + (y₁+y₂+ 1)a₂.

Iz te enakosti in iz pogoja (2), sledi, da a₁|(y₁+y₂+ 1) ina₂|(x₁+x₂+ 1). Torej je y1 +y2 + 1 =a1k1 in x1 +x2 + 1 = a2k2 za neka k1, k2 ∈ N. Števili k1 in k2 sta

(11)

torej pozitivni, to pa zato, ker so koeficienti x₁, x₂, y₁, y₂ ∈N0 in je tako a₁k₁ =y₁+y₂+ 1≥0 + 0 + 1 = 1,

a2k2 =x1+x2 + 1≥0 + 0 + 1 = 1.

Ker pa sta tudi a₁, a₂ ∈N, potem skupaj s tema dvema enakostma in pa iz prejšnje enačbe sledi

a₁a₂ = (a₂k₂)a₁+ (a₁k₁)a₂

= (k₁+k₂)a₁a₂, 1 =k1+k2

≥1 + 1

= 2,

kar pa je protislovje. Torej smo implikacijo v desno stran dokazali.

( ⇐= ) Implikacijo ¬B =⇒ A lahko zapišemo tudi v njeni ekvivalentni obliki

¬A =⇒ ¬(¬B) oziroma ¬A =⇒ B. Predpostavimo torej, da ne velja izjava A, oziroma da velja izjava ¬A. Torej da se vsote denarja s ne da razmenjati s kovanci z vrednostma a₁ ina₂, oziroma da ∄x, y ∈N0 :s =xa₁+ya₂. Dokažimo sedaj, da potem velja izjava B, torej da se vsoto denarja (a₁a₂−a₁−a₂)−s da razmenjati s kovanci teh dveh vrednosti, oziroma da je (a₁a₂ −a₁ −a₂)−s = x₂a₁ +y₂a₂ za neka x2, y2 ∈N⁰.

Vsota denarja s+ (a1a2−a1−a2) >(a1a2−a1−a2), saj je s ∈ N⁰ in je hkrati s ̸= 0, saj bi v nasprotnem primeru ne veljala izjava ¬A, oziroma bi veljala izjava A, ker bi bil s = 0 = 0·a₁+ 0·a₂ in bi se tako vsota denarja s dala razmenjati s kovanci z vrednostma a₁ in a₂. Zato po Schurovem izreku (izrek 2.7), katerega veljavnost smo za vsoto denarja a₁a₂ −a₁ −a₂ dokazali zgoraj, velja, da se vsoto denarja s+ (a₁a₂−a₁−a₂)da razmenjati s kovanci z vrednostma a₁ ina₂, torej da je s+ (a₁a₂−a₁−a₂) = x₁a₁+y₁a₁ za nekax₁, y₁ ∈N0. To enakost lahko zapišemo še na tri ekvivalentne načine kot

s=x₁a₁+y₁a₂+a₁+a₂−a₁a₂

= (x₁+ 1−a₂)a₁+ (y₁+ 1)a₂

= (x₁+ 1)a₁+ (y₁ + 1−a₁)a₂. Iz prve enačbe sledi

(a₁a₂−a₁−a₂)−s =a₁a₂−a₁−a₂−((x₁+ 1)a₁ + (y₁+ 1)a₂−a₁a₂)

=a₁a₂−a₁−a₂−(x₁+ 1)a₁−(y₁+ 1)a₂+a₁a₂

= (a₂−x₁−2)a₁+ (a₁−y₁ −2)a₂

=x₂a₁+y₂a₂.

Vsoto denarja(a₁a₂−a₁−a₂)−ssmo torej zapisali kot linearno kombinacijo vrednosti kovancev a₁ in a₂. Pokazati moramo torej le še to, da sta pripadajoča koeficienta x₂(= a₂−x₁−2), y₂(= a₁−y₁−2)∈N0.

Ker sta x₁, y₁ ∈N0, sledi, da je

x₁+ 1≥0 + 1 = 1≥0, y₁+ 1≥0 + 1 = 1≥0.

Torej po začetni predpostavki in pa preostalih dveh enačbah zgoraj sledi, da ker smo vsoto denarja s na dva različna načina zapisali kot linearno kombinacijo vrednosti

(12)

kovanceva₁ ina₂, kjer je pri obeh enačbah eden od koeficientov iz množiceN0, mora biti pri obeh enačbah zato drugi od koeficientov iz množice Z\N0. Torej iz prve od teh dveh enačb sledi

x₁ + 1−a₂ <0,

−(x₁+ 1−a₂)>0,

−(x1+ 1−a2)−1>0−1, a₂−x₁−2>−1, a₂−x₁−2≥0,

x₂ ≥0.

Iz druge od teh dveh enačb pa sledi

y1+ 1−a1 <0,

−(y₁+ 1−a₁)>0,

−(y₁+ 1−a₁)−1>0−1, a₁−y₁−2>−1, a₁−y₁−2≥0,

y₂ ≥0.

Torej sta oba koeficienta x₂ iny₂ res iz množiceN0, kar pomeni, da se vsoto denarja (a1a2−a1−a2)−s res da razmenjati s kovanci z vrednostma a1 in a2 oziroma je (a1a2−a1 −a2)−s =x2a1+y2a2, kjer sta x2, y2 ∈ N⁰. S tem pa smo dokazali še implikacijo v levo stran in tako Sylvestrov izrek, kot posledico pa še Frobeniusovo

formulo in zato celoten izrek. □

Ponazorimo sedaj Frobeniusovo formulo in pa Sylvestrov izrek na naslednjem zgledu.

Zgled 2.13. Do leta 1994 je v ameriškem nogometu veljalo pravilo, da ekipa lahko doseže točke zgolj na dva načina – ali po3z dosegom t. i.goala, ali pa po7z dosegom t. i. touchdowna. Kateri je bil največji točkovni izkupiček, ki ga ena ekipa ni mogla doseči? Odgovor je seveda g(3,7) = 3·7−3−7 = 11. Med točkovnimi izkupički manjšimi od 11, pa se je očitno dalo doseči3 (= 1·3), 6 (= 2·3),7 (= 1·7), 9 (= 3·3) in10 (= 1·3+1·7). Posledično pa se ni dalo doseči le1 (= 11−10), 2 (= 11−9), 4 (=

11−7), 5 (= 11−6)in 8 (= 11−3). ♢

3. Posebni problem razmene denarja

To poglavje je namenjeno glavnemu problemu tega dela – posebnemu problemu razmene denarja. Najprej bomo s pomočjo vpeljave nekaterih novih pojmov prišli do te konkretne variacije klasičnega problema razmene denarja, nato pa bomo v naslednjih dveh podpoglavjih rešili ta problem v dveh konkretnih primerih. Celotno poglavje je povzeto po [1].

Pa recimo, da imamo neskončno količino kovancev z vrednostmia₁, a₂, . . . , a_t∈N, ki ustrezajo pogoju (2) in naj bo s ∈ N0 neka vsota denarja. Vpeljimo sedaj dva nova pojma, ki ju bomo pogosto uporabljali v nadaljevanju.

Definicija 3.1. Naj bo d := d(s;a₁, a₂, . . . , a_t) funkcija, ki podaja število vseh različnih načinov, na katere lahko vsoto denarjasrazmenjamo s kovanci z vrednostmi

(13)

a₁, a₂, . . . , a_t. Vrednost, ki jo ta funkcija poda, imenujemototalna razmena za vsoto denarja s.

Definicija 3.2. Vsaka razmena vsote denarjas, s kovanci z vrednostmia₁, a₂, . . . , a_t, pri kateri uporabimo najmanjše možno skupno število teh kovancev, se imenuje optimalna razmena za vsoto denarja s.

Opomba 3.3. Če se vsota denarjasne da razmenjati s kovanci teh vrednosti (torej s /∈ S), potem je njena totalna razmena enaka 0. O optimalni razmeni pa v tem primeru nima smisla govoriti. Če pa se vsoto denarja s da razmenjati s kovanci teh vrednosti (torej s ∈ S), potem pa je očitno totalna razmena neko končno število, zato pa je tudi optimalna razmena v tem primeru dobro definirana, saj je med vsemi razmenami, ki jih je končno mnogo, zmeraj vsaj ena taka (lahko pa tudi več), ki uporabi najmanjše možno število kovancev.

Oglejmo si sedaj naslednji primer, kjer bomo ta dva pojma uporabili tudi v praksi.

Primer 3.4. Imamo neskončno količino kovancev po 4 c, 5c in 7 c. Zanima nas, kateri so vsi načini, na katere lahko kovance s temi vrednostmi razmenjamo za 34c.

• 6·4c+ 2·5 c= 34 c. Skupaj uporabimo 8 kovancev.

• 3·4c+ 3·5 c+ 1·7 c= 34 c. Skupaj uporabimo 7 kovancev.

• 2·4c+ 1·5 c+ 3·7 c= 34 c. Skupaj uporabimo 6 kovancev.

Zlahka se prepričamo, da drugih načinov ni. Totalna razmena za 34c je torej enaka d(34; 4,5,7) = 6. Optimalni razmeni za 34c pa sta dve in sicer zadnji dve, pri

katerih uporabimo skupaj le 6kovancev. ♢

Podobno kot pri klasičnem problemu razmene denarja smo tukaj imeli kovance z različnimi vrednostmi, ki smo jih skušali razmenjati za neko vsoto denarja. Pri tej konkretni vsoti denarja, ki se jo je s kovanci teh vrednosti dalo razmenjati, pa nas je zanimalo dodatno še, na koliko različnih načinov se to vsoto denarja da razmenjati. Ker namreč za vsako vsoto denarja, ki se jo da razmenjati, obstaja vsaj ena optimalna razmena (če je razmena nasploh ena sama je ta tudi optimalna), se lahko vprašamo, ali je optimalna razmena za to vsoto denarja ena sama ali jih je morda več. Če pa isto vprašanje postavimo za vse vsote denarja, ki se jih da razmenjati, pridemo do zadnje variacije klasičnega problema razmene denarja (in s tem tudi variacije preprostega problema nahrbtnika), s katero se bomo v tem delu ukvarjali – posebnega problema razmene denarja. Matematično lahko ta problem formuliramo z naslednjo definicijo.

Definicija 3.5 (Posebni problem razmene denarja). Imamo neskončno količino kovancev z vrednostmi a₁, a₂, . . . , a_t ∈ N, ki ustrezajo pogoju (2). Zanima nas, ali za te vrednosti kovancev obstaja natanko ena optimalna razmena za vsako vsoto denarja s, ki se jo s kovanci teh vrednosti da razmenjati. Torej, ali za vsak s ∈ S obstaja natanko ena optimalna razmena.

Preden si ta problem ogledamo za konkretne vrednosti t, navedimo in dokažimo še naslednjo lemo, ki pravi, da je število optimalnih razmen za neke konkretne vrednosti kovancev omejeno globalno za vse vsote denarja, ki se jih s temi kovanci da razmenjati.

(14)

Lema 3.6. Če imamo neskončno količino kovancev z vrednostmi a₁, a₂, . . . , a_t ∈N, ki ustrezajo pogoju (2), potem obstaja neko najmanjše številoN ∈N, za katerega velja, da za vsako vsoto denarja s∈S, katero se da razmenjati s kovanci teh vrednosti, obstaja največ N različnih optimalnih razmen.

Dokaz. Naj bo s ∈ N0 neka vsota denarja, ki se jo da razmejati s kovanci z vrednostmi a₁, a₂, . . . , a_t (torej je s∈S). Med vsemi optimalnimi razmenami za vsoto denarja s (po opombi 3.3 je teh končno mnogo), obstaja taka, pri kateri uporabimo najmanj kovancev z vrednostjo a_t (če je optimalna razmena ena sama, je seveda ta tista, pri kateri uporabimo najmanj kovancev z vrednostjo at). Naj bo c to število kovancev z vrednostjo at (c je lahko tudi enak 0), uporabljenih pri tej optimalni razmeni. Ker moramo torej za vsako optimalno razmeno vsote denarja s uporabiti vsaj c kovancev z vrednostjo a_t, ima potem vsota denarja s−ca_t∈S enako število optimalnih razmen kot vsota denarjas. Pri tem za vsoto denarjas−ca_tseveda velja tudi to, da obstaja vsaj ena optimalna razmena, pri kateri ne uporabimo nobenega kovanca z vrednostjo a_t (če je c= 0, je seveda s =s−ca_t ta vsota denarja, ki ima vsaj eno optimalno razmeno, pri kateri ne uporabimo nobenih kovancev z vrednostjo a_t).

Sedaj moramo dokazati le še to, da obstaja končno mnogo takih vsot denarja u ∈ S, za katere obstaja vsaj ena optimalna razmena, pri kateri ne uporabimo nobenega kovanca z vrednostjoa_t. Namreč, če nam to uspe dokazati, potem seveda velja, da ker je takih vsot denarja končno mnogo, vsaka izmed njih pa ima po opombi 3.3 končno mnogo optimalni razmen, je med temi vsotami denarja taka, ki ima največ optimalnih razmen. Število optimalnih razmen te vsote denarja označimo z N ∈N. Ker pa ima, po razmisleku iz začetka dokaza, vsaka vsota denarja s ∈S enako število optimalnih razmen kakor neka vsota denarja, za katero obstaja vsaj ena optimalna razmena, pri kateri ne uporabimo nobenega kovanca z vrednostjo a_t, te vsote denarja pa imajo vse največ N različnih optimalnih razmen – iz tega potem sledi, da ima tudi vsaka vsota denarjas∈S največN različnih optimalnih razmen.

Dokažimo sedaj, da obstaja končno mnogo takih vsot denarja u ∈ S, za katere obstaja vsaj ena optimalna razmena, pri kateri ne uporabimo nobenega kovanca z vrednostjo a_t. Naj bou₀ ∈S neka taka vsota denarja. Za u₀ torej velja

u0 =d1a1+d2a2+· · ·+dt−1at−1,

kjer so d_i ≥0, za vse i∈ {1,2, . . . , t−1}in je d₁+d₂+· · ·+dt−1 najmanjše možno število kovancev, s katerimi lahko razmenjamo vsoto denarja u₀. S protislovjem sedaj pokažimo, da za vsak i∈ {1,2, . . . , t−1} veljad_i < a_t.

Pa recimo, da to ni res in da obstaja neki i₀ ∈ {1,2, . . . , t−1}, da jed_i₀ ≥a_t. Če vsoti denarja u₀ prištejemo in odštejemo a_i₀a_t dobimo

u0 =d1a1+d2a2+· · ·+ (di0 −at)ai0 +· · ·+dt−1at−1 +ai0at. Dobili smo torej razmeno za vsoto denarja u₀, pri kateri uporabimo

d₁+d₂+· · ·+ (d_i₀ −a_t) +· · ·+dt−1+a_i₀ =d₁+d₂+· · ·+dt−1+ (a_i₀ −a_t)

< d₁+d₂+· · ·+dt−1

kovancev, saj je i₀ ∈ {1,2, . . . , t−1} in je zato po pogoju (2) res a_i₀ − a_t < 0.

To pa je v nasprotju s predpostavko, da je d₁ +d₂ +· · ·+dt−1 najmanjše možno število kovancev, s katerimi lahko razmenjamo vsoto denarjau0. Torej je res di < at

(15)

oziroma d_i ≤a_t−1 za vsaki∈ {1,2, . . . , t−1}. Iz tega tako sledi, da je u₀ =d₁a₁ +d₂a₂+· · ·+dt−1at−1 ≤(a_t−1)(a₁+a₂+· · ·+at−1).

Taka vsota denarja u₀ je torej lahko enaka največ (a_t−1)(a₁+a₂+· · ·+at−1) in ker je bila u₀ poljubna, pomeni da je vseh takih vsot denarja končno mnogo (največ (a_t−1)(a₁+a₂+· · ·+at−1)) in s tem je lema dokazana. □ Posebni problem razmene denarja sprašuje po tem, za katere vrednosti kovancev je N iz zgornje leme (lema 3.6) enak 1. Podobno kot pri problemu kovancev je za t ≥4 ta problem še zmeraj slabo raziskan. Primer, ko je t= 1, je seveda trivialen, primera, ko pa je t ∈ {2,3}, pa sta dobro poznana in z njima se bomo ukvarjali v naslednjih dveh podpoglavjih (oz. do konca tega poglavja in s tem do konca tega dela). Oglejmo si najprej primer, ko je t= 2.

3.1. Primer, ko je t = 2. V tem primeru je v resnici rešitev tudi precej nezanimiva, saj za čisto vsaki vrednosti kovancev a1, a2 ∈ N, ki ustrezata pogoju (2), zmeraj obstaja le ena optimalna razmena, za vsako vsoto denarja, ki se jo s kovanci teh dveh vrednosti da razmenjati. Vseeno pa to trditev navedimo in dokažimo.

Trditev 3.7. Če imamo neskončno količino dveh kovancev z vrednostmaa₁, a₂ ∈N, za kateri velja a₁ < a₂, potem obstaja natanko ena optimalna razmena za vsako vsoto denarja s ∈N0, ki se jo da razmenjati s kovanci teh dveh vrednosti (torej za vsak s∈S).

Dokaz. Dokazali bomo, da za vsako vsoto denarja s ∈ N⁰, ki se jo da razmenjati s kovanci teh dveh vrednosti (torej za vsaks ∈S), velja, da ne obstajata dve različni razmeni te vsote denarja s kovanci teh dveh vrednosti, ki bi uporabili enako skupno število kovancev. Iz tega bo potem sledilo, da tudi za optimalno razmeno (tj. tisto, ki uporabi najmanjše skupno število kovancev) poljubne vsote denarjas ∈S, ne bo obstajala še ena drugačna razmena, ki bi uporabila enako skupno število kovancev.

Torej bo za vsako optimalno razmeno veljalo, da je ena sama.

Pa recimo sedaj, da zgornja predpostavka ne velja, in poskušajmo priti v protislovje. Če nam uspe, bo to pomenilo, da naša predpostavka velja, iz tega pa bo sledilo, da tudi zgornja trditev velja, kar smo pa že utemeljili. Recimo sedaj, da za neko vsoto denarja s₀ ∈S zgornja predpostavka ne velja in da obstajata dve različni razmeni te vsote denarja s₀ =x₁a₁+x₂a₂ ter s₀ =y₁a₁+y₂a₂, ki uporabita enako skupno število kovancev. Torej, da je x₁+x₂ =y₁+y₂, kjer so x₁, x₂, y₁, y₂ ∈N0.

Če je x₁ = y₁, potem je očitno tudi x₂ = y₂, kar pa je protislovje, saj smo predpostavili, da sta razmeni različni (torej, da obstaja nekii∈ {1,2}, da jexi ̸=yi).

Zato mora biti x1 ̸= y1 in brez škode za splošnost lahko predpostavimo, da je x₁ > y₁.

Če sedaj izenačimo enačbi za s₀ in enakost preuredimo, dobimo po eni strani x₁a₁+x₂a₂ =y₁a₁+y₂a₂,

x₁a₁+x₂a₂−y₁a₁ =y₂a₂, (x1 −y1)a1+x2a2 =y2a2.

(16)

Po drugi strani pa iz zgornje neenakosti x₁ > y₁, pogojaa₁ < a₂ in zgornje enakosti x₁+x₂ =y₁+y₂ sledi tudi

(x₁−y₁)a₁+x₂a₂ <(x₁−y₁)a₂ +x₂a₂

= (x₁−y₁+x₂)a₂

=y2a2.

Torej smo prišli v protislovje, kar pomeni, da naša prvotna predpostavka velja in s

tem je trditev dokazana. □

Oglejmo si zdaj še glavni vsebinski del tega dela – posebni problem razmene denarja v primeru, ko je t= 3.

3.2. Primer, ko je t = 3. V tem primeru je stvar malce bolj zapletena, kot v primeru t = 2, zato moramo najprej definirati nekaj pomožnih vrednosti, ki nam bodo pomagale v nadaljevanju pri dokazovanju trditev in izrekov, vezanih na naš problem. Začnimo torej z naslednjo definicijo.

Definicija 3.8. Definirajmo vrednostid,m inn kot d:= gcd(a₃−a₂, a₃−a₁), m:= a₃−a₂

d , n:= a₃−a₁ d . Kot opazko pripomnimo, da veljata še enakosti

a2 =a3−md in a1 =a3 −nd.

(3)

Za te tri vrednosti veljata še dve lastnosti, ki ju bomo potrebovali v nadaljevanju, zato ju na tem mestu navedimo v naslednji trditvi in dokažimo njuno veljavnost.

Trditev 3.9. Za vrednosti d, m in n veljata enakosti gcd(m, n) = 1 in gcd(a₃, d) = 1.

Najprej v naslednji trditvi podajmo še nekaj osnovnih lastnosti funkcije gcd, ki jih bomo potrebovali pri dokazovanju trditve 3.9.

Trditev 3.10. Za funkcijo gcd, definirano na množici celih števil Z, veljajo naslednje lastnosti:

(1) gcd(a, b) = gcd(b, a),

(2) gcd(a, b) = gcd(−a, b) = gcd(a,−b) = gcd(−a,−b), (3) gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(a,gcd(b, c)), (4) gcd(a, b) = gcd(a, b+na), za vsak n∈Z,

(5) (d|a)∧(d|b) =⇒ gcd(^a_d,^b_d) = ¹_dgcd(a, b).

Dokaz trditve 3.10. (1) Očitno.

(2) Številiain−aimata enake delitelje, prav tako pa tudibin−b. Torej enakosti očitno veljajo. Med drugim je seveda gcd(a,0) =a za vsak a ∈Z\{0}, medtem ko gcd(0,0) ni definiran.

(17)

(5) Naj bo e = gcd(a, b) in f = gcd(â_d,_d^b). Potem so a = ea^′ in b = eb^′, kjer je gcd(a^′, b^′) = 1, ter â_d =f a^′′ in ^b_d =f b^′′, kjer jegcd(a^′′, b^′′) = 1, za neke a^′, a^′′, b^′, b^′′ ∈ N. Ker d|a in d|b, sledi, da d|e. Torej je a=kda^′ inb =kdb^′, za neki k∈N. Ker je gcd(a^′, b^′) = 1, je torej f = gcd(â_d,^b_d) = gcd(^kda_d^′,^kdb_d^′) = gcd(ka^′, kb^′) = k. Torej

iz e=kd=f d sledi _d¹e=f. □

Sedaj lahko z uporabo zgornjih lastnosti funkcije gcd ter definicij za vrednosti d, m in n enostavno izračunamo enakosti iz trditve 3.9.

Dokaz trditve 3.9.

gcd(m, n) = gcd

(︃a₃ −a₂

d ,a₃ −a₁ d

)︃

= 1

dgcd(a₃−a₂, a₃−a₁)

= 1 dd

= 1.

Dodatno pa lahko še z uporabo pogoja (2) izračunamo tudi gcd(a₃, d) = gcd(a₃, gcd(a₃−a₂, a₃−a₁))

= gcd(gcd(a₃, a₃−a₂), a₃−a₁)

= gcd(gcd(a₃,−a₂), a₃−a₁)

= gcd(gcd(−a₂, a₃), a₃−a₁)

= gcd(−a2,gcd(a3, a3 −a1))

= gcd(−a₂,gcd(a₃,−a₁))

= gcd(−a₂,gcd(−a₁, a₃))

= gcd(gcd(−a₂,−a₁), a₃)

= gcd(gcd(−a₁,−a₂), a₃)

= gcd(gcd(a1, a2), a3)

= gcd(a₁, a₂, a₃)

= 1. □

Zdaj, ko imamo vsa potrebna orodja, pa lahko zapišemo in dokažemo prvo trditev, ki nam bo podala prvi (sicer v praksi težko izvedljiv) način preverjanja ustreznosti rešitev pri posebnemu problemu razmene denarja.

Trditev 3.11. Če imamo neskončno količino treh kovancev z vrednostmia₁, a₂, a₃ ∈ N, ki zadoščajo pogoju (2), in je vrednost n enaka kot v definiciji 3.8, potem so naslednje trditve ekvivalentne:

(1) Za vsako vsoto denarja s ∈ S, ki se jo da razmenjati s kovanci teh treh vrednosti, obstaja natanko ena optimalna razmena.

(2) Obstaja natanko ena optimalna razmena za vsoto denarja na₂ ∈S.

(3) Vsoto denarja na₂ ∈S se da razmenjati z manj kot n kovanci.

Dokaz. (1) =⇒ (2) : Očitno, saj po (1) velja, da za vsako vsoto denarja s ∈ S, ki se jo da razmenjati s kovanci teh treh vrednosti, obstaja natanko ena optimalna razmena. Torej obstaja natanko ena optimalna razmena tudi za vsoto denarjana2 ∈

(18)

S, ki pa je res element množice S, saj se jo da razmenjati vsaj na en način – z n kovanci po a₂. Torej velja (2).

(2) =⇒ (3) :Najprej se spomnimo enakosti (3) iz definicije 3.8. Če drugo enakost pomnožimo z m in jo nato preuredimo, dobimo

a1 =a3−nd, ma₁ =ma₃−mnd, mnd=ma₃−ma₁.

Če pa zdaj prvo enakost pomnožimo znter namestomndvstavimo zgornjo enakost, dobimo

a2 =a3−md, na₂ =na₃−nmd

=na₃−(ma₃−ma₁)

=na₃−ma₃+ma₁

= (n−m)a₃+ma₁.

Po definiciji 3.8 sta m = ^a³^−a_d ² in n = ^a³^−a_d ¹. Iz pogoja (2) na strani 7 očitno sledi, da je n > m, torej je n −m > 0. Prejšnji izračun nam torej da še eno razmeno za vsoto denarja na₂ ∈ S, pri kateri pa prav tako uporabimo (n− m) +m = n kovancev. Po (2), ki pravi, da obstaja natanko ena optimalna razmena, za vsoto denarjana₂ ∈S, sledi, da razmena znkovanci ne more biti optimalna, saj obstajata vsaj dve različni razmeni, ki uporabitankovancev (vsaj ti dve, ki smo ju našli). Torej mora obstajati razmena vsote denarja na2, ki uporabi manj kot n kovancev (vsaj optimalna razmena). Torej velja (3).

(3) =⇒ (1) : Implikacijo lahko zapišemo tudi v ekvivalentni obliki kot¬(1) =⇒

¬(3). Dokazati torej moramo, da če obstaja neka vsota denarja s₁ ∈S, ki se jo da razmenjati s kovanci teh treh vrednosti in ki ima vsaj dve različni optimalni razmeni, potem se vsota denarja na₂ ∈S ne da razmenjati z manj kot n kovanci oziroma je ta razmena, ki uporabi n kovancev poa₂, optimalna.

Predpostavimo zdaj, da ne velja (1)(oz. da velja¬(1)), torej da obstaja nekis₁ ∈ S, ki ima dve različni optimalni razmenis₁ =x₁a₁+x₂a₂+x₃a₃ins₁ =y₁a₁+y₂a₂+ y₃a₃, kjer za koeficiente x₁, x₂, x₃, y₁, y₂, y₃ ∈ N0 velja, da ∃i ∈ {1,2,3} : x_i ̸= y_i. Ker sta obe razmeni optimalni, pomeni, da uporabita enako število kovancev, kar nam da x1+x2+x3 =y1+y2+y3.

Če jexi =yiza nekii∈ {1,2,3}(brez škode za splošnost, naj bo toi= 1), potem iz zgornjih enakosti sledi

s₁ =x₁a₁+x₂a₂+x₃a₃ =⇒ s₁−x₁a₁ =x₂a₂+x₃a₃, s₁ =y₁a₁+y₂a₂+y₃a₃ =x₁a₁+y₂a₂+y₃a₃ =⇒ s₁−x₁a₁ =y₂a₂+y₃a₃,

x₁+x₂+x₃ =y₁+y₂+y₃ =x₁+y₂+y₃ =⇒ x₂+x₃ =y₂+y₃,

kar pomeni, da se vsota denarja s₁ −x₁a₁ da razmenjati s kovanci dveh vrednosti a₂, a₃ ∈ N, za kateri velja a₂ < a₃, na dva različna načina, pri katerih uporabimo enako skupno število kovancev. Iz trditve 3.7 v primeru t = 2 pa vemo, da to ni mogoče, torej smo prišli v protislovje. Zato za vsaki∈ {1,2,3} velja, da je x_i ̸=y_i. Brez škode za splošnost lahko sedaj predpostavimo, da za i = 1 velja x₁ > y₁. Pokažimo sedaj, da je v tem primeru tudi x3 > y3.