P R E S E K
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652 Letnik 24 (1996/1997) Številka 1 Strani 14-18
Primož Potočnik: Z MATEMATIKO NAD POŠTO
Ključne besede: matematika.
Elektronska verzija: http://www.presek.si/24/1284-Potocnik.pdf
© 1996 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
Z MATEMATIKO NAD POŠTO
Andraž, Barbara in Cene so prijatelji, ki živijo vsak na svojem koncu zemeljske oble: Andraž v Ameriki, Barbara v Belgiji in Cene na Cejlonu. Prejšnje poletje so preživeli skupaj pri nas, na zelenem koščku Evrope. Večkrat so hodili na izlete, v gostilne in po nakupih, ker pa so vsi bolj raztresene sorte, je vsakokrat vsaj eden pozabil denar doma, tako da sta mu morala druga dva denar posojati. Vse dolgove so si pridno beležili, a poravnati so jili vselej pozabili. Tako je minilo poletje in odšli so vsak na svoj konec sveta, dolgovi pa so ostali nepoplačani. Ker pa se vsi trije si ri-njajo s starim pregovorom Čisti računi - dolgo prijateljstvo, so se odločili, da svoje finančne zadeve le uredijo, in sicer s pomočjo nakazil prek pošte. A glej ga zloruka, pošta nikjer na svetu ne dela zastonj, za vsako nakazilo zaračuna delež nakazanega zneska. To je Andraža, Barbaro in Ceneta tako motilo, da so se odločiti svoje posle urediti tako, da bo pošta dobila Sini manj.
Vsak od njih je razmišljal takole: Meni je povsem vseeno, koliko denarja mi pošljeta druga dva, oziroma jima ga pošljem jaz. Želim le, da bom na koncu dobil, oziroma dal res toliko denarja, kot bi ga dal, če bi poravnal z vsakim od drugih dveh svoj pravi dolg. Če bi na primer Andraž dolgoval Barbari tisoč tolarjev, Barbara Cenetu enako vsoto in Cene Andražu spet toliko, bi bili vsi zadovoljni tudi s tem, da nihče nikomur ne bi ničesar vračal, pa še pošta pri tem ne bi nič zaslužila. Žal pa njihova situacija ni bila tako preprosta. V resnici je Andraž dolgoval Barbari 9000 tolarjev, Cene Andražu 3000 tolarjev in Barbara Cenetu 5000 tolarjev. Kako naj uredijo svoje posle, da bo zaslužek poŠte najmanjši?
Skupaj mora Andraž plačati (3000 tolarjev, Barbara mora dobili 4000 tolarjev in Cene 2000 tolarjev. Barbara, ki je imela kot hči Corcnjke in Škota največ smisla za finančna vprašanja, je predlagala:
"Andraž naj pošlje meni namesto 9000 tolarjev le 4000 tolarjev, zato pa naj plača Cenetu 2000 tolarjev, namesto da bi jih od njega dobil 3000. Pri tem bo pošta od nas dobihi le delež od 6000 tolarjev, namesto da bi
ji plačali delež od 17000 tolarjev,"
Cene je Barbarinemu občutku neskončno zaupal in ni se mu zdelo vredno tuhtati, ali lahko pošti odščipnejo še kakšen tolar, Andraž pa je bil po naravi bolj skeptičen in je iskal še druge možnosti. Po nekaj neprespanih nočeh je obupal in se odločil poiskati pomoč. Spomnil se je, da je prejšnje poletje govoril z nekim mladim bralcem Preseka, ki je takšne in podobne probleme reševal kot za Šalo. Sedel je za računalnik
in mlademu znancu prek elektronske pošte pojasnil svoje težave ter ga prosil, naj najde rešitev, ki je boljša od Barbarine, ali pa naj dokaže, da boljše ni. Ni minil teden, ko gaje čakalo pisemce:
Dragi Andraž !
Le kdaj si boš zapomnil, da ima Barbara vedno prav. Tule ti pošiljam dokaz pravilnosti njenega nasveta in hkrati še recept, kako ravnati v drugih podobnih primerih.
Imejmo tri osebe A, B in C, ki si med sabo dolgujejo določene vsote denarja. Ker je vsem trem osebam vseeno, s kom si denar izmenjajo, je v resnici pomembno vedeti le, kolikšen je seštevek dolgov in terjatev posameznih oseb, kjer so terjatve predstavljene s pozitivnimi števili, dolgovi pa z negativnimi. Te seštevke označimo z V(/\), V(B) in V(C). Ce je katera od teb količin negativna, tedaj ustrezna oseba dolguje drugima d verna več, kot pa irna do njiju terjatev. V tvojem primeru je torej
V(A) = -6000 , V(B) = 4000 , V(C) = 2000 .
Ker so si osebe posojale denar le med seboj, mora biti vsota dolgov in terjatev med njimi enaka nič. Zapisano s simboli:
-t- -f- V(C) ^ 0 .	(1)
Ta enačba nam pove, da je možno le dvoje:
i) Ena od količin V (A), V(B) in V (C), denimo V(v4), je nenegativna in
drugi dve nepozitivni;
«) Ena od količin, denimo V (A), je nepozitivna in drugi dve nenegativni.
Recept: Osebe A, B in C' bodo dale pošti najmanjši zaslužek, če bo oseba A plačala osebi B znesek V (B) in osebi C znesek V (C). Pri tem naj to, da da nekdo nekomu negativen znesek, pomeni, da od njega dobi absolutno vrednost tega zneska. Očitno se bodo po teh nakazilih na računih oseb B in C res pojavili zneski V(B) in V(C), na računu osebe A pa bo pisalo — V(B) — V(C), kar pa je zaradi enakosti (1) enako To pa oseba A tudi pričakuje.
Dokažimo, da so to za naš problem res optimalna nakazila. Denimo, da je oseba A nakazala osebi B znesek V(B) + x namesto V{B), kjer je x poljubno neničelno realno število. Tedaj je morala nakazati osebi
C znesek V(C) — x, če naj bi skupaj nakazala znesek — V (A). Ha bodo računi čisti, mora še oseba B nakazati osebi C znesek x. Ker sta števili V(B) in V (C) po predpostavki enako predznačeni, velja:
Sedaj lahko ocenimo vsoto vseh nakazil:
+ |V(C)f = | V(B) + V (C) | = |(F(SJ + x) + (V(C) - *)| < < I V(B) + x\ + 1V(CI-*l<\V(8) + *l + - «I + \4.
V oceni smo uporabili trikotniško neenakost, ki pravi, da za poljubni števili a in 6 velja |a + tj < |n| + |6|.
Zgornja ocena, prevedena v slovenščino, pove, tla je vsota vseh nakazil, ki smo jih izvedli po receptu, res manjša od vsote nakazil pri katerikoli drugačni dopustni poravnavi. S tem smo dokazali, daje Barbara svetovala prav.
Pismo mladega presekovca je Andraža pomirilo. Čez nekaj dni pa je Andraž dobil novo pošto. Spet mu je pisal njegov prijatelj, kije nadaljeval tam, kjer je v prejšnjem pismu končal. Takole je posplošil nalogo:
Denimo, da si denarja ne bi posojali le trije ljudje ampak več. Označimo število teh ljudi z n. Vsakemu paru oseb, recimo »-ti in j-ti osebi, priredimo dve števili «¿j in a3,. Če i-ta oseba dolguje j-ti, je število ciij enako temu dolgu, število rr,,; pa negativni vrednosti tega dolga. Za poljubni števili i in j velja torej enačba = —ftj,. Ker t-ta oseba sama sebi nič ne dolguje, je smiselno določiti a a 0.
Vsaki osebi pripada stanje njenih dolgov in terjatev - od vsote terjatev odštejemo vsoto dolgov - in to stanje označimo z Vi. Očitno velja
ti
Vi = na ■ j=i
Osebe razdelimo na dve skupini: na tiste z nenegatavnim stanjem (te imajo vsaj toliko terjatev kot dolgov) in na tiste z negativnim stanjem (te so zadolžene bolj kot pa imajo terjatev). Ker velja
it	TI T K	n n	n
= EH aii = ^ + an) + ¿«¡¡=0 + 0 = 0, (2)
1 = 1	t = l J = 1	1=1 J=i + 1	1 = 1
sta obe skupini neprazni, če le niso vsa stanja V; enaka nič. V slednjem primeru pač niliče nikomur ničesar ne nakaže in zaslužek pošte je ničelen. Ce pa niso vsi V; enaki nič, lahko privzamemo, da smo osebe označili tako, da stanja Vit Vi, V3,... rastejo. Pri tem naj bo prvih — 1 stanj negativnih, stanja od V^ dalje pa naj bodo nenegativna.
Recept za optimalno poravnavo dolgov se glasi:
Prva oseba naj po vrsti poravnava terjatve oseb k\, k\ + 1,..., dokler ne porabi celotnega zneska —Vi. Denimo, da se ji to zgodi pri osebi Tedaj je prvič res	Vf > | Vi [. Ko se to zgodi, nastopi oseba 2. S
svojim dolgom poplača razliko do polne terjatve osebe k2 in nato prične poravnavati terjatve oseb 4- 1, fr-j + 2,.. .. Postopek nadaljujejo, dokler niso vsi dolgovi poplačani. Zaradi formule (2) se vse lepo izide in na koncu dobi ali plača vsak toliko, kot mu gre.
Pri opisanem postopkuje vsota vseli nakazil enaka	' I I '!1 Pre-
prosto se lahko prepričamo, da pod ta znesek ne moremo, saj mora vsak, ki dolguje (ki ima V{ < 0) svoj dolg, hočeš nočeš, nekomu nakazati. Temu se ni moč izogniti. Zato je minimalna vsota nakazil res enaka vsoti vseh dolgov, kije po drugi strani enaka vsoti vseh terjatev.
Za konec še primer:
Imejmo štiri osebe A, B, C in D, Oseba A dolguje 3000 tolarjev osebi B in 2000 tolarjev osebi C. Oseba B dolguje 2000 tolarjev osebi D, oseba C pa 1000 tolarjev osebi B. Hkrati oseba D dolguje 4000 tolarjev osebi A in 1)000 tolarjev osebi C. Te podatke lahko nazorno predstavimo z matriko, kjer na presečišču ¡-te vrstice in j-tega stolpca stoji število izraženo v enotah po tisoč tolarjev:
(	0	3	2	-4 \
	—3	0	-1	2
	-2	1	0	-5
\	4	-2	5	0 J
Če seštejemo stolpce v matriki, dobimo stanja posameznih oseb. Urejena po velikosti so enaka:
Najprej nakazuje oseba D (z največjim dolgom) osebi B. Ker je njen dolg večji od terjatve osebe /?, ji nakaže poln znesek 2000 tolarjev. Osebi D ostane še 5000 tolarjev dolga in tega v celoti nakaže osebi C. Vendar oseba C še ni v celoti poplačana, oseba D pa je že poravnala ves svoj dolg. Zato priskoči na pomoč oseba A in nakaže osebi C preostanek dolga, torej 1000 tolarjev. S tem so poravnane vse terjatve in poplačani vsi dolgovi. Optimalno rešitev lahko spet predstavimo z matriko, v kateri namesto dolgov zapišemo nakazila oseb pri optimalni poravnavi:
/0 0 1 0 \
0 0 0	-2
,-100	—5 ' V 0 2 5 0 /
Ta matrika ima s prejšnjo to skupno lastnost, da ima enake vsote vrstic in stolpcev, je pa vsota absolutnih vrednosti njenih elementov precej manjša kot pri prvi. To pa odloča o dajatvah pošti.
Primož Potočnik