Opravovatelia

Baška [email protected]

Aňa [email protected]

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í.