5. Krotil Medveď Strelcov? $\left(\kappa \le 8\right)$ vzorové riešenie

Zadanie

Medveď Daniel bol na lukostreleckej súťaži, na ktorej povedal faaakt zlý vtip o žirafách. Žirafky to nemohli nechať len tak, takže Medveďa Daniela zmlátili. Zhabali mu aj všetky luky a šípy, a tak sa z nich stali žirafí strelci.

Majme prvú KMS šachovnicu ako na obrázku 1. Žirafí strelec sa vie hýbať diagonálne o ľubovoľný počet políčok, ale počas svojho pohybu nesmie opustiť šachovnicu.

1. Koľko najviac žirafích strelcov možno umiestniť na šachovnicu tak, aby sa žiaden žirafí strelec nedokázal jedným ťahom pohnúť na políčko iného žirafieho strelca?

2. Koľko najmenej farieb je potrebných na ofarbenie políčok šachovnice tak, aby medzi ľubovoľnými dvoma políčkami rovnakej farby bolo možné spraviť jeden ťah žirafím strelcom?

Je pomerne nenáročné umiestniť na šachovnicu \(19\) strelcov tak, aby sa navzájom neohrozovali. Napríklad ako na obrázku nižšie. K týmto \(19\) strelcom vieme tiež pomerne jednoducho šachovnicu zafarbiť \(19\) farbami tak, aby každá bola na jednej diagonále, teda sa jedným ťahom dá dostať medzi všetkými políčkami jednej farby (dokonca aj každý strelec stojí na inej farbe).

Potrebujeme však ešte dôkaz, že viac ako \(19\) strelcov umiestniť nevieme, a nevieme šachovnicu ofarbiť menej ako \(19\) farbami. Našťastie, tento dôkaz už máme pred sebou. Ak by sme mali na šachovnicu umiestniť \(20\) (a viac) strelcov, museli by sme na niektorú z farieb položiť dvoch strelcov. Tí by sa však ohrozovali, keďže z každého políčka sa dá pohnúť na všetky ostatné rovnakej farby. Teda sa určite nedá umiestniť \(20\) alebo viac strelcov. A pre \(19\) sme rozloženie našli.

Ak by sme mali ofarbiť šachovnicu iba \(18\) (alebo menej) farbami, museli by na niektorej farbe stáť dvaja strelci z našich \(19\) umiestnených. Tí sa však určite neohrozujú, čiže medzi týmito políčkami sa nebude dať dostať na jeden ťah. Teda sa určite nedá ofarbiť menej ako \(19\) farbami, a pre \(19\) farieb sme ofarbenie našli.