Zadanie

Hneď prvý prípad agenta \(\check F\) sa týkal nejakého šialenca, ktorý tvrdil, že ho uniesli mimomarťania a vo svojej „lietajúcej rakete“ ho pokreslili. Neznelo to veľmi vierohodne, ale dotyčný bol skutočne pokreslený. A tie zvláštne symboly... Úlohou Marťanov v modrom však bolo zabrániť akýmkoľvek rečiam, preto nemal agent \(\check F\) inú možnosť ako (napriek osobnému presvedčeniu) vymazať svojmu spoluobčanovi pamäť. Na to využije pamäťovú gumu, ktorá vojde jedným uchom dnu a druhým von...

Nech \(m\) je kladné celé číslo. Pamäť je nekonečná postupnosť \(a_1, a_2, a_3, \ldots\), v ktorej \(a_1\) je kladné celé a pre každé \(n \geq 1\) platí \[a_{n+1} = \begin{cases}a_n^2+2^m & \text{ak } a_n< 2^m, \\ a_n/2 &\text{ak } a_n\geq 2^m.\end{cases}\] Pamäťová guma však vymaže len celé spomienky. Preto vzhľadom na \(m\) určte všetky \(a_1\), pre ktoré je každý člen postupnosti celé číslo.

Kým je naše aktuálne \(a_n \geq 2^m\), tak ho delíme dvomi, a zaujíma nás, či takto ostaneme pri celých číslach. Chceme si teda rozložiť \(a_n\) na \(2^kb\), kde \(b\) je nepárne. Postupnosť potom bude vyzerať tak, že keď spravíme prvý krok, tak sa nám môžu zmeniť \(k\) aj \(b\), ale potom sa iba \(k\) postupne zmenšuje o \(1\), až kým nie je zase \(2^kb < 2^m\). Necelé čísla nám pri tom vyjdú práve vtedy, keď je \(b > 2^m\).

Zaujíma nás teda, čo sa deje s \(b\) pri prvom kroku. Ďalší člen postupnosti bude \(2^{2k}b^2 + 2^m\). Na oboch stranách máme mocniny dvojky, takže by sme ich chceli vybrať pred zátvorku, ale nevieme, ktorá z nich je väčšia. Preto rozoberieme prípady:

  • Ak \(2k < m\), potom \(2^{2k}b^2 + 2^m = 2^{2k}(b^2 + 2^{m - 2k})\). Hodnota v zátvorke je nepárna, takže to bude naše nové \(b\).

  • Ak \(2k > m\), potom dostávame \(2^m(2^{2k - m}b^2 + 1)\), zase je hodnota v zátvorke nepárna.

Zatiaľ si môžeme všimnúť, že v oboch prípadoch sa nám \(b\) zväčší. Ak teda ostávame pri týchto prípadoch, tak určite niekedy dostaneme necelé čísla. Zostáva nám ešte jeden prípad:

  • Ak \(2k = m\), potom dostávame \(2^m(b^2 + 1)\), kde už zátvorka vpravo je párna, takže už nemôžeme použiť ten argument, čo predtým. Našťastie ale \(b^2 \equiv 1 \pmod 4\) (\(3\) nie je kvadratický zvyšok), takže \(4 \nmid b^2 + 1\), teda nové \(b\) bude \((b^2 + 1)/2\).

    To je tiež väčšie ako \(b\) okrem prípadu, keď \(b = 1\).

Ak je teda v nejakom momente \(b > 1\), potom sa už bude len zväčšovať, a teda niekedy dostaneme necelé číslo. Ak \(b = 1\), potom ďalšie číslo postupnosti bude \(2^{2k} + 2^m\). Aby toto malo stále nepárnu časť \(1\), musí byť \(2k = m\). Tým dostaneme nejakú mocninu dvojky, ktorú budeme deliť dvomi, až kým sa nedostaneme na \(2^{m - 1}\). Potom zase aplikujeme prvý krok. Aby sme zase dostali mocninu dvojky, musí byť aj \(2(m - 1) = m\).

Jediná možnosť je teda \(m = 2\). V tomto prípade môžeme začať s ľubovoľným \(2^k > 1\), vždy sa takto dostaneme ku \(2\) a odtiaľ znovu na \(8\), takto teda vždy ostaneme pri celých číslach. Vo všetkých ostatných prípadoch začnú byť čísla niekedy necelé.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.