5. Komplikácia Malovaných Sukovíc vzorové riešenie

V tejto úlohe skúmame, kedy z rôznych kombinácií troch paličiek je možné spraviť trojuholník. Na toto nám poslúži trojuholníková nerovnosť, ktorá hovorí o tom, že dĺžky ľubovoľných dvoch strán trojuholníka musia byť dokopy dlhšie ako tretia strana. Čo je splnené presne vtedy, keď súčet dvoch najkratších strán je väčší ako tretia.

Máme dokázať, že existuje minimálne jedna farba, kde keď zoberieme hocijakú kombináciu troch paličiek z tej farby, tak dostaneme trojuholník. To je ekvivalentné s tým, že chceme, aby v tej jednej farbe bol súčet dvoch najkratších paličiek dlhší ako najdlhšia palička tej farby – lebo ak dve najkratšie sú dlhšie ako najdlhšia, tak nám z toho vyplýva, že ak zoberieme ľubovoľné iné dve, ktoré sú dlhšie, tak tiež budú dlhšie ako najdlhšia, teda aj ako ľubovoľná tretia palička. Čo je presne to, čo chceme dokázať.

Zoraďme si pre jednoduchosť paličky v každej farbe od najkratšej po najdlhšiu, žlté \(A_1 \leq A_2 \leq \cdots \leq A_{100}\), červené \(B_1 \leq B_2 \leq \cdots \leq B_{100}\), zelené \(C_1 \leq C_2 \leq \cdots \leq C_{100}\). Teraz si môžeme BUNV (bez ujmy na všeobecnosti) povedať, že najkratšie paličky zo všetkých farieb sú usporiadané takto: \(A_{1} \leq B_{1} \leq C_{1}\).

Zo zadania vieme, že musí platiť \(A_{1} + B_{1} > C_{100}\), kde \(C_{100}\) je najdlhšia zo zelených. Ale ak platí táto nerovnosť, tak musí platiť aj nerovnosť \(C_{1} + C_{2} > C_{100}\), keďže vieme, že platí \(A_{1} \leq B_{1} \leq C_{1} \leq C_{2}\). Spojením týchto troch nerovností dostávame, že pre hocijakú trojicu \(i,j,k\) kde \(i<j<k\) platí, že \[C_{i} + C_{j} > C_{k},\] čo znamená, že v zelenej farbe vieme z hocijakých troch paličiek spraviť trojuholník.