Pripomeňme si, že ráno dostala Dášenka dve rovnaké čísla $p$ a $d$, ktoré sú väčšie ako nula. Následne niekoľkokrát hodila mincou a podľa toho, čo jej padlo spravila jednu z nasledovných operácií.

• Z (znak): pripočítame $d$ ku $p$, takže vznikne dvojica čísel $p+d$ a $d$

• H (hlava): pripočítame $p$ ku $d$, takže vznikne dvojica čísel $p$ a $d+p$

Na konci dňa mala Dáša dvojicu čísel $P$ a $D$. Našou úlohou bolo z týchto čísel zistiť, s akou hodnotou $p$ začínala a tiež prísť na to, čo jej padalo na minci.

Na začiatok urobme niekoľko užitočných pozorovaní:

• Dáša nikdy nemohla mať záporné číslo alebo nulu.

Obe čísla $p, d$ sú ráno väčšie ako nula a operácie $Z$ a $H$ k nim hodnoty pričítavajú. No a súčet dvoch kladných čísel môže byť iba kladný.

• Okrem rána (pred prvým hodom) sa Dášine čísla nemôžu rovnať.

Predstavme si, že v nejakom momente má Dášenka čísla $P’$ a $D’$. Po ďalšom hode bude mať čísla $P’+D’$ a $D’$ (resp. $P’$ a $D’+P’$). Ak by sa ale tieto dve čísla rovnali, tak platí $P’+D’ = D’$ (resp. $P’ = D’+P’$), čo znamená, že $P’ = 0$ (resp. $D’ = 0$). Podľa predchádzajúceho pozorovania sa však niečo také nemôže stať.

Podúloha a)

Dášenka doniesla Bobovi čísla $P=15$ a $D=35$.

Ako zistíme začiatočné čísla a postupnosť hodov? Najlepšie by bolo odsimulovať Dášenkino hádzanie, nevieme však, kde začať. Mohli by sme teda vyskúsať všetky možné začiatočné hodnoty $p$. Tých je iba 15. Uvedomme si totiž, že platí $p \leq P = 15$ a $p \leq D = 35$. Nepoznáme však ani postupnosť hodov, museli by sme vyskúšať všetky možnosti toho, čo mohla Dáša hodiť.

Skúšať všetky možnosti hodov je naozaj náročné a počet možností stúpa veľmi rýchlo s rastúcim počtom hodov. V prvom kroku mohla hodiť buď $H$ alebo $Z$. To sú dve možnosti. V druhom kroku síce platí to isté, ale už musíme rátať s tým, čo padlo v prvom kroku, takže máme štyri možnosti: $ZZ, ZH, HZ, HH$. Pri troch hodoch je tých možností opäť dvakrát viac, lebo pre každú z postupností pre dva hody máme dve možnosti čo mohlo padnúť ďalšie: $ZZ\pmb{Z}, ZZ\pmb{H}, ZH\pmb{Z}, ZH\pmb{H}, HZ\pmb{Z}, HZ\pmb{H}, HH\pmb{Z}, HH\pmb{H}$. Každým hodom sa počet možností, ktoré musíme vyskúšať, zdvojnásobí. Už pre 10 hodov musíme vyskúšať viac ako $1\,000$ možností, preto to nevyzerá ako správny postup.

Skúsme sa teda na to pozrieť zozadu. Pri tomto postupe aspoň poznáme výsledné hodnoty $P$ a $D$. Čísla, ktoré mala Dášenka pred posledným hodom si označme $P’$ a $D’$, ich hodnotu zatiaľ nepoznáme. Následne padla minca, čísla sa zmenili a dostali sme čísla $P$ a $D$. Posledný hod mohol byť $Z$ aj $H$, skúsme preto vyskúšať obe možnosti.

Posledný hod: znak

Ak čísla pred posledným hodom boli $P’$ a $D’$ a hodili sme $Z$, tak nové čísla musia byť $P’+D’$ a $D’$. Zároveň vieme, že nové čísla sú $P = 15$ a $D = 35$ (keďže to bol posledný hod), takže musí platiť:

$$P’+D’ = P = 15$$ $$D’ = D = 35$$

Z týchto rovníc vyplýva, že $D’ = 35$ a $P’ + 35 = 15$, teda $P’ = -20$.

To sa ale vylučuje s naším pozorovaním – nemôžeme mať záporné číslo. Posledný hod teda nemohol byť znak.

Posledný hod: hlava

Budeme postupovať úplne rovnako ako predtým.

Čísla pred posledným hodom boli $P’$ a $D’$ a hodili sme $H$, takže nové čísla musia byť $P’$ a $D’+P’$. Zároveň vieme, že nové čísla sú $P = 15$ a $D = 35$ (keďže to bol posledný hod), takže musí platiť:

$$P’ = P = 15$$ $$D’+P’ = D = 35$$

Z toho jasne vyplýva, že $P’ = 15$ a $D’ + 15 = 35$, teda $D’ = 20$.

Obe čísla su kladné, takže posledný hod mohol byť $H$. Keďže sme však hod znak vylúčili, posledný hod musela byť hlava.

Zvyšné hody

Teraz však máme úplne rovnakú úlohu, ale s číslami $15$ a $20$. Rovnakou úvahou ako predtým by sme zistili, že posledný hod nemohol byť znak (čísla pred hodom by museli byť $-5$ a $20$), ale musel byť hlava. Takže dostaneme čísla $15$ a $5$. A takto postupujeme, až kým nemáme dve rovnaké čísla:

Začiatočné čísla $p$ a $d$ boli rovné číslu 5, a skrátená postupnosť hodov je 2Z, 2H.

Tento príklad bol pekný. Keď sme išli odzadu, tak v každom kroku nám vyšla iba jedna možnosť hodu, druhá nebola možná, lebo viedla k záporným číslam. Musí to tak však byť vždy? Vieme si z tohto príkladu odvodiť aj nejaké všeobecnejšie pozorovania?

• Ak máme výsledné čísla $P$ a $D$, tak predchádzajúce čísla $P’$ a $D’$ vieme zistiť pomocou jedného odčítania (ak vám nasledujúce rovnice nie sú jasné, skúste sa vrátiť vyššie, kde sme odvádzali hodnoty $P’$ a $D’$):

• Hod $Z$:

$$P’ = P - D$$ $$D’ = D$$

• Hod $H$:

$$P’ = P$$ $$D’ = D - P$$

• Ak sú čísla $P$ a $D$ rôzne, tak práve jedno z $P-D$ alebo $D-P$ je kladné.

• Aby sme nedostali záporné čísla, tak vždy odčítavame menšie číslo od väčšieho. To zároveň určuje, posledný hod mince. Ak je menšie prvé číslo, posledný hod bol $H$, ak je menšie druhé číslo, posledný hod bol $Z$.

• Keďže čísla sú vždy rôzne, tak nikdy nemáme na výber medzi hlavou a znakom. Rovnaké čísla môžeme mať iba na začiatku nášho zisťovania, keď sme prišli k hľadaným číslam z rána.

• Postupnosť hodov zisťujeme odzadu.

Podúloha b)

Dášenka doniesla Bobovi čísla $P=111$ a $D=9$.

Rovnako ako v podúlohe a) to vieme spraviť postupným odčítavaním odzadu, čím dostaneme takýto výsledok:

Určite vás ale nebavilo odčítavať 9 stále a stále dookola – až dvanásťkrát. Nedalo by sa to spraviť rýchlejšie?

Vieme že 9 potrebujeme odčítať od čísla 111 toľkokrát, aby toto prvé číslo bolo menšie ako 9. Takže ak je rozdiel medzi 111 a 9 rovný 102, tak potrebujeme odčítať toľko 9, aby ich súčet bol aspoň 102. Zároveň to ale nemôžeme prehnať a dostať sa k záporným číslam. Hľadáme teda najmenší počet 9, ktorých súčet je aspoň 102.

Naša otázka teda je: “Koľkokrát musíme vynásobiť číslo 9, aby sme dostali číslo 102?”, na čo si vieme odpovedať pomocou delenia $102 / 9 \doteq 11,3$. Vidíme, že 11 deviatiek nebude stačiť a potrebujeme ich 12 (lebo $12 \cdot 9 = 108$ a to je naozaj väčšie ako 102). Mohli by sme teda povedať, že potrebný počet deviatiek je číslo $\frac{102}{9}$ zaokrúhlené nahor, teda 12.

Iný pohľad na to je, že potrebujeme od 111 odčítavať 9 kým nebudeme dostávať záporné čísla. Čo je vlastne inak povedané, “Koľkokrát sa deviatka zmestí do čísla 111?”. To sa dá vyjadriť podielom $111 / 9 \doteq 12,3$, ktorý zaokrúhlime nadol, dostaneme teda číslo $12$.

Vidíme, že oba postupy nám dávajú rovnaký výsledok – 12 odčítaní, ktorý sedí s naším predošlým riešením. Namiesto dvanástich odčítaní teda spravíme jedno delenie, do skrátenej postupnosti hodov si zapíšeme $12Z$ a nové hodnoty $P$ a $D$ budú $111 - 12\cdot 9$, teda 3 a 9.

Tento postup vieme samozrejme zovšeobecniť. Majme čísla $P$ a $D$, o ktorých predpokladajme, že $P > D$ (ak to bude naopak, tak postup bude takmer rovnaký). Chceme preto zistiť, koľko znakov v rade padlo na minci. Pýtame sa teda, koľkokrát sa hodnota $D$ zmestí do $P$, čo vieme zistiť pomocou celočíselného delenia $P / D$ (celočíselné delenie zaokrúhľuje nadol), túto hodnotu si označme $k$. Následne si do postupnosti hodov zapíšeme $kZ$, hodnota $D$ ostane nezmenená a novú hodnotu $P$ vypočítame ako $P - k\cdot D$.

Môžete si všimnúť ešte jednu zaujímavú vlastnosť. Od čísla $P$ odpočítavame hodnotu $D$ najviac krát ako vieme. To čo nám ostane je preto zvyšok po delení čísla $P$ číslom $D$. Tomu naozaj zodpovedá aj hodnota $P - k\cdot D$. A keďže väčšina programovacích jazykov vie zvyšok po delení počítať priamo, najrýchlejší spôsob ako zistiť novú hodnotu $P$ je použiť príkaz P = P%D (% označuje zvyšok po delení).

Čo ak je nová hodnota nula? Túto možnosť, že $P - k\cdot D = 0$ sme doteraz ignorovali. Všimnime si však, že v takomto prípade je číslo $P$ násobkom čísla $D$. Ak teda od $P$ odčítam $D$ iba $k-1$ krát, dostanem dve rovnaké čísla, obe rovné $D$. Takáto situácia preto nastane iba raz, a to na konci nášho výpočtu. Do skrátenej postupnosti vtedy zapíšeme $(k-1)Z$ a za hodnoty čísel $p$ a $d$ dosadíme aktuálne $D$.

Podúloha c)

Vedeli by ste riešiť takýto problém pre ľubovoľnú dvojicu čísel $P$ a $D$?

V predošlých častiach sme si ukázali všetky potrebné postupy, ostáva spojiť ich dokopy.

• Ak je $P > D$ tak zisťujeme dĺžku sekvencie znakov

$k = \frac{P}{D}$ zaokrúhlené nadol

hodnota $D$ sa nemení

• Ak $P$ nie je deliteľné $D$

zmeníme hodnotu $P$ na $P - k\cdot D$

zapíšeme $kZ$ do skrátenej postupnosti

• Ak je $P$ deliteľné $D$

zmeníme hodnotu $P$ na $P - (k-1)\cdot D$ (čo je vlastne $D$)

zapíšeme $(k-1)Z$ do skrátenej postupnosti

• Ak je $D > P$ tak zisťujeme dĺžku sekvencie hláv

$k = \frac{D}{P}$ zaokrúhlené nadol

hodnota $P$ sa nemení

• Ak $D$ nie je deliteľné $P$

zmeníme hodnotu $D$ na $D - k\cdot P$

zapíšeme $kH$ do skrátenej postupnosti

• Ak $P$ delí $D$

zmeníme hodnotu $D$ na $D - (k-1)\cdot P$ (čo je vlastne $P$)

zapíšeme $(k-1)H$ do skrátenej postupnosti

Tento postup spraví jeden krok nášho postupu. Budeme ho preto opakovať až kým sa čísla $P$ a $D$ nebudú rovnať. Všimnite si naviac, že v každom kroku sa zmení to, ktoré číslo je väčšie, takže naša skrátená postupnosť bude striedať hlavy a znaky.

Tento postup vieme samozrejme zapísať aj v ľubovoľnom programovacom jazyku. Skúste si pozrieť nižšie uvedenú implementáciu v Pythone. Zistíte, že sa veľmi podobá tomu, ako sme si to zapísali pred chvíľou.

print("Napis prve cislo:")
P = int(input())                                    # napr. číslo 111
print("Napis druhe cislo:")
D = int(input())                                    # napr. číslo 9

zoznam = []                                         # tu zapisujeme skrátenú postupnosť
while P != D:                                       # kým sa čísla P a D nerovnajú opakuj
    print(P,D)
    if P > D:
        k = P // D # celočíselné delenie
        if P % D != 0:  # číslo P nedáva po delení D zvyšok 0, nie je ním teda deliteľné
            P = P - k*D
            zoznam.append((k, 'Z'))
        elif P % D != 0:  # zvyšok je 0, P je deliteľné D
            P = P - (k-1)*D
            zoznam.append((k-1, 'Z'))
    elif D > P:
        k = D // P # celočíselné delenie
        if D % P != 0: # číslo D nie je deliteľné P 
            D = D - k*P
            zoznam.append((k, 'H'))
        elif D % P == 0:  # číslo D je deliteľné P
            D = D - (k-1)*P
            zoznam.append((k-1, 'H'))

# keďže zisťujeme ťahy odzadu, tak musíme zoznam obrátiť
zoznam.reverse()
print("Skrateny zoznam hodov:", zoznam)             # [(2, 'H'), (12, 'Z')]

# vypiseme aj zaciatocne cislo
print("Rano dostala Dasa cisla rovne hodnote:", P)  # 3

Je to dostatočne rýchle?

Pokúsme sa zamyslieť nad tým, koľkokrát musíme zopakovať vyššie uvedený postup. V jednom kroku sa rozhodneme, ktoré z čísel $P$ a $D$ je väčšie a toto väčie číslo upravíme, pričom bude menšie ako druhé číslo. Takže to, ktoré číslo je väčšie, sa bude v každom kroku striedať. Ak je najskôr $P > D$, tak hneď potom bude $P < D$, následne opäť $P > D$, a tak ďalej až kým $P = D$.

Pri každom tomto kroku vložíme do skrátenej postupnosti jeden záznam, teda jedno číslo a hod $Z$ alebo $H$. Trvanie nášho programu bude teda priamo úmerné dĺžke skrátenej postupnosti. Stále však nevieme, aká dlhá bude táto postupnosť a či to náš algoritmus zvládne aj pre čísla veľkosti milión.

Pozrime sa bližšie na to, ako sa mení číslo $P$. V každom druhom kroku sa veľkosť tohto čísla zmenší, keďže hodnoty $P$ a $D$ sa zmenšujú nastriedačku. Ako rýchlo sa toto číslo zmenšuje? Ak by sa v každých dvoch krokoch zmenšilo iba o 1, tak je to zlé. Pretože naša skrátená postupnosť by potom mala dĺžku $2\cdot P$, čo je veľa. Môže sa však číslo $P$ zmenšiť o tak málo? Skúste nájsť takú dvojicu $P$ a $D$, že po úprave čísla $P$ sa toto číslo zmenší iba o 1.

V skutočnosti totiž platí, že hodnota čísla $P$ sa musí pri jednej úprave zmenšiť aspoň na polovicu. Ukážme si, prečo je to tak. Všimnite si, že číslo $P$ sa mení v závislosti od čísla $D$. Dokonca sme si ukázali, že výsledná hodnota $P$ musí byť po úprave menšia ako hodnota $D$. Ak je teda číslo $D$ malé, bude malá aj nová hodnota $P$. Nová hodnota $P$ preto bude aspoň polovičná ak platí, že $D \leq \frac{P}{2}$ – číslo $D$ je menšie ako polovica $P$ a preto aj $P$ bude po úprave menšie ako jeho polovica.

Čo však v prípade, keď $D > \frac{P}{2}$? Pozrime sa na to, čo spraví náš algoritmus. Najskôr zistí, koľkokrát sa do čísla $P$ zmestí číslo $D$. Odpoveďou je raz, pretože $D$ je väčšie ako polovica $P$, takže dvakrát sa tam nezmestí. V ďalšom kroku sa od $P$ jedenkrát odpočíta číslo $D$. No a výsledok musí byť menší ako polovica $P$. Ak totiž máte číslo $P$ a zoberiete z neho viac ako jeho polovicu (číslo $D$), ostane vám menej ako polovica (nová hodnota $P$).

Tým pádom sa po každých dvoch krokoch hodnota čísla $P$ zmenšila aspoň na polovicu. Čo sa stane, ak bude číslo $P$ milión? V najhoršom prípade sa toto číslo zakaždým zmenší presne na polovicu až kým z neho neostane číslo 1, čo je najmenšie číslo, s ktorým Dášenka mohla začínať.

$$1000000 / 2 = 500000 / 2 = 250000 / 2 = 125000 / 2 = 62500 / 2 = 31250 / 2 = 15625 / 2 \doteq 7812 / 2 = 3906$$ $$3906 / 2 = 1953 / 2 \doteq 976 / 2 = 488 / 2 = 244 / 2 = 122 /2 = 61 / 2 \doteq 30 / 2 = 15 / 2 \doteq 7 / 2 \doteq 3 / 2 \doteq 1$$

Predošlý zápis znázorňuje, ako by sa hodnota $P$ zmenšovala¹. Vidíme, že na to, aby sme z nej dostali 1 potrebujem iba 19 krokov. Samozrejme, nezabudnime, že hodnota $P$ sa zmení iba v každom druhom kroku, niekedy sa totiž musí zmenšovať aj $D$. Stále z toho však vychádza, že nám stačí 38 krokov. A aj to iba v najhoršom možnom prípade.

Pre zaujímavosť, číslo 19 – koľkrát môžme vydeliť číslo $1\,000\,000$ číslom 2 – je aj približná hodnota dvojkového logaritmu z čísla $1\,000\,000$. Logaritmovanie je v podstate opak umocňovania.

Keď chceme skrátene zapísať súčin veľa dvojok, tak to môžme skrátene napísať pomocou umocnenia: $$2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2 = 2^8$$

Poprípade súčin $k$ dvojek je $2^k$.

Logaritmom sa označuje odpoveď na otázku: Na koľkú musíme umocniť číslo 2, aby sme dostali výsledok $y$? Ak by sme teda chceli zistiť, na koľkú treba umocniť 2, aby sme dosali číslo 256 (teda hľadáme $x$ rovnice $2^x = 256$), tak odpoveďou by bol práve $\log_{2}(256)$, čo je 8.

O našom postupe by sme preto mohli povedať, že potrebuje najviac $2\cdot \log_{2}P$ krokov.

Podúloha d)

Vedeli by ste dokázať, že počiatočné číslo $p$ delí obe výsledné čísla $P$ a $D$?

Začať môžeme tým, že sa vrátime ku konkrétnym príkladom z úloh a) a b). Všimnime si, že v oboch prípadoch platí, že číslo $p$ nedelí len výsledné čísla $P$ a $D$, ale všetky čísla, ktoré si Dášenka zapísala. V podúlohe a) vidíme iba násobky čísla 5, v podúlohe b) iba násobky čísla 3. To je podozrivé.

Pozrime sa teda, čo sa deje keď Dášenka začne hádzať mincou. Začína s dvoma číslami $p$ a $d$, ktoré sú rovnaké, a teda zjavne sú obe deliteľné číslom $p$. Po prvom hode mincou môže mať Dášenka zapísané čísla $2p$ a $p$, ktoré sú opäť deliteľné číslom $p$. Po druhom hode mincou má buď dvojicu $3p$ a $p$, alebo dvojicu $2p$ a $3p$, čo sú všetko násobky $p$.

No a táto vlastnosť sa nezmení. Čo totiž robí Dášenka? Jedno číslo nahradí súčtom a druhé nechá nezmenené. Ale ak sčítame dve čísla deliteľné číslom $p$, tak opäť dostaneme číslo deliteľné $p$. Skúsme si to ukázať o niečo formálnejšie. Číslo deliteľné $p$ si vieme zapísať ako $a\cdot p$ pre nejaké kladné $a$. Zoberme si teda ľubovoľné dve čísla deliteľné $p$, ktoré vieme zapísať ako $a \cdot p$ a $b \cdot p$. Ich súčet je $a\cdot p + b\cdot p = (a + b)\cdot p$. Tento súčet je ale zjavne opäť deliteľný číslom $p$, lebo sa dá zapísať ako $c\cdot p$, pre $c = a + b$.

Keďže Dášenka začína s dvoma číslami deliteľnými číslom $p$ (dvojica $p$, $d$) a robí iba operáciu sčítanie, všetky čísla, ktoré zapisuje sú naďalej deliteľné číslom $p$. Tým pádom to platí aj pre výsledné čísla $P$ a $D$.

Podúloha e)

Vedeli by ste dokázať, že ak nejaké číslo $x$ delí obe výsledné čísla $P$ a $D$, tak delí aj pôvodné číslo $p$?

Skúsme postupovať podobne ako v podúlohe d). Zoberme si číslo $x$, ktoré delí aj $P$ aj $D$. Tieto dve čísla sa teda dajú zapísať ako $P = a\cdot x$ a $D = b \cdot x$, pre vhodné $a$ a $b$. Čo sa s týmito číslami dialo krok pred tým? V podúlohe a) sme si ukázali, že hodnoty predchádzajúcich čísel získame tak, že menšie číslom nezmeníme a od väčšieho to menšie odčítame. Tvárme sa teda, že $P > D$, pre opačný prípad by sme robili to isté, akurát naopak.

Hodnota $D$ ostane rovná $b \cdot x$, ale hodnota $P$ sa zmení na rozdiel týchto dvoch čísel. Bude preto platiť, že $P = a\cdot x - b\cdot x$. To však vieme zapísať ako $P = (a-b)\cdot x$. Nová hodnota čísla $P$ bude teda opäť deliteľná číslom $x$.

Naviac, táto vlastnosť platí všeobecne a vyššie máme uvedený aj jej dôkaz. Ak si zoberieme dve čísla deliteľné $x$, tak ich rozdiel bude opäť deliteľný číslom $x$. Pri našom postupe teda budeme celý čas pracovať s číslami, ktoré sú deliteľné číslom $x$. To bude platiť aj keď sa na konci našeho postupu dostaneme k číslam $p$ a $d$. Ak teda číslo $x$ delí výsledné čísla, delí aj začiatočné $p$.

Čo vyplýva z vlastností d) a e) o čísle $p$?

V podúlohe d) sme ukázali, že číslo $p$ delí obe čísla $P$ a $D$. Takúto hodnotu označujeme ako spoločný deliteľ. Podúloha e) zase hovorí, že každý spoločný deliteľ $x$ čísel $P$ a $D$ delí aj číslo $p$. Z toho ale vyplýva, že $x \leq p$. Uvedomme si, že ak nejaké číslo $a$ delí číslo $b$, tak $b$ musí byť väčšie alebo rovné $a$.

Ak je teda každý spoločný deliteľ menší alebo rovný ako $p$ tak to značí, že $p$ je najväčší spoločný deliteľ čísel $P$ a $D$.

Na záver

V tejto úlohe sme teda celý čas počítali najväčšie spoločné delitele dvoch čísel. A postup, ktorý ste počas toho vymysleli sa volá Euklidov algoritmus a je to najrýchlejší spôsob ako túto hodnotu vypočítať.

Viac o Euklidovom algoritme si môžete prečítať na Wikipédii (https://sk.wikipedia.org/wiki/Euklidov_algoritmus). Jediný rozdiel s naším riešením je ten, že klasický Euklidov algoritmus skončí, keď je jedno z čísel rovné nule a nie keď sú rovnaké. Vďaka tomu netreba špeciálne ošetrovať podmienku deliteľnosti čísla $P$ číslom $D$.