Zadanie

Zanedlho po tom, ako začali prvotní ľudia formovať kmene a iné spoločenstvá objavil sa problém, ktorý dovtedy nemuseli riešiť. Nemali mená a nevedeli, ako sa oslovovať, čo vytváralo medzi súkmeňovcami nemalé problémy. Napríklad keď počas lovu niekto zakričal: „Hej ty tam, bacha, máš za chrbtom šabľozubého tigra!“ a otočili sa všetci, aj tí, ktorí mali tigra pred sebou, tak to nebolo dvakrát príjemné...

Kmeňoví šamani teda prišli s nápadom dávať ľuďom mená. Vymysleli spolu vyše \(40\) rôznych mien, zoradili celý kmeň do radu1 a súkmeňovci si začali zaradom dávať mená podľa nasledovných pravidiel:

  • Každý človek, ktorý stojí v rade na nepárnej pozícií sa volá „Kameň“.

  • Pre každé prirodzené číslo \(n\) platí, že každý človek, ktorý stojí v rade na pozícií \(n\) má rovnaké meno ako človek na pozícií \(4n\).

  • Pre každé prirodzené číslo \(n\) platí, že každý človek, ktorý stojí v rade na pozícií \(n\) má rovnaké meno ako aspoň jeden z ľudí na pozíciách \(n+2\) a \(n+4\).

Dokážte, že všetci sa volajú „Kameň“.

  1. Pre potreby úlohy je ľudí v našom kmeni nekonečne veľa, rovnako ako prirodzených čísel.↩

Pokúsme sa zistiť, kde sa v rade môže vyskytnúť človek, ktorý sa nevolá „Kameň“. Povedzme, že sa volá „Šuter“. Ak ukážeme, že takéto miesto nie je, budeme vedieť, že sa všetci volajú rovnako. Podľa prvej podmienky to bude na párnom mieste, keďže na nepárnom sa všetci volajú „Kameň“. Druhá podmienka zase vylúči možnosť, že by sa prvý „Šuter“ nachádzal na mieste deliteľnom \(4\). Keďže \(k\)-ta pozícia je pred \(4k\)-tou, tak \(k\)-ty človek sa volal „Kameň“ a \(4k\)-ty by tak bol ďalší „Kameň“.

Pre prvý „Šuter“ tak zostáva pozícia so zvyškom \(2\) po delení \(4\), zapíšeme ako \(4k+2\). Podľa tretej podmienky musí byť na mieste \(4k+4\) alebo \(4k+6\) tiež „Šuter“. Platí \(4k + 4 = 4(k + 1)\), preto sa \(4k+4\)-tý človek volá rovnako ako \(k+1\)-vý. Ten však stojí v rade pred \(4k+2\), preto sa volá „Kameň“. Človek \(4k+6\) teda musí byť „Šuter“.

Teraz vieme podľa tretej podmienky pokračovať ďalej. Keďže na pozícii \(4k+4\) je „Kameň“, tak na pozícii \(4k+6\) alebo \(4k+8\) musí byť ďalší „Kameň“. Ten teda bude na \(4k+8\). Ďalej \(4k+10\) bude „Šuter“ a takto sa budú striedať na párnych pozíciách do nekonečna. Za žiadnym „Kameňom“ totiž nemôžu na párnych pozíciách byť dvaja s menom „Šuter“ a naopak. Vidíme, že od pozície \(4k+2\) je každý štvrtý človek „Šuter“. Ostatní sú „Kameň“. To ale znamená, že každá pozícia deliteľná \(4\) je obsadená „Kameňom“. Pre každý „Šuter“ na pozícii \(n\) je tak na pozícii \(4n\) „Kameň“, čo je v rozpore s druhou podmienkou. Pre „Šuter“ tak nezostalo miesto a všetci sa volajú „Kameň“.

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ť.