Opravovatelia

David [email protected]

Skaloš [email protected]

Preformulujme si na začiatok zadanie do jazyka matematiky: náš hrad je graf so 43 vrcholmi, kde všetky vrcholy ležia na kružnici a z každého vrcholu vychádza práve 20 červených a 22 modrých hrán.

Tým, že z každého vrcholu vychádza práve 22 hrán modrej farby, tak vieme vybrať $\binom{22}{2}$ dvojíc, pričom spojnica ich rozdielnych vrcholov bude tvoriť tretiu stranu trojuholníka. Toto vieme spraviť pre všetkých 43 vrcholov a dostaneme $43\cdot\binom{22}{2}=9\,933$ trojuholníkov. No a tieto trojuholníky sú buď celé modré (ďalej len $3_m$$0_c$) alebo s dvomi modrými stranami a jednou červenou (ďalej len $2_m$$1_c$). V tomto momente si treba uvedomiť, že celé modré trojuholníky sme započítali vždy 3-krát, pretože 2 modré hrany vychádzajú z každého ich vrcholu. Potom musí platiť, že $$9\,933=3\cdot\textcolor{blue}{3_m}\textcolor{red}{0_c}+\textcolor{blue}{2_m}\textcolor{red}{1_c}=3\cdot2\,022+\textcolor{blue}{2_m}\textcolor{red}{1_c}.$$ Odtiaľ ako riešenie lineárnej rovnice dostaneme $\textcolor{blue}{2_m}\textcolor{red}{1_c}=3\,867$. Teraz budeme opakovať postup zo začiatku, ale nebudeme voliť 2 modré hrany. Namiesto toho budeme v každom vrchole voliť jednu modrú a jednu červenú hranu. V každom vrchole je takýchto možností $22\cdot20=440$, teda vo všetkých vrcholoch $43\cdot22\cdot20=18\,920$. Dostali sme tak trojuholníky s 2 modrými a 1 červenou stranou a 1 modrou a 2 červenými stranami (ďalej len $1_m$$2_c$). Do výsledného súčtu sme ale každý taký trojuholník započítali 2-krát, pretože v trojuholníku $1_m$$2_c$ existujú práve 2 vrcholy také, že z nich vychádza 1 modrá a 1 červená hrana. Obdobné tvrdenie platí aj pre trojuholníky s ofarbením $2_m$$1_c$. Z toho dostávame rovnicu v tvare $$18\,920=2\cdot\textcolor{blue}{2_m}\textcolor{red}{1_c}+2\cdot\textcolor{blue}{1_m}\textcolor{red}{2_c}=2\cdot3\,867+2\cdot\textcolor{blue}{1_m}\textcolor{red}{2_c},$$ ktorej riešenie bude $\textcolor{blue}{1_m}\textcolor{red}{2_c}=5\,593$. Posledný raz implementujeme metodiku zo začiatku, ale tento raz budeme vyberať 2 červené hrany, ktorých je $\binom{20}{2}$. Dobudovaním trojuholníkov dostaneme úplne červené trojuholníky (červené triá, ďalej len $\textcolor{blue}{0_m}\textcolor{red}{3_c}$) a $\textcolor{blue}{1_m}\textcolor{red}{2_c}$. Takýchto trojuholníkov bude $43\cdot\binom{20}{2}$, ale opäť ako pri úplne modrých trojuholníkoch, tak aj tu sme započítali $\textcolor{blue}{0_m}\textcolor{red}{3_c}$ až 3-krát. Zostáva nám posledná rovnica $$8\,170=\textcolor{blue}{1_m}\textcolor{red}{2_c}+3\cdot\textcolor{blue}{0_m}\textcolor{red}{3_c}=5\,593+3\cdot\textcolor{blue}{0_m}\textcolor{red}{3_c},$$ ktorej riešením je $\textcolor{blue}{0_m}\textcolor{red}{3_c}=\textbf{859}$, čo je hľadaným riešením.