Opravovatelia

Lukáš [email protected]

Noro [email protected]

Pri podobných úlohách sa často oplatí pozrieť sa na menšie prípady a z nich sa snažiť pochopiť, ako úloha funguje. Samozrejme, len to nestačí a musíme poriadne odôvodniť, že aj pri tých väčších sa to bude správať tak, ako tvrdíme, ale častokrát tak vieme pochopiť, čo sa deje.

Keby sme mali tabuľku $2\times 2$, v nej vieme znamienka priradiť len dvoma vyhovujúcimi spôsobmi – a to buď $+1-2-3+4=0$, alebo $-1+2+3-4=0$. V tomto prípade to teda celé funguje na tom, že $1+4=2+3$ a veľa nám to nepovedalo.

Skúsme sa ale pozrieť na tabuľku $4\times4$. Tam už počet možností, ako priradiť znamienka, je oveľa väčší. Pozrime sa na niektoré z nich.

$$\begin{array}{||r|r|r|r||r} \hline\hline +1 & +2 & -3 & -4 & -4\ \hline +5 & +6 & -7 & -8 & -4\ \hline -9 & -10 & +11 & +12 & 4\ \hline -13 & -14 & +15 & +16 & 4\ \hline\hline -16 & -16 & 16 & 16 & 0 \end{array} \qquad \begin{array}{||r|r|r|r||r} \hline\hline +1 & -2 & +3 & -4 & -2\ \hline -5 & +6 & -7 & +8 &-2\ \hline +9 & -10 & -11 & +12 &0\ \hline -13 & +14 & +15 & -16 & 0\ \hline \hline -8 & 8 & 0 & 0 &0 \end{array}$$

V týchto dvoch tabuľkách dostaneme v riadkoch vždy párne súčty a v stĺpcoch súčty deliteľné osmičkou. Ešte si overme, či sa niečo podobné deje aj pri tabuľke $6\times6$.

$$\begin{array}{||r|r|r|r|r|r||r} \hline\hline +1 & +2 & +3 & -4 & -5 & -6 & -9 \ \hline +7 & -8 & -9 & +10 & +11 & -12 & -1 \ \hline -13 & -14 & +15 & -16 & +17 & +18 & 7 \ \hline +19 & +20 & -21 & -22 & -23 & +24 & -3 \ \hline -25 & -26 & +27 & +28 & -29 & +30 & 5 \ \hline -31 & +32 & -33 & +34 & +35 & -36 & 1\ \hline \hline -42 & 6 & -18 & 30 & 6 & 18 & 0 \end{array}$$

Tu sú zas vo všetkých riadkoch súčty nepárne a pomerne malé, zatiaľ čo vo všetkých stĺpcoch násobkami $6$. Tie stĺpce vyzerajú pomerne podozrivo, tak sa poďme pozrieť na čísla v jednom stĺpci, teraz už však v zadanej tabuľke $8\times 8$.

V prvom stĺpci tabuľky $8\times8$ máme čísla $1, 9, 17, 25, 33, 41, 49, 57$. Tieto čísla sa postupne zväčšujú o $8$, pretože vždy ideme o celý riadok (a teda $8$ políčok) ďalej. To ale znamená, že čísla v jednom stĺpci tabuľky dávajú rovnaký zvyšok po delení ôsmimi. Keďže však polovici čísel z každého stĺpca pridáme $+$ a druhej polovici $-$, tieto rovnaké zvyšky sa navzájom odčítajú. Súčet v každom stĺpci teda bude násobkom $8$.

Z toho však vidíme, že každé číslo v tabuľke môžeme nahradiť najbližším menším násobkom čísla $8$. Tým zachováme súčty v stĺpcoch. Keďže súčet hodnôt v tabuľke je daný súčtom hodnôt v stĺpcoch, tak nám stačí ukázať, že na nulu sa nasčítajú tieto zmenené čísla.

Po zmene nám v prvom riadku zostane osem núl, v druhom riadku osem osmičiek, v treťom osem šestnástok, …. Tentokrát využijeme, že aj do riadkov dávame rovnako veľa $+$ a $-$, čo znamená, že tieto čísla sa v každom z riadkov nasčítajú na nulu, čiže aj celkový súčet v tabuľke je nula.

Iné riešenie

Úloha sa dá riešiť aj algoritmicky, no stále tam nejaké veci treba dokázať. Pozrieme sa teda na to, ako malými úpravami vieme tabuľku upraviť do jednoduchého tvaru.

Začnime s takýmto rozložením znamienok. $$\begin{array}{|r|r|r|r|r|r|r|r|} \hline + & + & + & + & - & - & - & - \ \hline + & + & + & + & - & - & - & - \ \hline + & + & + & + & - & - & - & - \ \hline + & + & + & + & - & - & - & - \ \hline - & - & - & - & + & + & + & + \ \hline - & - & - & - & + & + & + & + \ \hline - & - & - & - & + & + & + & + \ \hline - & - & - & - & + & + & + & + \ \hline \end{array}$$ Všimnime si, že v prvom riadku máme $+1-5=-4$, $+2-6=-4$, $+3-7=-4$ a $+4-8=-4$, teda súčet v ňom je $-16$. Podobne ukážeme, že aj ďalších troch riadkoch je súčet $-16$ a v spodných štyroch zas $+16$, teda celkový súčet je nulový.

Túto tabuľku však vieme aj upravovať. Totiž, ak máme štyri políčka vo vrcholoch obdĺžnika, ktoré majú v susedných vrcholoch rozličné znamienka, súčet v nich je dokopy nula. Na to, aby sme sa presvedčili, že je to tak, pozrime sa na štyri čísla v nasledovnej tabuľke. $$\begin{array}{|r|r|r|r|r|r|r|r|} \hline & & & & & & & \ \hline +a & \quad&\quad &\quad & -b &\quad &\quad &\quad \ \hline & & & & & & & \ \hline -c & & & & +d & & & \ \hline & & & & & & & \ \hline & & & & & & & \ \hline & & & & & & & \ \hline & & & & & & & \ \hline \end{array}\qquad \begin{array}{|r|r|r|r|r|r|r|r|} \hline & & & & & & & \ \hline -a &\quad &\quad &\quad & +b &\quad &\quad &\quad \ \hline & & & & & & & \ \hline +c & & & & -d & & & \ \hline & & & & & & & \ \hline & & & & & & & \ \hline & & & & & & & \ \hline & & & & & & & \ \hline \end{array}$$

Vzhľadom na to, v akých stĺpcoch sú jednotlivé čísla, musí pre nejaké $k$ platiť $b=a+k$ a $d=c+k$. Potom ale $$a-b-c+d=a-(a+k)-c+(c+k)=0,$$ čo sme chceli dokázať. To okrem iného znamená, že aj po výmene znamienok v týchto štyroch políčkach zostane súčet nulový.

No a tu mnohí z vás skončili, že už je to hotovo. Žiaľ, nie je. Napríklad ešte nie je jasné, prečo by sme sa takýmito úpravami mali vedieť dostať ku každej vyhovujúcej tabuľke $8\times 8$. My popíšeme opačný smer – a to, ako sa od ľubovoľnej tabuľky spĺňajúcej zadanie dostať k tej „štvorblokovej“ zo začiatku.

Naším prvým cieľom bude dostať do požadovaného tvaru prvý stĺpec. Predpokladajme teda, že ešte nie je v poriadku, čiže v jeho hornej polovici sa nachádza $-$. Potom sa v nej môžu nachádzať najviac tri $+$, a teda aspoň jedno $+$ bude v dolnej polovici. Tým sme našli dve zo štyroch požadovaných znamienok.

Ešte by sme potrebovali nájsť nejaký iný stĺpec, v ktorom budú v príslušných riadkoch opačné znamienka. Keď sa v riadku s mínusom pozrieme na štyri plusové stĺpce, v riadku s plusom musí aspoň jeden z nich mať mínus (ostávajú nám už iba tri). $$\begin{array}{|r|r|r|r||r|r|r|r|} \hline & & & & & & & \ \hline - &\; \; & + &\; \; & + & + &\; \; & + \ \hline & & & & & & & \ \hline & & & & & & & \ \hline\hline & & & & & & & \ \hline + & & + & & - & + & & + \ \hline & & & & & & & \ \hline & & & & & & & \ \hline \end{array}$$

Túto štvoricu teda vieme prehodiť a dostať tak $+$ do hornej polovice prvého stĺpca. Takto vieme docieliť, že prvý stĺpec bude mať hore plusy a dole mínusy. Uvedomme si, že podobne vieme dosiahnuť, že v poslednom stĺpci budú hore mínusy a dole plusy. Zároveň tým ani nepokazíme prvý stĺpec, lebo do štvoríc tenokrát hľadáme stĺpce, kde mínus je v hornej polovici a plus v dolnej polovici (čo prvý stĺpec už nespĺňa).

Podobnou úvahou vieme upraviť aj prvý a posledný riadok, čím tabuľku dostaneme do nasledovného tvaru. $$\begin{array}{|r|r|r|r||r|r|r|r|} \hline + & + & + & + & - & - & - & - \ \hline + & & & & & & & - \ \hline + & & & & & & & - \ \hline + & & & & & & & - \ \hline\hline - & & & & & & & + \ \hline - & & & & & & & + \ \hline - & & & & & & & + \ \hline - & - & - & - & + & + & + & + \ \hline \end{array}$$

Tým nám však zostane tabuľka rozmerov $6\times6$, kde v každom riadku aj stĺpci majú byť tri $+$ a tri $-$, čiže matematickou indukciou vieme nájsť postupnosť výmen aj pre ňu.