9. Kúpim Milión Stužiek vzorové riešenie

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.