Odporúčaný článok

Termín zimného sústredenia - Milí riešitelia a rodičia, vzhľadom na momentálnu nestabilnú situáciu sme sa rozhodli, že zimné sústredenie presunieme na február. … Prejsť na článok

×
Kategórie:
5
6
7
8
9

Zadanie

Porotcovia sa chcú usadiť na stoličky usporiadané v mriežke 9\times 9 tak aby si navzájom nezacláňali a mali dosť miesta. To znamená, že porotca nemôže mať nikoho priamo naľavo ani napravo od seba a ani na miestach o dva rady pred týmito miestami. Okrem toho nemôže nikto sedieť na stoličke priamo o dva rady za ním. Tieto podmienky môžeme vidieť znázornené aj na obrázku. Koľko najviac porotcov vieme takto usadiť na pripravené stoličky?

Vzorové riešenie

Opravovali: palo

Ako prvé sa pozrime na zadané obmedzenia usádzania (prvý obrázok vľavo). Presnejšie, všimnime si tri vyznačené zelené políčka. Na týchto políčkach taktiež nemôže sedieť porotca spolu s porotcom na žltom políčku, pretože potom by práve ten žltý zavadzal zelenému. Môžeme povedať, že každý porotca v skutočnosti obsadzuje nie päť, ale osem políčok. Presne tak, ako na pravom obrázku.

Uvedomme si teraz, že na ľubovoľných štyroch políčkach, ktoré tvoria rohy obdĺžnika s dvomi stĺpcami a tromi riadkami, môže sedieť nanajvýš jeden porotca. To preto, lebo každé z týchto políčok blokuje všetky tri ostatné (a možno aj ďalšie políčka, ale to nás teraz nezaujíma). To znamená, že vieme pokryť celú plochu niekoľkými takýmito skupinami napríklad tak, ako na nasledujúcom obrázku:

Na obrázku môžeme vidieť farebne a číselne naznačené tie spomínané rohy obdĺžnika. Nemusíme ani používať celú takúto formáciu, napríklad násobky päťky na pravom okraji používajú iba polovicu spomínaného obdĺžnika. Nakoniec spodný riadok tiež používa iba polovicu, ale tuto je jednoduchšie argumentovať, že viac ako päť porotcov sa do riadku nezmestí, keďže nemôžu sedieť vedľa seba.

Z tohto vyplýva, že viac ako 25 porotcov sa určite do mriežky nezmestí. Navyše, keď sa pozrieme na obrázok nižšie, tak vidíme, že práve 25 porotcov do mriežky usadiť vieme a to bez akéhokoľvek zavadzania si.

Odpoveď:

Najviac vieme usadiť 25 porotcov, napríklad tak, ako na poslednom obrázku.

Komentár

Tento príklad bol veľmi náročný a priemerný počet získaných bodov bol iba 3{,}136. Najväčší problém bol poriadny dôkaz toho, že viacej ako 25 porotcov usadiť nevieme. Veľakrát úplne chýbal, alebo bol nedostatočný - to, že je niečo najvýhodnejšie pre jeden riadok, ešte neznamená, že je to najlepšie pre celú tabuľku.

Na desaťbodový dôkaz treba uviesť niečo typu tohto vzorového riešenia, t.j. pokryť celú tabuľku tak, aby bolo jasné, prečo je práve 25 to najlepšie.