Kleuringen

Op hoeveel verschillende manieren kunnen we de hoekpunten van een gelijkzijdige driehoek kleuren als we alleen over de drie hoofdkleuren rood,geel en blauw mogen beschikken. Twee kleuringen zijn gelijk als ze door een draaing op elkaar overgaan.

 

  • Een eerste manier werkt als volgt: als je slechts 1 kleur gebruikt zijn er drie mogelijkheden. als je twee kleuren gebruikt zijn er 6 oplossingen en als je alle drie de kleuren gebruikt dan zijn er 2 mogelijkheden. in het totaal heb je dus 11 mogelijke kleuringen.
  • Een tweede manier maakt gebruik van de stelling van Burnside: Als een eindige groep werkt op een verzameling , dan is het aantal verschillende configuraties “tot symmetrie” (dus het aantal banen/orbits) gegeven door de formule

        \[\frac{1}{|G|}\sum_{g \in G} |Fix(g)|\]

    met Fix(g) bedoelt men de verzameling elementen x van X die door g worden vastgehouden. In ons voorbeeld noemen we voor G de rotaties van een gelijkzijdige driehoek; dus een draaiing over 0^{circ},120^{\circ}, 240^{\circ}. Voor X nemen we alle mogelijke kleuringen van de hoekpunten met de drie gegeven kleuren. G telt dus 3 elementen. |Fix( 0^{\circ}}|=3^3=27 en |Fix( 120^{\circ})|=|Fix( 240^{\circ})|=3. Volgens de stelling van Burnside zijn er dus

        \[\frac{1}{3}(27+3+3)=11\]

    oplossingen

  • Er bestaat ook een formule die het probleem oplost voor een willekeurige regelmatige. n-hoek:

        \[\frac{1}{n}\sum_{d|n}\varphi(\frac{n}{d})m^d\]

    Hierbij stelt m het aantal beschikbare kleuren voor en is \varphi de totïent functie van Euler.


                     

Kleuringen

Soms kan het nuttig zijn om een rooster in te  kleuren  en daardoor te bewijzen dat een bepaalde situatie al dan niet mogelijk is. Deze heuristiek wordt dikwijls gebruikt wanneer je een schaakbord moet opvullen met bepaalde vormen.

Voorbeeld: Kan een 10 x 10 schaakbord opgevuld worden met 25 tetrominos van de vorm 

Oplossing:

  • Geef elk vakje van het schaakbord een uniek adres door het rijnummer en kolomnummer van het vakje te noteren. Zo een adres is dan van de vorm (i,j) \text{ waarbij } 1 \leq i,j \leq 10.
  • Kleur (i , j ) met de kleur t = i +j \text{ mod4 } zodat t \in \{1,2,3,4\}. Hierbij is1 = blauw; 2 = geel; 3 = rood; 4 = groen.
  • Elke tetromino zal door de schikking van de kleuren (cijfers) precies 4 vakjes met vier verschillende kleuren bedekken.
  • Aangezien er op het bord 25 keer blauw (1), 26 keer geel (2) 25 keer rood (3) en 24 keer groen (4) voorkomt zal het niet mogelijk zijn om het bord te vullen met 25 tetromino’s