ISSN 0351-6652 Letnik 18 (1990/1991) Številka 4 Strani 206-210
Franc Savnik: RAZDELIVA SI VINO
Ključne besede: matematika.
Elektronska verzija: http://www.presek.si/18/1050-Savnik.pdf
© 1991 Društvo matematikov, fizikov in astronomov Slovenije © 2009 DMFA - založništvo
RAZDELIVA SI VINO
V četrti številki 14. letnika Preseka je bila pod gornjim naslovom objavljena tale starodavna naloga:
"Dva prijatelja imata osem litrov vina v osemlitrski posodi. Poleg tega
imata še petiitrsko in trilitrsko steklenico. Vino bi si rada razdelila na pol.
Kako naj samo s prelivanji med temi tremi posodami razdelita vino?"
Anekdota pravi, da je ta naloga usodno vplivala na življenjsko pot znamenitega francoskega matematika Poissona (Simeon Denis Poisson, 1781 — 1840), ki da je kot deček kazal na vseh področjih dokaj omejene sposobnosti. Ko pa je samostojno rešil nalogo o delitvi vina s pretakanjem med različno velikim? posodami, se je ogrel za matematiko in se z njo ukvarjal vse življenje.
Nalogo lahko posplošimo. Vzemimo posode A, B, C s celoštevilskimi prostorninami a, b, c, pri čemer je a sodo število in je c < b. Prva posoda naj bo polna, drugi dve prazni. Zanima nas, ali lahko vsebino posode A razpolovimo samo s pretakanjem med danimi posodami.
O Izražanju: Naši predniki so za ravnanje z vinom in z drugimi tekočinami razvili obsežno in tenkočutno izrazje, o čemer pričajo glagoli točiti, dotočiti, Iztočiti, natočiti, odtočiti, potočki, pretočiti, pri t oči t i, raztočili, s točit i- Zal med njimi ni takega, ki bi v celoti ustrezal potrebam naše naloge. Zadovoljili se bomo z zvezo "natočiti iz X v Y", ki naj pomeni "s pretakanjem iz X v Y izprazniti X ali napolniti Y".
Iz povedanega sledi, da je pred vsakim pretakanjem in po njem vsaj ena posoda polna, ali pa je ena prazna.
Trenutno razporeditev vina po posodah A, B, C opišimo z urejeno trojico celih nenegativnih števil (x, y, z), kjer je
x + y + z = a in x < a, y < b, z < c.
Začetno stanje je tedaj podano s točko (a, 0,0), rešitev naloge pa je vsaka točka, ki jo lahko dosežemo s pretakanjem in ima vsaj eno koordinato enako j. Pretakanje med posodami lahko opišemo z usmerjenimi povezavami točk. Dobimo usmerjeni graf; imenujmo ga graf naloge [a, b, c] ali kar graf
[a, b, c].
V tem članku se bomo ukvarjali izključno z nalogami, v katerih je b+c < < a. Največjo skupno mero prostornin b in c bomo označevali z d. Upoštevali bomo, da je tedaj b — b'd in c = c'd, kjer sta si števili b1 in c' tuji.
Bralcu predlagam, da za ogrevanje nariše grafa [20, 9, 6] in [28, 15, 10]
in ju primerja z grafom [8, 3,2]. Videl bo, da imajo vsi trije enako število točk in isto število povezav in da so si tudi sicer zelo podobni. Pozneje bomo videli, da sta za to "odgovorna" pogoj b + c < a in enakost razmerij b : c.
V	nalogi [20, 9, 6] lahko pretočimo naenkrat !e 3, 6 ali 9 litrov vina, v nalogi [28,15,10] pa le 5, 10 ali 15 litrov. To ni naključje; velja namreč
IZREK 1. če je b + c < a, sta prostornini vina v posodah B in C večkratnika največje skupne mere teh dveh posod.
Trditev je očitno pravilna za začetno točko (a. 0, 0). In če velja za točko {xn,yn, velja tudi za točko (x„_|_i, yn+i, zn+l). ki jo iz prejšnje dobimo z enim natakanjem. Zaradi privzetka b + c < a namreč lahko pretočimo iz poljubne posode v katero koli drugo posodo le večkratnik največje skupne mere d. Tako se veljavnost izreka prenese s točke (a, 0, 0) na vsako drugo točko grafa.
Prostornina vina v posodi A je največja v točki {a, 0,0), najmanjša pa je takrat, ko sta posodi B in C polni: a — b — c < x < a. Ti oceni skupaj z izrekom 1 povesta, da so vrednosti x med števili = a — kd, kjer je k = 0,1,. ■ f, hf + c'. Pokazali bomo, da ob pametnem pretakanju lahko prostornina vina v posodi A doseže vsako izmed vrednosti Uporabimo postopek Pl, ki je opisan na sliki 2.
V	postopku Pije posoda B pred vsakim natakanjem iz A v B prazna, po njem pa je polna, saj bi sicer posoda A bila prazna in bi zaradi x = 0 in y < b ob privzetku b + c < a veljalo x -4- y + z < a. Zato se pri vsakem natakanju iz A prostornina x zmanjša za b. Podobno uvidimo, da se pri vsakem natakanju v A prostornina x poveča za c.
Naj bo (xm, ym. zm) m-ta točka, ki jo obiščemo v postopku Pl. Očitno je Xj = a. Pokažimo, da za vsako drugo dovoljeno vrednost m velja:
Slika 1. Graf [8,3,2], V vsaki točki je vsaj ena posoda polna, ali pa je ena prazna. Naloga ima dve režltvl: (4,2,2) in (4.3,1).
[(<.3,1)
če je m — 2k aH m = 2k + 1, je xm = a — b — c + (ic c) mod (fa + c), kjer je k ustrezno naravno itevilo in je (icc) mod (b + c) ostanek pri deljenju
kc : (b + c).
1° Trditev je pravilna za m — 2, saj (1-c) mod (b+c) = c in je = 3 — b. 2° Naj bo m = 2k 4-1. Iz opisa postopka Pl je razvidno, da v točko z liho zaporedno Številko lahko pridemo le z natakarjem iz B v C. Po formuli za xm je ><2k+l = x2k 'n tako je tudi prav, saj pri natakanju iz 6 v C pustimo vino v posodi A pri miru. 3° Iz točke z zaporedno Številko m = 2k -f 1 stopimo v naslednjo točko. Pokazati moramo, da je
Xm+l = a — b — C + ((/f + l)c) mod (b -f c).
Poglejmo v posodo B. Ce je prazna, je xm > a — c. Od tod sledi ocena (fcc) mod (b c) + c > b + c, zaradi katere je
(fcc) mod (t + c) + c - (b + c) = ((/t + l)c) mod (b + c),
xm+i = xm - b = xm -f- c - (6 + c)
= a - b - c + (kc) mod ( b + c) + c- (b + c) = a- b- c + {(k + l)c)mod(fa + c). Za natakanje iz A v B je trditev pravilna.
(Začetek: (■,0,0).')
Na t oči i* A v B.
Slika 2. Postopek Pl. Iz A lahko odtočimo le b litrov vina, v A ga lahko določimo le c litrov naenkrat. V točko z liho zaporedno Žtevilko lahko pridemo le z natakanjem iz B v C.
Natoči i i Bv C.
Natoči ii C v A
T
Ne
(Konec: (a-b-i:,b,č]T)
Ce pa posoda B ni prazna, pustimo vino v njej pri miru in po natakanju
iz C v A je xm + c < a. Potem je
(kc) mod (b + c) + c < b + c, zato (kc)mod (b + c) + c = ((fc + l)c) mod (b + c) in je
= xm + c = a—b — c + (frc) mod (fe + c) + c = a~b~c + ((k + l)c) mod (fc + c).
Formula za xfTt_|_j. velja tudi pri natakanju iz C v A.
Sedaj znamo izračunati prostornino xm za vsako točko, ki jo obiščemo v postopku Pl. Ne vemo pa še, ali ta postopek doseže vse točke grafa; ne vemo niti, ali se sploh kdaj konča. Naslednji premislek pokaže, da je odgovor na obe vprašanji pritrdilen.
Naj bosta b' in c' prostornini posod B in C, izmerjeni z največjo skupno mero teh dveh posod. Števili b' in c' sta si tedaj tuji in ko preteče k vrednosti 1, 2, ..., b1 + c', zavzame izraz a — fc — c + (/tc) mod (b 4- c) natanko 6' + c' različnih vrednosti.
Denimo, da to ni res. Potem obstajata v zaporedju 1, 2.....b' + c'
različni števili ki in ir^, za kateri dajeta izraza k\c in fcjc pri deljenju z b + c enak ostanek. Potem je razlika k\c — k%c deljiva z b + c in je produkt (/ti — J<2)c' deljiv z b' + c'. Ker sta si števili c' in b' + c' tuji, je razlika iti — deljiva z b' + c'. To pa je zaradi ocene ki — J<2 < b' + c' možno le, če je ki = k2- Res so za k = 1, 2, ..,, b' + c' vse vrednosti a — b — c + (kc) mod (b + c) med seboj različne.
Brž ko k doseže vrednost b' + c', je
xm = a-b-c + ((b' + c')c) mod (b + c) = a-b-c + ({b + c)c') mod (b + c) = a — b — c.
Posodi S in C sta tedaj polni in postopek Pl se konča.
Iz povedanega sledi, da doseže v postopku Pl prostornina vina v posodi A vsako izmed vrednosti = a — kd, kjer je it = 0, 1, ..b' + c'.
Vrednosti x = a in x — a — b — c nastopita le v prvi in zadnji točki, vse druge vrednosti x pa nastopijo po dvakrat. Graf [a, b, c] ima potemtakem 2(i>' + c') točk. Preštejmo še povezave. V točkah (a, 0, 0) in (a-b-c, b, c) izvirata po dve, v točkah (a — b, b, 0) in (a — c, 0, c) izvirajo po tri, v vsaki
izmed preostalih točk pa po štiri. Imamo
IZREK 2. Če je fc+c < a, ima graf naloge 2(b'+c') točk in po veza v.
Vidimo, da ob pogoju ¿>+c < a podatek a ne vpliva na Število točk. Tako ima na primer graf [1734, 243, 162] deset točk - toliko kot graf [1734r 3, 2] ali pa graf [8,3,2].
Po vsem, kar smo ugotovili o grafu pretakanja, lahko nalogo o delitvi vina povemo takole:
Ali je enačba a — kd — a/2 z neznanko k rešljiva v Številih
1,2,..., b' + c'l
Izračunamo k — ^ in odgovor zapišemo v
IZREK 3. Če je b 4- c < a, je naloga o delitvi vina rešljiva natanko takrat, kadar prostornina ^ ne presega vsote b + c in je večkratnik največje skupne mere posod B in C.
V postopku P1 smo s pretakanjem iz A v B, iz B v C in iz C nazaj v A obiskali vsako točko grafa natanko enkrat. To pa lahko naredimo tudi s postopkom — imenujmo ga P2f ki je zasnovan na strategiji pretakanja A C B —► A. Bralec se lahko sam prepriča, da iz točke (a,0,0) do rešitve (če ta sploh obstaja) vodijo tudi druge poti. Vendar je najkrajša tista, ki jo kaže postopek Pl, ali pa tista, ki jo kaže postopek P2. Njuni dolžini se da izračunati, vendar tega vprašanja tokrat ne bomo načenjali.
Franc Savn i k