Odporúčaný článok

Anketa - Ahoj Rieškar, stalo sa ti niekedy, že si nerozumel zadaniam? Chcel by si v lete prísť na denný tábor? Sú nejaké akcie, ktoré by si chcel, aby sme robili častejšie? … Prejsť na článok

×

7. príklad - Vzorové riešenie

Kategórie:
5
6
7
8
9

Zadanie

Horský trollovia mali dohodnutú bojovú formáciu. Tou je tabuľka n \times n\, (n \ge 2), v ktorej je v jednotlivých políčkach postupne 1, 2, \ldots, n^2 trollov v tomto poradí (v prvom riadku je postupne 1, 2, \ldots , n trollov, v druhom riadku n + 1, n + 2, \ldots, 2n, atď.). V jednom kroku môžeme zvoliť ľubovoľné dve susedné políčka (t. j. také, ktoré majú spoločnú stranu), a ak je v nich spolu párny počet trollov, rovnomerne ich prerozdelíme medzi tieto dve políčka (aby ich bolo v oboch políčkach rovnako veľa). Najsilnejšia je formácia vtedy, keď je v každom políčku rovnako veľa trollov. Pre ktoré n vieme takúto formáciu dosiahnuť?

Vzorové riešenie

Opravovali: Paľo

Ako prvé si treba uvedomiť, že počet trollov sa nemôže touto priemerovacou operáciou zmeniť. To plynie z toho, že ak pôvodne je v dvoch políčkach x a y trollov, tak podľa popisu kroku je teraz v oboch políčkach p=\frac{x+y}{2} trollov, t.j. 2 \cdot p= x+y, teda sme zachovali počet.

To znamená, že počet trollov na začiatku je rovnaký, ako počet na "konci" - keď budú mať všetky políčka rovnako veľa. Na začiatku máme 1+2+3+ \ldots + (n^2-1) + n^2 trollov, čo je známy súčet, ktorý má hodnotu \frac{n^2 \cdot (n^2+1)}{2}. Teraz, počet políčok v tabuľke je n^2, čiže na každé políčko pripadá práve

\displaystyle \frac{n^2 \cdot (n^2+1)}{2 \cdot n^2} = \frac{n^2+1}{2}

trollov. Z tohto vyplýva, keďže v každom políčku sú vždy len celočíselné počty trollov, že n musí byť nepárne.

Teraz ale uvážme, pre prípad nepárneho n, rozloženie parity na začiatku. Ukážeme, že nevieme urobiť ani jeden krok a preto nepárne n je taktiež nevyhovujúce. Susediace čísla v riadku sa líšia o 1, čo znamená, že ich súčet je vždy x+(x+1)=2x+1, čo je nepárne a teda nemôžeme priemerovať. Inak povedané, dve po sebe idúce čísla sú vždy jedno párne a jedno nepárne, v súčte teda nepárne.

Po chvíli zamyslenia si môžeme všimnúť, že hodnota čísla hneď pod x je na začiatku práve o n viac, keďže tabuľka má n stĺpcov. Preto, ich súčet je x+(x+n)=2x+n. Toto je zjavne nepárne číslo, lebo n je nepárne.

Tým pádom, pre nepárne n je na začiatku súčet všetkých dvojích susediacich čísel nepárny - čo znamená, že nemôžeme nič priemerovať a nepohneme sa. Rovnovážny stav je nedosiahnuteľný.

Odpoveď: Najsilnejšiu formáciu nevieme dosiahnuť iba popísaným priemerovaním pre žiadne n \geq 2.

Komentár

Väčšina ste sa popasovali s touto úlohou dobre. Dôležitý krok - ktorý bol skoro jasný a preto sme zaň nestrhávali body -, ktorí ste viacerí nespomenuli, bol, že počet trollov sa nemení po priemerovaní dvoch susedných políčok.

Niektorí ste mali jednu alebo obe časti zdôvodnenú neporiadne a podľa veľkosti nedostatku dôkazu ste strácali body.