Kategórie:
5
6
7
8
9

Zadanie

Puding vyzerá ako mriežka n \times n, kde n je nepárne. Ideme ho zdobiť piškótami. Najskôr do ľavého horného rohu dáme jednu piškótu. Potom budeme pokračovať opakovaním nasledovných krokov:
  1. Posunieme sa o dve políčka doprava, a o jedno políčko dole. Ak by sme mali vyjsť z okraja mriežky, znova do nej vojdeme na opačnej strane.
  2. Ak stojíme na políčku, na ktorom už sú nejaké piškóty, posunieme sa ešte raz, ale tentokrát o dve políčka doľava a o jedno políčko dole.
  3. Nakoniec na políčko, na ktorom stojíme, položíme o jedna viac piškóty, ako sme dali naposledy.

Takýmto spôsobom celú mriežku zaplníme všetkými počtami piškót od 1 do n^2. Dokážte, že keď skončíte, počet piškót v každom riadku a stĺpci bude rovnaký.

Na obrázkoch môžete vidieť, ako v mriežke 3 \times 3 vyplníme prvé tri políčka a ako vyplníme to štvrté.

Poznámka/dovysvetlenie: Ak v prvom kroku urobíme krok doprava von z mriežky, posunieme sa na prvé políčko z ľava v danom riadku. Podobne sa presunieme navrch pri kroku von z tabuľky smerom dole.

Vzorové riešenie

Opravovali: Imro, MichalImrisek

Zadanie sa môže na prvý pohľad zdať dlhé a zložité, no po chvýli skúšania je možné si všimnúť opakújuci sa vzor, ktorý je kľúčom k riešeniu. Poďme to teda rozlúštiť.

Nazvime krok o jedna dolu a o dve doprava ako obyčajný. Všimnime si, že obyčajným krokom stúpim z políčka A na políčko B, kde už sú piškóty, tak pôvodne sme tieto piškóty museli umiestniť iným než obyčajným spôsobom. Totiž, ak by sme ich pôvodne na B umiestnili obyčajným spôsobom znamenalo by to, že tento krok začínal v A. To by však znamenalo, že v A už tiež musia byť piškóty a teda by sme z neho nemohli spraviť obyčajný krok.

Po n obyčajných ťahoch z políčka X sa opäť dostaneme na políčko X keďže sa spolu pohneme o 2n vpravo a o n nadol. Prejdeme teda cez každý riadok nakoľko n je nepárne a teda je nesúdeliteľné s 2. Na n-tý ťah skočíme na riadok, na ktorom je X. Taktiež skočíme na stĺpec, kde je X, lebo sa pohneme o n nadol. Čiže na každý stĺpec skočím práve raz, nakoľko po vyskočení z tabuľky sa vrátime naspäť. Keď teda začneme v ľavom hornom rohu, po n ťahoch skočíme na toto isté políčko. Po ceste neskočíme na žiadne piškóty a to preto, lebo žiadne iné políčko nebude mať piškóty vložené inak ako po obyčajnom ťahu.

Následne spravíme neobyčajný ťah o dve vľavo a jedno dole a skončíme na políčku Y. Teraz je jediné políčko s piškótami na ktoré môžeme skočiť Y, keďže na všetky ostatné zaplnené políčka sme sa už pohli obyčajným ťahom. Spravíme teda ďaľších n obyčajných ťahov a ocitneme sa na políčku Y. Opäť teda vykonáme neobyčajný ťah a tým začneme nový cyklus. Pod pojmom cyklus myslíme n po sebe idúcich obyčajných ťahov, ktoré začínajú aj končia na rovnakom poličku. Ako sme už vyššie ukázali takýto cyklus prechádza cez každý riadok aj každý stĺpec práve raz. Prvý cyklus začína v ľavom hornom rohu.

Už sme takéto cykly spravili dva a vždy keď sa po skončení cyklu pohneme, bude to začiatok nového, keďže potom urobíme n obyčajných krokov späť na toto políčko. Takýchto cyklov bude n, keďže v každom cykle uložím piškóty na n políčok a tých je celkovo n^2.

Začiatky cyklov sa hýbu vždy o jedno políčko dole a o dve doľava. Tým pádom bude jeden začiatok cyklu v každom riadku a v každom stĺpci. To preto, lebo 2 je nesúdeliteľné s n, keďže n je nepárne.

V k-tom cykle umiestnime postupne na políčko na začiatok cyklu (k-1) \cdot n +1 piškôt, na druhé políčko (k-1) \cdot n +2, na tretie (k-1) \cdot n +3 a tak ďalej. Až na n-té políčko cyklu umiestnime (k-1) \cdot n + n piškôt. Prvý cyklus začína na políčku vľavo hore. Počas jedného cyklu pridáme do každého riadku aj každého stĺpca (k-1) \cdot n piškôt a do každého z nich potom pridáme počet piškôt podľa toho koľkaté je dané políčko v cykle. Nás bude zaujímať práve tento zvyšok, keďže všetko ostatné je rovnaké pre každý riadok aj každý stĺpec.

Všimnime si, že každý riadok/stĺpec bude v jednom cykle prvý, v jednom cykle druhý, v jednom cykle tretí atď až v jednom cykle n-tý. Teda súčet zvyškov v každom riadku/stĺpci bude rovnaký. Preto aj súčet každého riadku/stĺpca bude rovnaký.

Komentár

Väčšina z vás si správne všimla ako sa správajú cykly no po väčšine ste nedokázali, že vrámci cyklu nenarazíme na žiadne políčko (okrem začiatočného políčka cyklu) kde už boli piškóty predtým.