5. Kolobeh Mokrých Skúmaviek $\left(\kappa \le 8\right)$ vzorové riešenie

Najprv sa skúsme pozrieť na prípad, kedy sú \(n\) a \(k\) nesúdeliteľné. Ak by sa nám podarilo ukázať, že najmenší kladný objem, ktorý vieme v jednej skúmavke dostať, je \(1\), tak by sme vedeli mať v každej skúmavke každý celočíselný objem.

Nech sme objem \(1\) v jednej zo skúmaviek dostali ľubovolnou sekvenciou prelievania vody medzi skúmavkami. Aby sme v danej skúmavke dostali objem \(2\), stačí nám danú sekvenciu prelievania zopakovať dvakrát. Rovnako ak chceme v danej skúmavke dostať objem \(l\), tak nám stačí danú sekvenciu prelievania zopakovať \(l\)-krát. Zhora sme limitovaní len objemom skúmavky, logicky väčší objem vody ako objem skúmavky v nej nemôžeme mať.

Čo pre nás, ale znamená „zopakovať sekvenciu prelievania \(l\)-krát“? Uvažujme, že v sekvencii prelievania nenapĺňame neprázdnu skúmavku, nevylievame neplnú skúmavku a jednu skúmavku len plníme a druhú len vyprázdňujeme (čo pre sekvenciu pre objem \(1\), ktorú vytvoríme, platí). Prelievanie medzi skúmavkami objem nemení, môžeme ho teda zanedbať. Spočítajme počet naplnení a vyliatí. Ak ho prenásobíme \(l\)-krát, zrejme tak dostaneme \(l\)-násobný objem, ktorý vieme preliať do ktorejkoľvek skúmavky.

Keďže obe skúmavky majú celočíselný objem, tak sa nám ich prelievaním nepodarí v žiadnej vyrobiť neceločíselný objem. Prelievanie vody je ekvivalentné so sčítavaním a odčítavaním celých čísel. Teda žiaden nenulový objem menší ako \(1\) v žiadnej skúmaviek nevieme dostať. Už nám stačí ukázať, že vieme dostať objem \(1\).

Bez ujmy na všeobecnosti môžeme predpokladať, že \(n > k\). Teda si vieme \(n\) zapísať v tvare \(n = qk + r\), kde \(q\) je podiel a \(0 \leq r \leq k-1\) je zvyšok po celočíselnom delení \(n\) číslom \(k\). Najskôr naplníme veľkú skúmavku. Ak by sme postupne prelievali vodu z veľkej skúmavky do malej, pričom keď malá skúmavka je plná, tak ju vyprázdnime, po \(q\) krokoch by sme vo veľkej skúmavke mali objem \(r\). Ten by sme preliali do malej skúmavky a veľkú naplnili vodou doplna. Opäť by sme postupne prelievali vodu z veľkej skúmavky do malej a po \(q\) krokoch by sme vo veľkej skúmavke mali objem \(2r\) (keďže sme do malej skúmavky preliali o \(r\) menej vody, keďže tú sme tam mali z pôvodného prelievania).

Takto by sme vedeli vo veľkej skúmavke postupne dostávať objemy tvaru \(mr\). Vždy by sme sa však pozreli len ich zvyšok po delení \(k\), teda ak by \(mr > k\), tak by sme prebývajúci objem vo veľkej skúmavke preliali do malej skúmavky. To by sme opakovali až pokým by vo veľkej skúmavke nezostal objem menší ako \(k\). Dôležité je si uvedomiť, že sa nám stačí pozerať len na hodnoty \(m\), pre ktoré platí \(1 \leq m \leq (k-1)\). Ak by \(k \leq m\), tak by sme si mohli \(m\) zapísať v tvare \(pk+o\), kde \(p\), \(o\) sú celé čísla a \(o\leq (k-1)\), teda by sme vo veľkej skúmavke mali objem tvaru \((pk+o)r = pkr+or\). Keďže sa pozeráme na zvyšky po delení \(k\), tak \(pkr+or\) dáva rovnaký zvyšok ako \(or\).

Máme teda \(k-1\) súčinov v tvare \(mr\), kde \(1 \leq m \leq (k-1)\). Zároveň máme \(k-1\) rôznych zvyškov po delení \(k\). Teda ak by nám žiadne dva zo súčinov nedávali rovnaký zvyšok, jeden zo súčinov by musel dávať zvyšok \(1\). Ako si však môžme byť istí, že žiadne dva súčiny nedávajú rovnaký zvyšok? Predpokladajme, že také dva súčiny existujú. Nech sú to súčiny \(ir\) a \(jr\). Aby dávali rovnaký zvyšok, tak musí platiť

\[\begin{align} k &\mid (ir-jr),\\ k &\mid r(i-j).\end{align}\]

Keďže však \(k\) a \(r\) sú nesúdeliteľné, tak \(k \mid (i-j)\). Teda \(i\) a \(j\) dávajú rovnaký zvyšok, čo v našom prípade znamená, že \(i=j\). Teda taká dvojica súčinov neexistuje, takže dostávame postupne všetky zvyšky po delení \(k\), teda aj \(1\).

Resp. ak dostávame všetky zvyšky po delení \(k\), tak dostávame aj všetky celočíselné hodnoty v malej skúmavke. Rovnako to funguje aj vo veľkej skúmavke, keďže každý jej celočíselný objem sa dá vyjadriť v tvare \(ak+b\), kde \(a\) a \(b\) sú celé čísla a \(b\) je zvyšok po delení \(k\).

Keď vieme aké všetky objemy vody sa môžu nachádzať v jednotlivých skúmavkách, zostáva sa nám už len pozrieť na všetky konfigurácie, ktoré môžu nastať. Dôležité je si uvedomiť, že ak máme ľubovolnú skúmavku v inom stave, než plnom či prázdnom, druhá skúmavka nemôže byť v inom stave ako v plnom alebo prázdnom. Inými slovami, nemôže sa mi stať, že by dve skúmavky boli v poloplnom stave. Teda pre každý z objemov \(x\), kde \(1 \leq x \leq n-1\) v skúmavke s objemom \(n\), nadobúda skúmavka s objemom \(k\) len dva stavy. To robí dohromady \(2(n-1)\) rôznych konfigurácií. Pre objemy \(0,n\) v skúmavke s objemom \(n\) nadobúda skúmavka s objemom \(k\) objemy \(y\), kde \(0 \leq y \leq k\). To robí dohromady \(2(k+1)\) rôznych konfigurácií. V obidvoch skúmavkách vieme, teda vyrobiť \(2(n-1)+ 2(k+1)=2(n+k)\) rôznych konfigurácií.

Ak by \(n\) a \(k\) boli súdeliteľné, tak existuje \(\operatorname{NSD}(n,k)>1\), označme si ho \(d\). Ak by sa nám podarilo ukázať, že konfigurácie skúmaviek s objemami \(n\), \(k\) a \(\frac{n}{d}\), \(\frac{k}{d}\) sú rovnaké máme vyhrané. Skúmavky s objemami \(\frac{n}{d}\) a \(\frac{k}{d}\) majú na základe predošlého odstavca počet všetkých konfigurácií \(2 \left( \frac{n+k}{d}\right)\). Každú jednotku objemu daných skúmaviek môžeme rozdeliť na \(d\) rovnakých častí a daný dielik prehlásiť za novú jednotu objemu. Potom sme, ale v situácií, že máme skúmavky s objemami \(n\) a \(k\). Teda aj skúmavky s objemami \(n\) a \(k\) majú práve \(2 \left( \frac{n+k}{d}\right)\), keďže sa jedná o tie isté skúmavky a počet konfigurácií sa teda nemohol zmeniť.

Iné riešenie.

Na riešenie tejto úlohy vieme použiť aj vedomosť Bézoutovej rovnosti, ktorá hovorí, že pre každé dve čísla \(x,y\) existujú také koeficienty \(a,b\in \mathbb{Z}\), že \(ax+by=\operatorname{NSD}(x,y)\). A zároveň \(\operatorname{NSD}(x,y)\) je najmenšie kladné číslo, ktoré vieme napísať v takomto tvare. Ak by sa nám podarilo použiť Bézoutovu rovnosť na opísanie správania skúmaviek, mali by sme vyhrané.

Keďže \(\operatorname{NSD}(x,y)\) je nanajvýš rovné menšiemu z dvojice \(x,y\), tak s určitosťou vieme, že práve jeden z koeficientov \(a,b\) je kladný. Nech bez ujmy na všeobecnosti to bude \(a\), teda \(b\) je záporné. Kladný koeficient \(a\) bude predstavovať počet naplnených skúmaviek a záporný koeficient \(b\) počet vyprázdnených skúmaviek. Inak povedané skúmavku s objemom \(x\) naplníme vodou a následne prelejeme do skúmavky s objemom \(y\). Ak je skúmavka s objemom \(y\) plná, celý jej objem vody vylejeme. Na konci celého cyklu sme skúmavku s objemom \(x\) naplnili práve \(a\)-krát a skúmavku s objemom \(y\) vyprázdnili práve \(b\)-krát. Na základe Bézoutovej rovnosti vieme, že nám v jednej skúmavke vznikol objem vody rovný \(\operatorname{NSD}(x,y)\) a že žiaden menší objem nevieme prelievaním vody v skúmavkách vyrobiť. Zároveň vieme vyrobiť v každej skúmavke ľubovolný násobok \(\operatorname{NSD}(x,y)\). Môžeme to vidieť priamo z rovnosti \(ax+by=\operatorname{NSD}(x,y)\), keďže nám stačí len celú rovnicu vynásobiť prislúchajúcim násobkom.

Teraz nám, už len treba premenovať si naše konštanty, teda nech \(\{x,y\}=\{n,k\}\). Potom vieme v skúmavke s objemom \(n\) dosahovať všetky objemy tvaru \(id\), kde \(d=\operatorname{NSD}(n,k)\) a \(0 \leq i \leq \frac{n}{d}\), analogicky pre skúmavku s objemom \(k\).

Keď vieme, aké všetky objemy vody sa môžu nachádzať v jednotlivých skúmavkách, zostáva sa nám už len pozrieť na všetky konfigurácie, ktoré môžu nastať. Dôležité je si uvedomiť, že ak mám ľubovolnú skúmavku v inom stave, než plnom či prázdnom, druhá skúmavka nemôže byť v inom stave ako v plnom alebo prázdnom. Inými slovami, nemôže sa mi stať, že by dve skúmavky boli v poloplnom stave. Teda pre každý z objemov \(id\), kde \(1 \leq i \leq \frac{n}{d}-1\) v skúmavke s objemom \(n\), nadobúda skúmavka s objemom \(k\) len dva stavy. Čo robí dohromady \(2(\frac{n}{d}-1)\) rôznych konfigurácií. Pre objemy \(0,n\) v skúmavke s objemom \(n\), nadobúda skúmavka s objemom \(k\) objemy \(id\), kde \(0 \leq i \leq \frac{n}{d}\). Čo robí dohromady \(2(\frac{k}{d}+1)\) rôznych konfigurácií. V obidvoch skúmavkách vieme teda vyrobiť \(2\left(\frac{n}{d}-1\right)+ 2\left(\frac{k}{d}+1\right)=2\left(\frac{n+k}{d}\right)\) rôznych konfigurácií.