Zadanie
Malý Janko sa vozí na kolotoči, ktorý má \(n\) sedadiel usporiadaných do kruhu. Vozí sa \(n\) jázd. Po každej jazde (okrem poslednej) si presadne v smere hodinových ručičiek o najviac \(n-1\) miest. Nájdite všetky kladné celé čísla \(n\), pre ktoré je možné, aby Janko v každej jazde sedel na inom mieste, pričom po každej jazde si presadne o iný počet miest. Nezabudnite zdôvodniť, prečo to pre ostatné \(n\) nie je možné.
V tejto úlohe je dôležité uvážiť, o koľko sedadiel sa celkovo vo všetkých presadnutiach Janko posunie a následne zistiť, či a ako je možné posuny realizovať.
Janko sa presunie zo sedačky na inú po každej z jázd od \(1\) po \(n-1\), vždy o iný počet sedadiel. Z toho vyplýva, že sa musí práve raz presunúť o \(1\) miesto, práve raz o \(2\) miesta a takto až po \(n-1\) miest. Celkovo sa teda pred \(n\)-tou jazdou posunie o \[1+2+...+(n-1) = \dfrac{n\cdot(n-1)}{2}\] sedadiel. Podmienkou v zadaní je, že po \((n-1)\)-vej jazde musí Janko sedieť na inej sedačke ako na začiatku. Ukážeme si, že pre niektoré čísla bude sedieť opäť tam, kde začínal (tie budeme môcť vylúčiť).
Rozdeľme si čísla na dve skupiny: nepárne a párne. Pre nepárne \(n\) platí, že \(\frac12(n-1)\) je celé číslo, teda \(\frac12n\cdot(n-1)\) je celočíselný násobok \(n\). To znamená, že po \((n-1)\)-vej jazde by Janko musel nutne sedieť na sedadle, kde začínal. Z toho ale vyplýva, že na jednom z \(n-1\) ostatných sedadiel určite nesedel. A to je problém, ak je \(n>1\), pretože nesplníme zadanie. V špeciálnom prípade \(n=1\), zjavne môže sedieť len na jedinom mieste, teda \(n=1\) spĺňa zadanie.
Pre párne \(n\) tento problém nevznikne, pretože \(\frac12(n-1)\) nie je celé číslo. Ukážeme si, že pre párne \(n\) Janko dokáže sedieť na kolotoči podľa zadania. Ide to napríklad takýmto spôsobom: Najprv sa Janko posunie o \(1\) sedadlo, potom o \(n-2\), čím sa dokopy dostane o \(1\) sedadlo proti smeru hodinových ručičiek od toho, kde začínal. Takto sú obsadené sedadlá naľavo aj napravo od počiatočného. Následne Janko pokračuje tak, že obsadí dvojicu miest, ktoré ohraničujú miesta, kde už predtým sedel. Postupne sa tak posúva o \(3,\, n-4,\, 5,\, n-6,\, \dots\) sedadiel a rozširuje tak miesta, na ktorých sedel doľava aj doprava, až kým nepríde k poslednému, na ktoré príde posunom o \(2\) sedadlá. Zjavne si takto posedí na každom zo sedadiel práve raz. Navyše využije posun každej dĺžky, pretože ak si všimneme, posuny o nepárne čísla pokryje v nepárnych jazdách od \(1\) až po \(n-1\) a posuny o párne čísla zase klesajúcou postupnosťou od \(n-2\) až po \(2\).
A to je všetko, pretože sme si ukázali, že pre párne \(n\) a jednotku zadanie splniť vieme a pre nepárne \(n\) nie.
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ť.