*Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Baške na *

“Dášenka, pamätáš si ako som ťa učil počítať?”, pýta sa ocko Bob.

“Áno. Nula, jeden, dva, tri, štyri až po veeeeľmi veľa.”, odpovedá malá Dáša s úsmevom.

“Tak dnes ti ukážem hru, ktorú sa s tými číslami môžeš hrať.”

“Jéj, ďalšia hra. Aké sú pravidlá?”

“Každé ráno odo mňa dostaneš dve rovnaké nenulové čísla. Potom si vezmeš túto mincu, a budeš si ňou hádzať. Vždy keď hodíš hlavu, pripočítaš prvé číslo k druhému a na papier si zaznačíš H. Keď hodíš znak, tak pripočítaš druhé číslo k prvému a na papier si zaznačíš Z.”

“Môžeš mi to ukázať na príklade?”

“Samozrejme. Začnem napríklad s dvoma štvorkami. Povedzme že som hodil postupne znak, hlava, znak a znak. Aké budú výsledné čísla?”

Dášenka sa zamyslela, zobrala si papier a začala sčítavať. Nakoniec vyhlásila: “Tridsať dva a dvanásť!”.

Bob si pozrel jej papier a našiel tam nasledovnú tabuľku:

“Správne. Na konci dňa mi potom donesieš ukázať aj postupnosť znakov, aj výslednú dvojicu čísel, dobre?”

To ho už ale Dášenka poriadne nepočúvala. Začala si mincu hádzať a pokračovala sčítavaním 32 a 12.

“Ešte jedna vec, kým dávaš pozor. Aby si sa neupísala do zbláznenia, tak ak hodíš viacero rovnakých znakov za sebou, tak stačí ak napíšeš číslo, koľkokrát to bolo, a písmenko Z alebo H. Teda náš príklad by sa dal zapísať ako 1Z,1H,2Z. Dobre?”

“Áno oci.” a už jej nebolo.

Ďalší deň

Na druhé ráno dostala Dášenka od Boba dve rovnaké čísla a celý deň si hádzala mincou.

Avšak večer prišla za svojím ockom celá nešťastná, lebo stratila všetky svoje výpočty, a s nimi aj začiatočné dve čísla a postupnosť hodov. Jediné čo jej ostalo boli výsledné dve čísla.

Nanešťastie si ani Bob už nepamätá čísla, ktoré jej ráno zadal. Obrátil sa preto na vás:

“Ahojte PRASKáči. Vedeli by ste z posledných dvoch čísel zistiť, ktoré čísla som zadal ráno Dášenke a ako vyzerala celá postupnosť hodov? Alebo to už nejde?”

Úloha

Tak si to zhrňme. Na začiatku máme čísla $p$ a $d$, ktoré sú rovnaké a kladné. Postupne s nimi robíme operácie dvoch typov:

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

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

Potom, ako sme spravili niekoľko takýchto operácií, sme získali nejaké dve čísla $P$ a $D$. V prvých troch podúlohách je vašou úlohou zistiť (ak je to možné) začiatočnú hodnotu čísel $p$ a $d$. Okrem toho zistite aj postupnosť hodov mince v skrátenom formáte.

Skrátený formát je postupnosť dvojíc: číslo a písmenko (Z alebo H). Číslo je vždy kladné väčšie ako nula, a hovorí koľkokrát po sebe Dášenka hodila konkrétnu stranu mince. V rámci tejto skrátenej postupnsoti sa vždy strieda hlava a znak, takže nemôže nastať napríklad takýto prípad: $$3Z,5H,7Z,6Z,8H,1Z,5H$$ pretože by sme to vedeli skrátiť a prepísať $7Z,6Z$ na $13Z$.

Táto úloha sa skladá z niekoľkých podúloh:

1. (2 body) Dášenka doniesla Bobovi čísla $P=15$ a $D=35$. Viete zistiť postupnosť hodov a hodnotu čísel $p$ a $d$, ktoré ráno od Boba dostala? Poprípade vysvetlite Bobovi, že sa to už zistiť nedá.

2. (2 body) Ak by Dášenka doniesla Bovovi čísla $P=111$ a $D=9$, vedeli by ste zistiť postupnosť hodov a hodnotu počiatočných čísel $p$ a $d$?

3. (5 body) Vedeli by ste riešiť takýto problém pre ľubovoľnú dvojicu čísel $P$ a $D$? Popíšte postup, ktorý z dvoch čísel $P$ a $D$ zistí počiatočné čísla $p$ a $d$ a tiež skonštruuje skrátenú postupnosť hodov.

Snažte sa, aby bol váš postup dostatočne rýchly. Vzorové riešenie by vedelo len s pomocou papiera a pera vypočítať výsledok aj pre čísla $1\,000\,000$ a $14$, poprípade pre ľubovoľnú dvojicu čísel veľkých až milión.

4. (3 body) Vedeli by ste dokázať, že počiatočné číslo $p$ delí obe konečné čísla $P$ a $D$?

5. (3 body) 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$?

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