10. príklad - Vzorové riešenie

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ď:

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.