Maandelijks archief: augustus 2025

Art gallery theorema

Geplaatst op door

Het art gallery theorema (of kunstgalerijtheorema) is een bekend resultaat uit de computationele meetkunde. Het werd voor het eerst geformuleerd door de wiskundige Victor Klee in 1973 en later bewezen door Václav Chvátal in 1975.

Stel je hebt een kunstgalerij die de vorm heeft van een veelhoek (polygoon) met n hoeken . Je wilt bewakers plaatsen zodat elke plek in de galerij zichtbaar is voor ten minste één bewaker. De vraag is: Hoeveel bewakers zijn minimaal nodig? Het theorema zegt:

    \[\left\lfloor \frac{n}{3} \right\rfloor\]

bewakers zijn altijd voldoende en soms noodzakelijk om een veelhoek met hoeken volledig te bewaken. Een veelhoek met hoeken kan altijd bewaakt worden door hoogstens bewakers.

Het bewijs maakt gebruik van triangulatie van veelhoeken: Elke veelhoek kan worden opgedeeld in driehoeken. Dan kan men de driehoeken inkleuren met drie kleuren (vergelijkbaar met grafen die drie-kleurig zijn). Er bestaat altijd minstens één kleur die in hoogstens \left\lfloor \frac{n}{3} \right\rfloor driehoeken voorkomt. Als je bewakers in de hoekpunten van die kleur zet, kun je de hele veelhoek bestrijken.

Hieronder zie je een voorbeeld van een 10 hoek:

 

De chromatische veelterm

Geplaatst op door

In de grafentheorie speelt het inkleuren van grafen een centrale rol. Hoeveel manieren zijn er om de knopen van een graaf te kleuren, zodat aangrenzende knopen altijd verschillende kleuren krijgen? Deze eenvoudige vraag leidde tot de introductie van een krachtig wiskundig object: de chromatische veelterm.

Stel dat we een graaf hebben met knopen. Een \lambda-kleuring is een toewijzing van \lambda kleuren aan de knopen, waarbij buren (knopen die door een boog  verbonden zijn) nooit dezelfde kleur mogen hebben. Het aantal mogelijke geldige \lambda-kleuringen hangt natuurlijk af van zowel G als van \lambda. Voor elk natuurlijk getal kunnen we dus het aantal geldige -kleuringen tellen. Verrassend genoeg blijkt dit aantal altijd gegeven te worden door een veelterm in \lambda. Deze veelterm noemen we de chromatische veelterm van , genoteerd als P(G,\lambda). Een voorbeeld:

Er is een verband met het chromatisch getal van een graaf G: het kleinste aantal kleuren dat nodig is om de knopen van zo te kleuren dat geen twee aangrenzende knopen dezelfde kleur krijgen. Het chromatisch getal van een graaf G is dus het kleinste getal \lambda waarvoor de chromatische veelterm positief is.

Enkele vaststellingen:

  1. Een lege graaf met n knopen (geen bogen):
    Elke knoop kan willekeurig één van de \lambda kleuren krijgen, dus P(G,\lambda)=\lambda^n.
  2. Voor volledige grafen is de situatie eenvoudig. Zo geldt voor de volledige graaf  K_3 op 3 knopen dat p(K_3,\lambda)= \lambda(\lambda-1)(\lambda-2). 

 

Vingerrekenen

Geplaatst op door

De herkomst van de symbolen voor onze cijfers is het meest duidelijk voor het cijfer 1: de vinger.

Omdat je maar 10 vingers hebt, heb je voor opgaven met het getallen boven de 10 trucjes nodig om ze toch met behulp van je vingers uit te kunnen rekenen. Neem bijvoorbeeld het vingervermenigvuldigen. Het is voldoende om de tafels tot 5×5 te kennen. 

Wil je het product weten van twee getallen a en b, beide tussen 5 en 10, dan steek je je ene hand op met a – 5 vingers en de andere hand met b – 5 vingers. Het resultaat van de vermenigvuldiging is de som van het aantal opgestoken vingers x 10 en het product van de beide aantallen niet opgestoken vingers. Neem bijvoorbeeld 6 x 9: in het ene hand steek je 1 vinger op en in de andere hand 4 vingers. De som van de opgestoken vingers, vermenigvuldigd met 10 is 50. Tel daar bij op het product van de niet opgestoken vingers van beide handen: 4 x 1 = 4 en je krijgt 50 + 4 = 54.

Het vierkantswortel symbool

Geplaatst op door

Het wortelteken werd ingevoerd door Christoff Rudolff (1499-1545) in zijn Duits algebraboek Die Coss (1525). Dit boek was zeer invloedrijk, vooral in Duitsland. In 1553 publiceerde Michael Stifel (1487-1567), de grootste Duitse algebraïst van de 16de eeuw, er in Königsberg een verbeterde versie van. Ook in zijn bekende werk Arithmetica integra  (1544), gebruikte Stifel dit symbool in de huidige betekenis.

Het teken  leek op een schuine r (van het Latijnse woord radix, wat “wortel” betekent). In middeleeuwse notities werd het woord radix soms afgekort tot een gotische of cursieve ‘r’.
Als die r wat werd verlengd en gestileerd, kreeg je iets wat op het moderne symbool voor vierkantswortel  lijkt. In Rudolffs drukwerk stond het symbool zonder bovenste horizontale streep: de horizontale “vinculum” (het bovenlijntje) werd toegevoegd om duidelijk te maken welke delen van de formule onder de wortel horen. Vanaf de 17e eeuw werd het symbool geleidelijk gestandaardiseerd in de vorm die we nu kennen: een schuine streep met een horizontale lijn erboven.

de stelling van Van Aubel

Geplaatst op door

De stelling van Van Aubel is een wiskundige stelling die te maken heeft met vierkanten op de zijden van een willekeurige vierhoek. Het zegt dat als je vierkanten bouwt op de zijden van een vierhoek, de som van de oppervlaktes van twee tegenoverliggende vierkanten gelijk is aan de som van de oppervlaktes van de andere twee tegenoverliggende vierkanten. Of in een meer klassieke vorm: De lijnstukken die de middens van tegenoverliggende vierkanten (in het rood getekend)  verbinden, staan loodrecht op elkaar en zijn even lang.

Het is een veralgemening van een ander beroemd meetkundig resultaat — namelijk het stelling van Napoleon, maar dan toegepast op vierhoeken in plaats van op driehoeken : als je gelijkzijdige driehoeken construeert op de zijden van een willekeurige driehoek (allemaal naar buiten toe), dan liggen de middens van deze driehoeken op de hoekpunten van een gelijkzijdige driehoek.