Zadanie
Toho večera v tmavom kúte hradu v hlavnom meste Al-Gebry sa chystala Mita Li na ďalšiu tajnú prácičku. Kvôli kontrolám po ceste si nemohla zobrať zbraň vcelku, no Mita bola skúsená a vedela, ako si zbraň zmontovať. Ak všetko klapne, Al-Gebra bude ráno potrebovať nového vládcu.
Ako rukoväť Mitinej zbrane slúži číslo \(r\) a ostrie má tvar čísla \(o\). Mita si samozrejme nezabudla svoj skrutkovač a kladivko. Pomocou skrutkovača dokáže z dvoch kladných celých čísel \(a\) a \(b\) zhotoviť dvojicu čísel \(\overline{ab}, \overline{ba}\), ktorou nahradí pôvodnú dvojicu čísel. Keď na čísla \(a, b\) použije kladivko, tak ich zmení na čísla \(a+b\) a \(|a-b|\).
Mita vie, že kráľ Horner disponuje štítom, cez ktorý preniknú iba zbrane, ktorých rúčka \(r\) aj ostrie \(o\) sú deliteľné číslom \(9\). Určte všetky dvojice kladných celých čísel \((x, y)\), z ktorých dokáže Mita zmajstrovať takúto zbraň.
Poznámka: Značením \(\overline{ab}\) rozumieme celé číslo zložené z cifier kladného celého \(a\), za ktorými sú napísané cifry kladného celého čísla \(b\).
Zaujíma nás iba, či budú tie čísla deliteľné deviatimi, takže sa nám stačí pozerať na zvyšky po delení \(9\). Nech máme dvojicu zvyškov \((a, b)\) (pričom bez ujmy na všeobecnosti to prvé číslo je väčšie alebo rovné ako to druhé), potom skrutkovačom dostaneme \((a + b, a + b)\)1 a kladivkom \((a + b, a - b)\), pričom zase to prvé číslo bude väčšie alebo rovné ako to druhé. Od tohto bodu už budeme hovoriť iba o zvyškoch a týchto nových operáciach. Ešte budeme hovoriť, že ak dosiahneme \((0, 0)\), tak sme vyhrali a ak sa to z nejakej dvojice nedá, tak sme prehrali.
Ak v nejakom bode použijeme skrutkovač, potom obe čísla budú rovnaké. Ďalej použitím skrutkovača sa dostaneme na \((2x, 2x)\). Použitím kladivka sa z \((x, x)\) dostaneme na \((2x, 0)\), potom skrutkovačom aj kladivkom na \((2x, 2x)\). Tým sa nezmení deliteľnosť deviatimi, takže ak \(x\neq 0\), tak už potom nevyhráme.
Ak zo začiatočnej dvojice použijeme iba kladivko, tak z \((a, b)\) dostaneme \((a + b, a - b)\) a potom \((2a, 2b)\). Keď to budeme robiť ďalej, tak sa teda dostaneme len k číslam \((2^ka, 2^kb)\) a \((2^k(a + b), 2^k(a - b))\). Po prvom použití skrutkovača potom dostaneme \((2^k(a + b), 2^k(a + b))\) alebo \((2^ka, 2^ka)\).
Vyhráme teda v prípade, že \(a\equiv 0\pmod 9\) alebo \(a + b\equiv 0\pmod 9\). Keďže násobenie \(2\) nám deliteľnosť deviatimi nezmení, v iných prípadoch nemôžeme vyhrať.
lebo \(10a\equiv a\pmod 9\) a \(10b\equiv b\pmod 9\).↩︎
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ť.