Borkimérés

1. A klasszikus példa

Van három demizsonunk, melybõl az elsõ 3, a második 5, a harmadik 8 literes; az elsõ kettõ üres, a harmadik pedig tele van borral.  Hogyan mérjünk ki pontosan négy liter bort, ha nem használhatjuk csak ezeket a demizsonokat?

A feladat megoldható a következõ módon:

Elõször mérjünk ki öt liter bort.  Ebbõl töltsünk át három litert a háromliteres demizsonba.  Majd azt a három liter bort töltsük át a nyolclitersbe.  Az ötösben maradt két litert töltsük át a hármasba.  Ekkor két liter bor van a háromliteres demizsonban,és hat liter a legnagyobban.  Ebbõl a hat liter borból töltsük fel az ötliterest.  Még egy liter bor fér a háromliteresbe.  Ha ezt az egy litert az ötliteresbõl töltjük át, akkor abban pont négy liter marad.

2.  Algoritmus

Figyeljük meg,hogyan is mértük ki a bort!

Ha az ötös tele volt,akkor kiürítettük. Egyébként ha üres volt a hármas,akkor teletöltöttük. Egyéb esetben pedig annyi bort töltöttünk át az ötliteresbe,amennyit csak lehetett. Ez alapján lehet konstruálni egy függvényt,amely megmondja,hogy hányadik lépés után melyik demizsonban hány liter bor van:

Alg1[{a_, b_}, 0] := {0, 0, a + b}

Alg1[{a_, b_}, n_] := Alg1[{a, b}, n] = 
        Which[
Alg1[{a, b}, n - 1][[2]] == b, 
          Alg1[{a, b}, n - 1] + {0, -b,  
              b}, 
Alg1[{a, b}, 
                n - 1][[1]] == 0, 
          Alg1[{a, b}, n - 1] + {a, 
              0,  -a}, 
Alg1[{a, b}, 
                  n - 1][[2]] + Alg1[{a, b}, n - 1][[1]] <  
            b,  {0, Alg1[{a, b}, n - 1][[1]] + Alg1[{a, b}, 
                  n - 1][[2]] , Alg1[{a, b}, 
                n - 1][[3]]}, 
True, {Alg1[{a, b}, 
                  n - 1][[2]] + Alg1[{a, b}, n - 1][[1]] - b, 
            b, Alg1[{a, b}, 
                n - 1][[3]]}
]

Most nézzük meg a néhány elsõ lépést!

Table[Alg1[{3 , 5}, i], {i, 0, 15}]

Ez azért szerencsés,mert ezzel könnyen leolvashatjuk,hol mennyi bor van az akárhányadik lépés után.  Olyan mennyiségek mérhetõk ki,amelyek itt szerepelnek.Nyilván elegendõ a második {0,0,8} helyzetig átnézni.

Így azok a mennyiségek kimérhetõk ezzel a módszerrel,amelyek ebben a táblázatban elõfordulnak.Mik is ezek a mennyiségek?

Kimerh[{a_, b_}] := 
      Union[Flatten[
          Table[Alg1[{a, b}, i], {i, 
              0, (a + 1) (b + 1)}]]]

Általában nem lenne szükséges ilyen nagy táblázat.De ekkora mindig elég,mert ilyen táblázatban már van ismétlõdés,és az az elõállítási mód miatt csak a kezdeti állapot lehet. Ennek oka pedig az,hogy minden egyes állapotból visszakereshetõ,milyen helyzetbõl jutottunk el oda:Ha a háromliteres tele van,akkor biztosan azt az elõzõ lépésben töltöttük fel. Ha a háromliteres nincs tele és az ötliteres üres,az elõzõ lépésben azt ürítettük ki.Különben pedig annyit töltöttünk át az ötösbe a hármasból az elõzõ lépésben,amennyit csak tudtunk.

Most nézzük meg,mik mérhetõk ki.

Kimerh[{3, 5}]

Tehát minden mennyiség kimérhetõ ezzel a módszerrel,amely nem több,mint nyolc liter. Ez még azért is külön jó, mert ezzel az algoritmussal kaptuk meg ezeket az eredményeket. Hiszen lehetséges lenne,hogy valamely mennyiség más módszerrel kimérhetõ lenne,csak ezzel az algoritmussal nem.Ebben az esetben ez szerencsére nem történt meg.

De nem lehetne-e esetleg "megfordítani" a méréseket?Olyanra,hogy a nyolcasból mindig a ötösbe töltsünk,a hármasba mindig az ötösbõl,és a háromliteresbõl töltögessünk vissza a nyolclite-resbe?

Alg2[{a_, b_}, n_] := Alg1[{b, a}, n]

Lássuk, így mik mérhetõk ki?

Table[Alg2[{3, 5}, i], {i, 0, 15}]

Itt is elõáll a négy! És látjuk,hogy más közbülsõ lépések vezetnek a négy liter kiméréséhez,mint az elõbb.Tehát több megoldás van.

3. Észrevételek

Tehát több megoldás is lehetséges.Például a következõ módon is kimérhetõ a négy liter bor:

Kimérünk három liter bort,majd áttöltjük az ötliteresbe.Ekkor ismét három liter bort töltünk ki a legkisebb demizsonba.Ebbõl még két liter fér át az ötlitersbe.Azt át is öntjük. Így marad egyetlen liter bor a háromliteresben.Ekkor az ötösbõl visszaöntjük a bort a legnagyobb demizsonba,és az egy liter bort a háromliteresbõl átöntjük az ötliteresbe.Kimérünk hozzá három liter bort, így pontosan négy liter bor kerül az ötliteres demizsonba.

Azonban könnyen,mindössze egy kis utánagondolással belátható,hogy a fenti két megoldási mód során egyszer sem használtuk ki,hogy a legnagyobb demizson nyolcliteres.A nyolcliteres demizson emiatt tulajdonképpen helyettesíthetõ lenne pl egy káddal,amely "elég nagy, és elég sok bor van benne". Például az elsõ módszerrel a négy liter bor kiméréséhez elegendõ lenne,ha nekünk csak hét liter bor állna rendelkezésünkre,ugyanis a töltögetések során mindig maradt legalább egy liter bor a legnagyobb demizsonban.A második megoldáshoz pedig már hat liter bor is elég lenne a nyolc liter helyett,mivel a mérés során végig volt legalább két liter bor a legnagyobb demizsonban.

De ha a korábbiakkal ellentétben figyelünk arra is,hogy a legnagyobb demizson nyolc literes,kezdetben nyolc liter borral,akkor kimérhatõ a négy liter bor például a következõ módon is:U-gyanúgy kezdjük a méregetést,mint a második esetben.Azonban az utolsó lépés,a három liter bor áttöltése az egy liter bor mellé az ötliteresbe,már fölösleges volt.Mert amikor az egy liter bor már az ötliteres demizsonban volt,és már megtöltöttük a háromliterest is,akkor pont négy liter bor volt a nyolcliteres demizsonban.

Azok a függvények,amelyek nem foglalkoznak a legnagyobb demizsonban található bor mennyiségével,például azért,mert nem ismert,hogy összesen mennyi bor van. Hasonló módon határozhatók meg, mint a korábbi függvények,és most ezt ki is használjuk. Úgy állítjuk elõ õket,hogy egyszerûen "levágjuk" az utolsó számot.

Alg3[{a_, b_}, n_] := Delete[Alg1[{a, b}, n], 3]

Alg4[{a_, b_}, n_] := 
      Delete[Alg2[{a, b}, n], 3]

Lássuk:

Table[Alg3[{3, 5}, i], {i, 0, 15}]

Table[Alg4[{3, 5}, i], {i, 0, 15}]

4. Következtetések

Elõször is külön megjegyezném,hogy a feladatnak nem csak egyetlen megoldása van.Még ha a második és harmadik kimérési módot azonosnak is tekintjük,akkor is,az elsõ már lényegesen különbözik tõlük.

De azt is láttuk,hogy annak ellenére,hogy eleinte nem használtunk ki minden lehetõséget,meg tudtuk oldani a példát.Csak legfeljebb több lépésre volt szükség.Mert a kisebb demizsonokkal való méregetéshez biztosan nem kell nyolc liternél több bor,azért,mert nem fér el bennükc csak összesen nyolc liter bor.és ha nekünk csak legfeljebb nyolc liter borra van szükség,akkor ez a nyolc liter bor elfér a legnagyobb,nyolcliteres demizsonban.

Sõt,nekünk a mérésekhez már nyolc liter bor sem kell.Nyolc liter borral mindkét kis demizsont megtöltenénk,és már nem tudnánk mérni.

De összefoglalva az utóbbiakat:A megoldhatóság szempontjából teljesen mindegy számunkra,hogy a legnagyobb demizson nyolc literes nyolc liter borral,vagy legalább nyolc literes legalább nyolc liter borral.

5. Megjegyzés

A feladat megfogalmazásában nyilván nem sok szerepet játszik a "liter" szó.Azaz,ha minden litert pl.deciliterre cserélnénk,akkor ez nem változtatna a megoldhatóságon.Ha eredetileg megoldható,akkor ezután is az maradna,ha eredetileg nem megoldható,így sem lehetne.Sõt,a liter helyébe bármit,bármilyen mértékegységet írhatnánk.Vagy akármilyen általunk tetszés szerint definiált mértékegységet használhatnánk.
    
 A demizsonok méretének aránya bármely megfogalmazásban megegyezne az eredeti aránnyal,ami jelen esetben 3:5:8. Ezért nincs szerepe a mértékegységeknek,mert ez az arány számít.
 Három-,öt-és nyolcliteres demizsonnal kimérhetõ a négy liter.Így például hat-,tíz-és tizenhatliteressel kimérhetõ a nyolc liter.
 Így részben az egyszerûség kedvéért,részben a feladat eredeti szövegéhez hûen továbbra is mindig literben fogunk számolni.Bármely konstanssal megszorozva a mennyiségeket a kapott eredmények helytállóak.

Az Alg1 függvény (de a többi is) ilyen konstansszoros értékekkel is mûködik.

Table[Alg1[{11 Sqrt[2],  17 Sqrt[2]},  i], {i, 0, 20}]

6. A megoldások száma

Tudjuk,hogy több lehetõségünk is van a négy liter kimérésére.Azonban hány megoldás lehet lényegesen különbözõ?

Lényegesen különbözõnek tekinthetõ az elsõ és a második megoldás,mert más módon közelítik meg a problémát.Az erlsõ esetben a nyolcliteresbõl mindig csak ötösével mértünk ki bort,a másodiknál viszont a legnagyobb demizsonból mindig csak a háromliteressel mértünk ki.De a második és a harmadik kimérési módszer nem tekinthetõ lényegesen különbözõnek,mert bár nem egyeztek meg teljesen,de a legtöbb lépés azonos volt.

Tulajdonképpen egyelõre úgy tûnik,hogy két lényegesen különbözõ megoldás van:az Alg1-gyel,és az Alg2-vel történõ kimérés.Az biztos,hogy a közös algoritmussal kimérhetõk nem lényegesen különbözõk,de még lehetséges valamely teljesen más módszer is.

Lényegesen különbözõ megoldások keresésénél elegendõ csak a fölösleges lépésektõl mentes megoldásokat nézni. Például fölösleges lépések vannak egy megoldásban, ha valamely két köztes állapot megegyezik a mérések során. Hiszen ha mondjuk ugyanúgy oszlik el a bor a harmadik és a tizenhetedik mérés során, akkor az összes lépés a negyediktõl a tizenhetedikig fölösleges volt. A sok fölösleges lépés miatt esetleg két lényegesen nem különbözõ megoldást lényegesen különbözõnek tekinthetnénk. Meg amúgy is,mi nem akarunk fölöslegesen méregetni. Ezért nem kell foglalkozni a fölösleges lépéseket tartalmazó megoldásokkal.

7. Észrevétel

Egy fontos észrevételt tehetünk arról,hogyan is mértük ki a négy liter bort az ötliteres demizsonba a nyolcliteresbõl.Eleinte a pontos megfogalmazástól eltekintve,csak az összefüggésre rávilágítva:

Az elsõ esetben kimértünk a nyolcliteresbõl kétszer öt litert és kiöntöttünk kétszer három litert az ötliteresbõl.De:

Másodszor pedig háromszor mértünk ki három litert,és egyszer öntöttünk ki ötöt.

Mi három-és ötliteres demizsonokkal mérünk.És mindig teletöltjük õket.Ezért mi csak olyan mennyiségeket tudunk kimérni,amelyek elõállíthatók a három és az öt lineáris kombinációjaként.Bárhogy mértünk ki valamilyen mennyiséget,biztosan visszakereshetjük az adott elõállításhoz tartozó lineáris kombinációt.

Tehát ha belátjuk egy mennyiségrõl,hogy nem állítható elõ a három és az öt lineáris kombinációjaként,akkor már beláttuk azt is,hogy a mennyiség nem mérhetõ ki.

Azonban foglalkozni kell azzal a kérdéssel is,hogy ha egy mennyiség valamiképp elõáll a három és az öt lineáris kombinációjaként,vajon jelenti-e ez azt is,hogy ki is mérhetõ.

Nevezzük kimért bornak azt a mennyiséget,amely a három és az ötlitertes demizsonban található.Például,ha az egyikben három,a másikban két liter van,akkor a kimért bor mennyisége öt liter.A kimért bor mennyisége nem lehet több nyolc liternél emiatt.Arra nem kell figyelni,hogy a kimért borból a legnagyobba visszatöltött bor ott elférjen:mivel erdetileg csak ott volt bor,még ha az összeset is vissza akarnánk tölteni,az is elférne.

Hogyan is írható fel a négy a három és az öt lineáris kombinációjaként?Ehhez a következõ diophantoszi egyenletet kell megoldani:

Ez megoldhatõ.Nem csak azért tudjuk,mert már találtunk két megoldást,hanem azért is,mert az ilyen egyenletek akkor és csak akkor oldhatók meg,ha az ismeretlenek együtthatóinak legnagyobb közös osztója osztja a konstans tagot.Oldjuk is meg:

Tudjuk,hogy 3*3-1*5=4. Így például megoldás,ha x=3 és y=-1. De:

Tehát pl.megoldás a következõ is:8*3-4*5=4. Azonban felírható-e ez az összeg olyan módon,hogy elvégezhetõ legyen kimérésként?

Legyen K a kitöltött bor mennyisége.Nyilván K≤8 feltételnek mindig teljesülni kell.Most akkor próbáljunk mérni a fenti lineáris kombináció alapján.

Mi nem akarunk fölösleges méréseket végezni.Ezért a mérést olyan módon próbéljuk megoldani,hogy összesen csak nyolcszor mérjünk be három litert,és négyszer öntsünk vissza ötöt. Ha ezt el tudjuk érni,akkor nem végeztünk fölösleges lépést.Mert:

Nyilván teljesen fölöslegesen mérnénk ki a harmadik lépésben három litert,ha utána ismét csak bemérnénk.

Most tekintsük K-t:

K+3≤8 ⟺ K≤5 Tehát ha ki tudunk mérni újabb három liter bort,akkor nme tölthetõ vissza még az öt liter.És K>5 ⟺ K+3>8 Azért nem lehet egyenlõ,mert mi nem akarjuk mérések közben ismét teljesen kiüríteni a két kisebb demizsontm,mert akkor minden korábbi lépés fölösleges lett volna.De akkor ez azt is jelenti,hogy ha kiönthetõ 5 liter bor,akkor ki is öntendõ,mert már nem férne el újabb három liter bor a két kisebb demizsonban.

És nyilván legelõször nekünk olyan mennyiségû bort akarunk kimérni,amely együtthatója a lineáris kombinációban pozitív (valamelyik biztosan az).Mert mi nem akarunk fölösleges lépéseket végezni.

De akkor ez már azt jelenti,hogy minden lineáris kombinációhoz tartozó kimérési sorrend egyértelmûen meghatározott.Például a fenti esetben:

Már itt is megállhatnuk,mert részletösszegként megkaptuk a négyet.És innentõl kezdve nyilván már fölöslegesen méregetnénk tovább,azt pedig nem akarjuk.Lehetséges,hogy két demizsonban található a négy liter,de már akkor is csak egy lépés szükséges,minden további töltögetés feölösleges lenne,és az úgy kapott megoldás már nem is lenne a korábbitól lényegesen különbözõnek tekinthetõ.

Bár egy konkrét példán mutatott a módszer,de ilyen módon minden lineáris kombinációhoz készíthetõ lenne kimérési sorrend (legfeljebb "levágnánk a végét",mint ahogy az elõbb is történt).De már korábban igazolt,hogy csak olyan mennyiség mérhetõ ki,amely elõáll a három és az öt lineáris kombinációjaként.Emiatt:

Egy adott mennyiség akkor és csak akkor mérhetõ ki a három-és ötliteres demizsonnal,ha az adott mennyiség elõáll a három és az öt lineáris kombinációjaként.

De mér beláttuk,hogy a lineáris kombinációkhoz tartozó kimérési sorrend egyértelmû.Így,ha mi csak lényegesen különbözõ megoldásokat keresünk,akkor már a legelsõ méréssel eldöntöttük,milyen módszer szerint akarjuk kimérni a bor mennyiségét:elkezdjük a mérést,és az elsõ adandó alkalommal,amikor négy liter a kimért bor mennyisége,megállunk.

Még egy dolgot kell figyelembe venni:ha ismert az összes bor mennyisége,akkor mi figyelhetjük azt is,vajon nem négy liter bor van-e a legnagyobb demizsonban.
      Most már kezdhetjük összefoglalni az eseteket a kimérési sorrend szempontjából.A két lehetséges kimérési sorrend:

Így,ha tudjuk az összes bor mennyiségét,a következõ módon mérhetõ ki a négy liter:

Az egy csoportba vett megoldások nyilván nem különböznek lényegesen,és az utolsó lépésbõl eldönthetõ,hogy melyik számunkra az egyszerûbb.De az biztos,hogy két lényegesen különbözõ megoldás van.

Ha nem tudjuk,hogy összesen mennyi borunk volt,csak azt,hogy legalább nyolc liter legalább nyolcliteres demizsonban,akkor is marad két lényegesen különbözõ megoldás:

8. Becslés a bor mennyiségére

Még az összefüggések tanulmányozásának elején beláttuk,hogy a négy liter bor kiméréséhez elegendõ a nyolc liter bor.Azaz,ha lenne nyolc liter borunk,de nem lenne megoldható a feladat,annak oka biztosan nem az lenne,hogy nincs elég borunk.De a néhány felsorolt megoldásnál láttuk,hogy néha már kevesebb bor is elég lenne.Például a második megoldásnál utólag beláttuk,hogy már hat liter borral is elvégezhetõ a módszer.Azonban a megoldás során a bor mennyiségét végig ismeretlennek feltételeztük,csak azt tudtuk,hogy a bor mennyisége elég sok ahhoz,hogy a kérdéses lépéseket végrehajtsuk.

Ezért vetõdhet fel a következõ kérdés,a feladat egy másik változata:Van egy három-,egy öt-és egy nyolcliteres demizsonunk,utóbbiban valamennyi bor.Ezekkel szertnénk kimérni négy liter bort.Találjuk meg azt a módszert,amely a legkevesebb mennyiségû bort igényli.

Mi már tudjuk,hogy van olyan módszer,amellyel a mérés már akkor is elvégezhetó,ha a bor mennyisége csak hat liter.És nyilván legalább négy liter bor kell ahhoz,hogy kimérhessünk négy litert.

Tulajdonképpen ezt a kérdést úgy is vizsgálhatjuk,hogy ha nyolc liter bor lenne a legnagyobb demizsonban a kiindulási állapitban,akkor mennyi bor marad a mérések során végig a legnagyobb demizsonban.És ezt a mennyiséget a nyolc literbõl kivonva kapnánk meg a szükséges bormennyiséget.Hiszen ez a bor végig a legnagyobb demizsonban van,akkor nem hiányozna a mérések során.Ugyanakkor ha kicsit több bor hiányozna,akkor nem lehetne már mérni,hiszen legalább egy állapotban negatív mennyiségû bor lenne a nyolcliteres demizsonban,ami nyilván nem lehetséges.

Hogyan is mértük ki a második módszerrel a bort?Kimértünk három liter bort,és átöntöttük az ötösbe.Ekkor végig még volt öt liter bor a legnagyobb demizsonban.Majd megint kimértünk három litert,ekkor is maradt még két liter bor a nyolcasban.Majd a hármasból kiegészítettük az ötöst,azt pedig visszaöntöttük a nyolcasba,így ott már megint volt hét liter bor.Végül az egy liter bort átöntöttük az ötösbe,majd kimértünk három liter bort.Így kaptuk meg a négy liter bort a legnagyobb demizsonban.A mérések során a legnagyobb demizsonban mindvégig volt legalább két liter bor.Így ha ez a bor "nem lenne",az még nem rontaná el a mérésünket.Így valóban,ha ismeretlen mennyiségû borunk van,de legalább hat liter,megoldható a feladat.

Most a "fölösleges",azaz az olyan bor mennyiségét becsültük,amelynek hiánya nem rontaná el a mérési módszert. De mi becsülhetjük közvetlenül is a szükséges bor mennyiségét.Hiszen a szükséges bor mennyisége legalább annyi,hogy a kitöltött bor mennyisége minden állapotban ugyanannyi,vagy kevesebb legyen nála. De annál több bor nem kell, mint amennyi borból kimérhetõ a szükséges mennyiségû kitöltött bor,mert akkor már a mérés elvégezhetõ,és mi pont azt a minimális bormennyiséget keressük,amellyel elvégezhetõ a mérés.

A korábban elért eredményeket felhasználva jóval egyszerûbben megadhatjuk a választ a bor mennyiségének (M) becslésére.

M számunkra ismeretlen,így nekünk a négy liter bor kiméréséhez csak két lényegesen különbözõ lehetõségünk van:

Nyilvánvalóan más,azaz nem lényegesen különbözõ mérési lehetõségek (ami az összes többi),most eltekinthetünk.Mert fölösleges lépéseket a négy liter bor kimérése során most sem akarunk végezni.Sõt,a fölösleges lépések végrehajtása lehet,hogy nagyobb mennyiségû bort igényel.De ha többet nem is,kevesebbet biztos nem.Így azon esetek vizsgálata tényleg teljesen fölösleges lenne.Ezért elegendõ csak a fenti két esettel foglalkozni.

Már megfogalmaztuk,hogy mennyi bor szükséges:annyi,hogy a szükséges lépések mindig elvégezhetõk legyenek,azaz minden állapotban a szükséges bor mennyisége nagyobb vagy egyenlõ a kitöltött bor mennyiségénél.De már azt is beláttuk,hogy a minimálisan szükséges bormennyiség ezen kitöltött mennyiségek maximuma.Így az elsõ módszernél a következõknek kell teljesülni:

Emiatt 6≤M.Tehát a mérés kivitelezéséhez legalább hat liter bor szükséges.

Ugyanezen módon belátható,hogy valóban kell hét liter bor ahhoz,hogy a másik összeg jellemezte mérés elvégezhetõ legyen:

Ezen feltételek teljesülnek,ha 7≤M.Tehát valóban,legalább hét liter bor kell ahhoz,hogy elvégezhetõ legyen a mérés.

Becsüljük a kimért bor mennyiségét.  Ez az,amennyi a két kisebb demizsonban összesen van.

Kimert2[{a_, b_}, 
        n_] := Alg2[{a, b}, n][[1]] + Alg2[{a, b}, 
            n][[2]]

Kimert2[{5, 3}, 3]

Table[Kimert2[{5, 3}, i], {i, 0, 15}]

A mérés kivitelezéséhez szükséges minimális bormennyiség is jól meghatározható ezek alapján.

Szuk2[{a_, b_}, c_] := 
      Max[c, Table[Kimert2[{a, b}, i], {i, 0, Lep2[{a, b}, c]}]]

Szuk2[{5, 3}, 4]

Table[Szuk2[{5, 3}, i], {i, 0, 8}]

Ellenõrzésképp:

Table[Alg2[{5, 3}, i], {i, 0, 15}]

9. Észrevétel

Az eredeti összefüggések:

Kicsit más alakra hozva az elsõ kettõt:

Mit is jelent ez?Ezek a sorok pontosan azt írják le,mi a mi kimérési eljárásunk volt.Az elsõ esetben addig mértünk ki három litert,amíg fért a két kisebb demizsonba,majd,ha már nem fért,akkor öt litert visszamértünk.Hasonló volt az eljárás a második esetben is.Azonban ez az alak már egyértelmûvé teszi,mi is felel meg a részletösszegeknek az elsõ,illetve a második esetben:

Korábban megállapítottuk,hogy:"... igaz, hogy ha valamelyik összeg elsõ néhány tagját kiválasztva a részletösszeg megegyezik a kívánt menniséggel, akkor a kívánt mennyiség kimérhetõ."

Most már megfogalmazhatjuk ezt az állítást más alakban:Kimérhetõ az adott mennyiség (y),a három-és ötliteres demizsonok segítségével,ha megoldhatók a következõ kongruenciák.

Mivel tudjuk,hogy mit takarnak ezek a kongruenciák,ezért tudjuk azt is,hogy az egyik akkor és csak akkor oldható meg,ha a másik is.De ez könnyen belátható a kongruenciák tartalmának ismerete nélkül is:

De ismert a következõ összefüggés is:

Az a*x ≡ b (m) lineáris kongruencia megoldható⟺(a,m)|b.

Így most már kimondhatjuk:Egy három-és egy ötliteres demizson segíségével bármely egész mennyiségû bor kimérhetõ egy és nyolc liter között.Persze csak akkor,ha van annyi borunk.

Indoklás:1≤y≤8 ha teljesül:Az y liter bor kimérhetõ ⟺ 3*k ≡ y (8) kongruencia megoldható ⟺ (3,8)|y azaz 1|y.de az 1 minden egész szám osztója,tehát igaz az állítás.

10. Megjegyzések

Természetesen,mint a korábbi példa is mutatja,lehetséges,hogy a kívánt mennyiségû bor majd hamarabb marad "maradékként" a legnagyobb demizsonban,minthogy kimérnénk a két kisebbe.Persze ezzel a lehetõséggel csak akkor számolhatunk,ha ismert az összes bor mennyisége.

A fenti összefüggés felhasználható azon kérdés megválaszolására is,amikor a kiméréshez szükséges bor legkevesebb mennyiségét keressük.A részletösszeges formában már megkaptuk a választ,csak át kell fogalmazni kongruenciákra.Ebben a formában pedig a következõképpen hangzik:

Ha x mennyiségû bort akarunk kimérni:k*3 ≡ x (8),akkor M1 az m*3 ≡ y (8) y mennyiségeinek maximuma,ahol 1≤m≤k és 0≤y≤7. 
Ugyanezen módon meghatározott M2 is,csak az a k*5 ≡ x (8) kongruencia alapján.  A minimálisan szükséges bor mennyisége pedig ezen M1 és M2 értékek minimuma.

11. Egy másik általánosítás: hány literesek a demizsonok?

Eddig három-és ötliteres demizsonokkal mértünk.Mostantól egy a-és egy b-literes demizsonokkal szeretnénk mérni.

Elõször nézzünk néhány példát a korábbi függvényekkel.

Kimerh[{3, 5}]

Kimerh[{21, 4}]

Kimerh[{9, 49}]

Kimerh[{6, 15}]

Kimerh[{2, 14}]

Most már a következõ kérdésre keressük a választ:Van egy a-és egy b-literes demizsonunk.Ezekkel melyek azok az (a+b)-nél nem nagyobb mennyiségek,amelyek kimérhetõk egy (a+b)-literes demizsonból.Illetve,mint ahogyan már korábban beláttuk,a megoldhatóság szempontjából közömbös változtatás,ha a teli (a+b)-literes helyett egy legalább (a+b)-literest veszünk legalább (a+b)-liter borral.Legfeljebb több lépésre lesz szükségünk.

A bizonyítások teljesen azonos módon történnek,mint a korábbi speciális eseteknél.Hiszen pl.a bor felének kimérésekor nagyon sokszor nem használtuk,ki,hogy a keresett mennyiség éppen az összes fele.

A kérdéses mennyiségû bor kimérhetõ,ha a két demizson térfogatának mérõszámának legnagyobb közös osztója osztja a kívánt mennyiséget.Illetve most is igaz,hogy a mennyiségelnek csak az aránya számít.

Emiatt a megoldhatóság eldöntésének van egyszerûbb módja:használhatjuk a nem is sokkal korábban kimondott tételt is.

\(\(\(
\)\(\(Megoldh[{a_, b_}, c_] := 
      If[Element[c/GCD[a, b]\  && \ c < \ a + b + 1, \ Integers], True, 
        False]\)\(
\)
    \)\)\)

Megoldh[{6, 8},  7]

Megoldh[{3, 5}, 4]

Tetszõleges demizsonoknál is igaz,hogy a kimérési sorrend csak attól függ,hogy elsõre a,vagy b liter bort mértünk ki.Ezután már egyértelmûen meghatározott,hogyan kell folytatnunk,ha nem akarunk fölösleges lépéseket végezni.

Például a liter bor kimérésével kezdtük,és a kimért bor mennyisége s.  De:

Tehát ha kimérhetõ újabb a liter bor,akkor még nem mérhetõ vissza b liter.És:

Így ha már visszamérhetõ b liter bor,nem mérhetõ ki újabb a liter.És ugyanígy meghatározott a kimérési sorrend,ha b liter kimérésével kezdtünk.

Ha pedig tudjuk,hogy összesen mennyi borunk van,akkor arra is figyelnünk kell,hogy nem maradt-e esetleg már korábban pont annyi bor a legnagyobb demizsonban,mint amennyit mi ki szeretnénk mérni.

És szintén azt is analóg módon kapjuk meg,ha a legkevesebb szükséges bort szeretnénk megtudni.

12. Az "átmozgatott" bor mennyisége

Mit is jelent ez?Azt,hogy összesen mennyi bort töltögettünk a mérések során.Például:

"Kimérünk három liter bort és áttöltjük az ötliteresbe."

A fenti mûvelet során 6 literrel nõtt az áttöltött bor mennyisége,mert három litert jelent míg kimértük,de maga az áttöltés az ötliteres demizsonba is újabb három liternyi "átmozgatást" jelent.

Szerencsére a korábbi eredményeket felhasználva ez a mennyiség már elég egyszerûen becsülhetõ.

Ennek oka pedig az,hogy az általunk használt mérési módszer során adott demizsonból csak egyetlen helyre kerülhet a bor,illtve adott demizsonba csak egyetlen helyrõl kerülhet bor.

Például elõször nézzük az eredeti példát.

Mondjuk most a mérést a következõ lineáris kombinációval jellemezhetõ módon végezzük:

Ekkor a legnagyobb demizsonból kimértünk összesen kilenc liter bort.A mérés legvégén a háromliteres demizson üres,így innen az összes bor továbbmozgott.De akkor az átmozgatott bor mennyisége már legalább tizennyolc liter.Így kilenc liter bor került be összesen az ötliteres demizsonba.Viszont a végén már csak négy liter van ott.Tehát az átmozgatott bor mennyisége további öt literrel több.Emiatt legalább huszonhárom liter.

Azonban a kérdéses mennyiség pontosan huszonhárom liter.Ugyanis a legnagyobból mi csak a hármasba mértünk bort,a hármasból csak az ötösbe,az ötösbõl pedig csak a legnagobba mértünk vissza bort.Így már mi minden esettel foglalkoztunk.De akkor már nem lehet több az átmozgatott bor mennyisége,mint amennyit eddig számoltunk,ami huszonhárom liter.

Ha mi az utolsó mérés,az utolsó három liter bor ötliteresbe töltése elõtt észrevesszük,hogy a legnagyobban már pont négy liter bor van (ha ismerjük az összes bor mennyiségét),akkor egy "háromliteres lépést" nem teszünk meg,és az átmozgatott bor mennyisége húsz liter.Ekkor mi a következõ összeg alapján mértünk:

És ezzel a módszerrel mindig számolható természetesen az átmozgatott bor mennyisége.De azért paraméteres megoldás helyett ide inkább még egy példát írok.

Mégpedig azt,amikor négy liter bort mértünk ki a következõ összeggel jellemezhetõ módon:

Ekkor az ötösökbe kimértünk tíz liter bort.A mérés végén négy liter maradt ott,így hat litert mozgattunk tovább.A mérés végén a háromliteres teli volt,de akkor a hat literbõl mi csak három liter bort mozgattunk tovább.Így ezen mérések során az átmozgatott bor mennyisége tizenkilenc liter.

Ennek olyan vonatkozásban lehet jelentõsége,ha minket nem zavar,ha több lépésben kell ide-oda töltögetni a bort,amennyiben összességében átmozgatott bor mennyisége kevesebb.Például ha arra gondolunk,hogy ha kevesebb bort kell átmozgatnunk,akkor lehetséges,hogy gyorsabban végzünk a méréssel

A lépés során átmozgatott bor mennyisége is becsülhetõ a korábbi függvények segítségével.  Ugyanis egy lépés során egy helyen nem változik a bor mennyisége,egy helyen csökken,egy helyen nõ.  Ott,ahol nõ, ott pontosan az átmozgatott bor mennyiségével növekszik.

Mozg1[{a_, b_}, 0] := 0

Mozg1[{a_, b_}, n_] := 
      Mozg1[{a, b}, n - 1] + 
        Max[Alg1[{a, b}, n] - Alg1[{a, b}, n - 1]]

Table[Mozg1[{3, 5}, i], {i, 1, 15}]

Mozg2[{a_, b_}, 0] := 0

Mozg2[{a_, b_}, n_] := 
      Mozg2[{a, b}, n - 1] + 
        Max[Alg2[{a, b}, n] - Alg2[{a, b}, n - 1]]

Table[Mozg2[{3, 5}, i], {i, 1, 15}]

13. Lépésszám

Mérjük meg az elõállításhoz szökséges lépésszámot.De mivel minden függvény azonos elven mûködik,ezért csak az egyik  verziót írom ki.

Lep2[{a_, b_}, c_] := 
      Module[{i}, i = 0; 
        While[MemberQ[Alg2[{a, b}, i], c] == False, i = i + 1]; 
        i]

ListPlot[Table[Lep2[{3, 5}, i], {i, 0, 8}], 
        PlotJoined -> True];

Most próbáljuk megbecsülni az összesen átmozgatott bor mennyiségét egy mérés során.

Atmozg2[{a_, b_}, c_] := Mozg2[{a, b}, Lep2[{a, b}, c]]

Table[Atmozg2[{3, 5}, i], {i, 0, 8}]

Végül vizsgáljunk meg egy olyan esetet,amivel eddig nem foglalkoztunk,a fenti függvényeket használva.

A két demizson mérete kilenc és tizenhat liter.

Kimerh[{16, 9}]

Megoldh[{16, 9}, 13]

Table[Kimert2[{16, 9}, i], {i, 0, 16}]

Ott a tizenhárom liter bor.

Szuk2[{16, 9}, 13]

Tehát legalább ennyi bor kell.

Atmozg2[{16, 9}, 13]

Lep2[{16, 9}, 13]

Table[Alg2[{16, 9}, i], {i, 0, 14}]

Innen leolvashatók a szükséges mérések.És segít ellenõrizni,valóban jól mûködtek-e a függények.