8. príklad - Vzorové riešenie

Rozdeľme možný počet kráľovstiev na dva prípady: Keď je ich počet párny a keď je nepárny. Pre každú časť zistíme samostatne, ktoré takéto čísla mohli byť počtom kráľovstiev.

Začnime prípadom, keď je počet kráľovstiev párny. Môžeme si vyskúšať, ako sa Anka bude pohybovať, a všímať si, ktorými kráľovstvami prechádza. Zaujímavé pozorovanie je, že s výnimkou prvého kráľovstva sa Anka pohybuje iba po kráľovstvách s párnymi číslami. Prečo je to tak? Pretože vždy, keď je na kráľovstve číslo napríklad x, tak sa posunie o x kráľovstiev dopredu, teda na kráľovstvo číslo 2x. Toto číslo musí byť zjavne párne, keďže je násobkom dvoch. Ešte sa môže stať, že pri tejto ceste prejde cez kráľovstvo číslo n a vráti sa na 1 (môže sa to stať nanajvýš raz, pretože inak by to znamenalo, že prešla viac ako n kráľovstvami, a to by musela ísť z kráľovstva s číslom vyšším ako n). V tomto prípade sa číslo Ankinho kráľovstva znížilo o n-1 namiesto toho, aby sa zvýšilo o 1, teda vlastne “stratila” n krokov. To znamená, že skončí nie na kráľovstve 2x, ale 2x-n. Keďže n je párne, tak táto hodnota bude, rovnako ako 2x, tiež párna.

To ale znamená, že jediné kráľovstvo s nepárnym číslom, ktoré Anka navštívi, je 1. Teda ak existuje aj nejaké iné nepárne kráľovstvo, napríklad 3, tak Anka už logicky nemôže navštíviť všetky. Teda jediný vyhovujúca párny počet kráľovstiev je 2.

Čo nepárne čísla? Môžeme si všimnúť, že pri takýchto počtoch kráľovstiev už Anka vie stúpiť aj na nepárne kráľovstvá. Stále ale existuje kráľovstvo, do ktorého určite nikdy nevstúpi. Je to posledné kráľovstvo, ktorého číslo je n. Už sme spomenuli, že z kráľovstva x sa Anka vždy dostane iba do kráľovstva číslo 2x alebo 2x-n. Môže sa niektorej z týchto hodnôt rovnať nepárne n? 2x to nebude, keďže to je vždy párne. Stále ale pripadá do úvahy 2x-n. Môžeme v rovnici zapísať, že je to rovné n, a následne ju upraviť:

Teda vidíme, že jediný spôsob, akým Anka môže pricestovať do kráľovstva číslo n, je, že v tomto istom kráľovstve svoj pohyb aj začína, ale z iného kráľovstva sa tam nikdy nedostane.

Toto znamená, že pri nepárnych n Anka môže navštíviť posledné kráľovstvo iba tak, že v ňom aj začína, teda vyhovuje iba n = 1.

Teda dostávame dve riešenia: 1 a 2. Ľahko si overíme, že tieto riešenia naozaj fungujú.

Odpoveď: Úloha má dve riešenia: 1 a 2.

Bodovanie:

Za každé nájdené a skontrolované riešenie sme dávali 1 bod, 3 body za vyriešenie párnych prípadov a 5 bodov za vyriešenie nepárnych prípadov.