Kategórie:
5
6
7
8
9

Zadanie

Subjekt je n-uholník s n vrcholmi a všetkými jeho uhlopriečkami aj stranami. Možné počty vrcholov sú n = 7, 8, 10, 11, 12. Pre každý z týchto útvarov zistite, či vieme zafarbiť jeho uhlopriečky (a strany) niekoľkými farbami tak, aby pre jeho ľubovoľné dva vrcholy A a B existoval práve jeden vrchol C taký, že trojuholník ABC má všetky hrany rovnakej farby.

Vzorové riešenie

Opravovali: mišo

Dobrým začiatkom pri takomto príklade je nakresliť niektorý z prípadov (napr. pre n = 7) a skúsiť si strany a uhlopriečky vyfarbiť. Bez ohľadu na to, či sa nám to podarí vieme prísť k niekoľkým záverom. Ako prvé si môžeme uvedomiť, že každý trojuholník vieme vyfarbiť inou farbou. Ak dva trojuholníky majú rovnakú farbu a žiadnu spoločnú stranu, prefarbením jedného z nich nič nepokazíme. Ak by mali rovnakú farbu aj spoločnú stranu, tak si kraje tejto úsečky označíme A a B a máme dva možné body C, čo podľa zadania nemôžeme.

Ako prvé teda vidíme, že každá uhlopriečka a strana musí byť jednej z niekoľkých farieb. Ich počet označíme f. Každej farby sú tri strany jedného trojuholníka, takže všetkých uhlopriečok musí byť 3 \cdot f, čo je násobok 3. Počet všetkých úsečiek v n-uholníku je n \cdot (n-1) : 2. Overíme, ktoré n túto podmienku spĺňajú.

n = 7{:}~~~ 7 \cdot 6 : 2 = 21 = 3 \cdot 7,\\ n = 8{:}~~~ 8 \cdot 7 : 2 = 28 = 3 \cdot 9 + 1,\\ n = 10{:}~~~ 10 \cdot 9 : 2 = 45 = 3 \cdot 15,\\ n = 11{:}~~~ 11 \cdot 10 : 2 = 55 = 3 \cdot 18 + 1,\\ n = 12{:}~~~ 12 \cdot 11 : 2 = 66 = 3 \cdot 22.

Teraz by sme mohli skúsiť nakresliť si 7-,\, 10-,\, 12-uholníky a vyfarbiť im uhlopriečky, aby sme overili, že to ide. Pri 10- a 12-uholníku sa nám to však nepodarí. Prečo?

Vráťme sa späť k trojuholníkom. Z každého vrcholu trojuholníka vychádzajú 2 strany. Teda z každého vrcholu n-uholníka musia vychádzať dve hrany za každú farbu trojholníka, ktorému patrí daný vrchol. Z vrcholu n-uholníka vychádza n-1 strán a uhlopriečok, ktoré chceme rozdeliť na dvojice. To ide iba ak je n-1 párne a teda n je nepárne. To vylučuje n = 10 a n = 12.

Pre správnosť by sme mali ešte overiť, že 7-uholník zadanie spĺňa. Mohlo by sa nám stať, že sme len nejaké pravidlo vynechali a že v skutočnosti nefunguje ani tento prípad. Najľahšie overenie je nájsť správne ofarbenie -- napríklad ako na obrázku.

Odpoveď: Uhlopriečky a strany vieme podľa zadania ofarbiť len v 7-uholníku.

Komentár

Aj keď sa to tak z riešenia nemusí zdať, príklad sa ukázal byť pomerne náročný a odovzdalo ho len málo riešiteľov. Tí mali poväčšinou správnu myšlienku s rozdeľovaním na trojuholníky, no využili ju len na overenie deliteľnosti tromi. Ako však môžeme vidieť tento postup nevylúči 10-uholník ani 12-uholník.

Niektorým z Vás by mohlo ešte vŕtať v hlave, čo s prípadom 9-uholníka, ktorý sa v zadaní nevyskytuje. Po overení výpočtov prídete aj sami na to, že by mohol zadaniu vyhovovať. A skutočne, ak si k tomu na chvíľu sadnete, mohlo by sa Vám podariť nájsť správne ofarbenie strán a uhlopriečok.