2. Príbeh o Dášenke a minci

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\)?