Odporúčaný článok

Adventný Logboj - Adventný Logboj je individuálna súťaž v riešení logických úloh, v ktorej môžu súťažiť základoškoláci, stredoškoláci aj starší. Na stránke súťaže bude každý decembrový deň až do vianoc sprístupnená jedna úloha, … Prejsť na článok

×

10. príklad - Vzorové riešenie

Kategórie:
5
6
7
8
9

Zadanie

Mapa je zapísaná ako postupnosť čísel, pričom prvé 4 čísla sú 1, 2, 3 a 4 v tomto poradí. Každé ďalšie číslo je cifra na mieste jednotiek súčtu predošlých 4 čísel. Napríklad piate číslo v poradí bude 0, lebo 1 + 2 + 3 + 4 = 10 a tá má na mieste jednotiek 0. A tak ďalej. Hrdinovia však potrebujú vedieť, či sa v postupnosti niekde nachádzajú za sebou čísla 2, 3, 5, 7, a či sa čísla 1, 2, 3, 4 nachádzajú za sebou aj niekde inde ako na začiatku postupnosti. Zistite odpovede na tieto otázky.

Vzorové riešenie

Opravovali: Red, erik
Zopakuje sa 1, 2, 3, 4?

Vidíme, že v postupnosti sú dôležité štvorice po sebe idúcich čísel, lebo na základe nich vieme, ako bude postupnosť pokračovať. Namiesto toho, aby sme sa pozerali na jednotlivé členy postupnosti osobitne, pozrime sa teda na postupnosť týchto štvoríc. Prvá štvorica je (1, 2, 3, 4), ako nám hovorí zadanie. Ďalšia štvorica bude začínať 2, 3, 4 a nakoniec v nej bude nasledujúce číslo v postupnosti, čo je 0. Druhá štvorica teda bude (2, 3, 4, 0), tretia (3, 4, 0, 9), a tak ďalej.

Každú štvoricu v postupnosti vieme jednoznačne určiť zo štvorice, ktorá je v postupnosti pred ňou. Keď máme štvoricu (a, b, c, d) a za ňou (b, c, d, e), tak e = a + b + c + d - k \cdot 10, kde k si vyberieme tak, aby bolo 0 \leq e < 10 (čiže máme iba jednu možnosť). Z toho vyplýva ďalšia dôležitá vec: z každej štvorice vieme jednoznačne určiť, aká štvorica musí byť v postupnosti pred ňou. Poslednú rovnicu si vieme upraviť na a = e - b - c - d + k \cdot 10, kde k je znova jednoznačne dané.

Rôznych štvoríc je len konečne veľa, takže sa nám niekedy v postupnosti musí vyskytnúť taká, ktorá tam už bola predtým. Pozrime sa na prvú takúto (zopakovanú) štvoricu, ktorá sa v postupnosti vyskytne. Štvorica pred ňou musí byť rovnaká ako štvorica pred jej prvým výskytom. To ale nemôže byť, lebo potom by táto štvorica nebola prvá v poradí, čo sa zopakuje. Prvý výskyt tejto štvorice teda musí byť na začiatku postupnosti, aby pred ním nebola žiadna ďalšia štvorica, a tým pádom to musí byť (1, 2, 3, 4). To znamená, že 1, 2, 3, 4 sa v postupnosti určite zopakuje.

Bude tam 2, 3, 5, 7?

Nič nenasvedčuje tomu, že by tam zrovna takáto štvorica mala byť, poďme teda skúsiť dokázať, že nebude. Asi by bolo ťažké vylúčiť práve túto konkrétnu štvoricu, tak na nej môžeme skúsiť nájsť nejakú všeobecnejšiu vlastnosť, o ktorej budeme vedieť, že ju štvorice v postupnosti nemôžu mať.

Postupnosť si môžeme zjednodušiť napríklad tak, že sa budeme pozerať len na paritu čísel v nej. Vďaka parite po sebe idúcich čísel vieme určiť aj paritu nasledujúceho. Postupnosť teda bude vyzerať takto (0 znamená párne, 1 nepárne):

\displaystyle 1, 0, 1, 0, 0, 1, 0, 1, 0, \dots

Vidíme, že sa nám rýchlo zopakuje štvorica (1, 0, 1, 0), takže odvtedy sa bude v postupnosti opakovať stále to isté. Pritom (2, 3, 5, 7) má parity (0, 1, 1, 1), a to sa v tejto postupnosti nenachádza. V pôvodnej postupnosti sa teda takisto nemôže nachádzať ani 2, 3, 5, 7.

Komentár

Veľa z Vás, vyriešilo príklad vypisovaním, či už manuálnym alebo za pomoci programovania. Musím preto pochváliť tých, ktorí sa rozhodli riešiť príklad práve matematicky.