Az ABCDE szabályos ötszög minden átlóját illetve oldalát kék vagy piros színnel színezzük úgy, hogy bármely három csúcsa által meghatározott háromszögnek legyen két különböző színű oldala. Hányféle ilyen színezés létezik?

Hmm… Érdekes feladat.

Elsőre arra gondoltam, mi lenne, ha visszavezetnénk egy négyzetre az esetet. Ott könnyen belátható egy csúcsból nem indulhat három azonos színű szakasz, mert ezek végpontjait összekötő szakaszokat – a négyzet másik két oldalát és azok végpontjait összekötő átlót – ellentétes színnel kellene színezni, így a három másik csúcs által határolt háromszög mindegyik oldala azonos színű lenne.

Pl. Ha AB, AC és AD is piros, Akkor:

Az ABC háromszög két oldala (AB és AC) piros, így BC csak kék lehet.

Az ACD háromszög két oldala (AC és AD) piros, így CD csak kék lehet.

Az ABD háromszög két oldala (AB és AD) piros, így BD csak kék lehet.

Ebből adódóan BCD háromszög mindegyik oldala kék lesz, így nem megfelelő ez a színezés.

(Természetesen négy azonos színű szakasz sem indulhat egy csúcsból ugyanezen ok miatt.)

Ergo mindegyik csúcsból pontosan két kék és két piros szakasznak kell találkoznia.

~ ~ ~

I. Tegyük fel, hogy AB és AC piros, AD és AE kék.

BC-nek kéknek kell lennie az ABC háromszög miatt, hiszen AB és AC piros.

DE-nek pirosnak kell lennie az ADE háromszög miatt, hiszen AD és AE kék.

Több kényszerítő színezés nincs.

I.1. Tegyük fel, hogy BE kék.

Mivel B-ből már indul két kék szakasz (BC és BE), ezért BD csak piros lehet.

Mivel E-ből már indul két kék szakasz (AE és BE), ezért CE csak piros lehet.

Így C-ből is és D-ből is két-két piros szakasz indul (AC és CE, illetve BD és DE), ezért CD csak kék lehet.

Ha végignézzük, ez egy helyes megoldás.

I.2. Tegyük fel, hogy BE piros.

Mivel B-ből már indul két piros szakasz (AB és BE), ezért BD csak kék lehet.

Mivel E-ből már indul két piros szakasz (BE és DE), ezért CE csak kék lehet.

Így C-ből is, D-ből is két-két kék szakasz indul (BC és CE, illetve AD és BD), ezért CD csak piros lehet.

Ha végignézzük, ez is helyes megoldás.

~ ~ ~

Tehát az A-ból induló egyetlen színezés esetén két megoldás található.

Mivel az ötszög csúcsai megcserélhetők, és a gráf ettől nem változik (csak a csúcsait kell más betűvel jelölni, ha körbejárási irányban akarjuk őket betűvel ellátni), így bármilyen A-ból induló olyan színezésre, ahol A-ban két kék és két piros szakasz találkozik, pontosan két megoldás fog jutni.

A-ból meg 6 különböző színezés indítható úgy, hogy két piros és két kék szakasz találkozik. Ezek:

AB és AC piros,

AB és AD piros,

AB és AE piros,

AC és AD piros,

AC és AE piros,

AD és AE piros.

Így tehát összesen 12 különböző a feltételnek megfelelő színezés létezik.

~ ~ ~ ~ ~ ~ ~

Nem tartom kizártnak, hogy létezik ennél egyszerűbb megoldás, de most hirtelen ez jutott eszembe.