Grafen

The absurd circle division patern Moser’s circle problem

3Blue1Brown https://www.youtube.com/watch?v=YtkIWDE36qU Strong law of small numbers De formule [latex]F_n=2^{2^n}+1[/latex] geeft priemgetallen voor natuurlijke getallen [latex]n \le 4[/latex]. Fermat verwachtte dat de rij [latex]F_n[/latex] zou blijven doorlopen met priemgetallen. Toen Euler in 1732 bewees dat [latex]F_5[/latex] geen priemgetal is, werd de droom rond de priemgetallen van Fermat in de kiem gesmoord. De formule [latex]G_n=n^2-n+41[/latex] echter

[ Lees meer ]

Een klein beetje grafentheorie, een sterk gevolg: het lemma van Sperner

Het lemma van Sperner is een resultaat dat de kracht van de grafentheorie als didactisch onderwerp opnieuw laat zien: met minimale kennis van grafen leid je een bewijs af met een diep resultaat. Het lemma kan bewezen worden met sterkere leerlingen in de 2[latex]^\text{e}[/latex] of 3[latex]^\text{e}[/latex] graad, die niet terugdeinzen voor een streepje abstractie. Het lemma is de discrete variant van de stelling van Brouwer en legt zo een link tussen continue en discrete wiskunde. Een graaf [latex]G=(V,E)[/latex] bestaat uit twee eindige verzamelingen [latex]V[/latex] en [latex]E[/latex]. De elementen van [latex]V[/latex] worden knopen genoemd, en die van [latex]E[/latex] bogen. Elke boog…

[ Lees meer ]

Instant insanity

Instant Insanity is de naam van een puzzel die bestaat uit vier kubussen waarvan elk zijvlak rood (R), blauw (B), groen (G) of wit (W) is. In de figuur hieronder zie je een foto van een uitgave van de speelgoedproducent Parker Brothers uit 1967 die nog in de originele verpakking zit. De tekst die op de verpakking staat, is veelbelovend: 'Be calm ... You may never, ever see them this way again'. [caption id="attachment_32777" align="aligncenter" width="441"] Figuur 1 Be calm ... ... You may never, ever see them this way again. (Bron: https://www.ebay.com/itm/392938423661)[/caption] Het doel van het spel is om…

[ Lees meer ]

Wiskunde rond besmettingsziekten

In deze coronatijd overstelpen de media ons met uitgebreid cijfermateriaal. Zelden werd het belang van wiskunde zo duidelijk onderstreept voor de hele maatschappij. Toch loopt de itnerpretatie van dit materiaal nogal eens fout. In deze loep doen we een bescheiden poging om helderheid te brengen in dit kluwen van informatie. We zoomen in op drie Covid-gerelateerde thema's die bruikbaar zijn in de lessen wiskunde. We brengen de beruchte contactbubbels in verband met grafentheorie. Vervolgens bespreken we een item in verband met kansrekening in het kadeer van teststrategieën voor Covid-19. In het laatste deel focussen we op een uitgewerkte onderzoeksopdracht over de discrete versie van heet beruchte SIR-model. We leveren in deze loep materiaal voor in de klas en achtergrond om te kunnen vertellen elk jaar.

[ Lees meer ]

Korste afstandsalgoritme toegepast op verrassende puzzel (Bruno Teheux)

Bruno Teheux, À la recherche des chemins les plus courts Losanges 46 (2019), 45-54 De auteur van dit artikel is onderzoeker aan de ‘Mathematics Research Unit’ van de universiteit van Luxemburg. Het artikel gaat over grafentheorie en het algoritme van de Nederlander Edsger Wybe Dijkstra (20ste eeuw) om de kortste routes te vinden in een graaf. Dit algoritme bepaalt de kortste routes vertrekkend van een gegeven knoop naar elke andere knoop (afzonderlijk; het gaat niet over een route die alle knopen moet aandoen zoals bij het handelsreizigersprobleem). De puzzel van de witte en zwarte bollen Het spectaculaire is dat Teheux dit…

[ Lees meer ]

Redeneren en puzzelen met grafen

Een graaf bestaat uit ‘knopen’ die wel of niet verbonden zijn door ‘bogen’. De grafentheorie, ontstaan met de bruggen van Koningsbergen in de 18de eeuw, is nu overal aanwezig als wiskundig model voor het internet, sociale netwerken, routeplanners... en doet binnenkort ook haar intrede in de eindtermen wiskunde voor de tweede graad. We laten in deze loep zien hoe leerlingen met grafen (zullen) kunnen redeneren, puzzelen en bewijzen zonder veel voorkennis of algebraïsche hindernissen. Ze leren ook diverse situaties modelleren in een zelfde taal van knopen en bogen. Bij de meeste ‘echte’ toepassingen gaat het om reusachtige grafen en zijn er systematische algoritmen nodig om hierin bv. kortste wegen te vinden, of om alle knopen efficiënt met elkaar te verbinden. Exemplarisch laten we de leerlingen kennis maken met het algoritmisch denken dat hiervoor nodig is.

[ Lees meer ]

Nieuw handelsreizigersprobleem? J. Klauwen, Pythagoras

Pythagoras, wiskundetijdschrift voor jongeren, 59/1, 6-8 Het tijdschrift Pythagoras is sterk in korte artikels die lange namijmeringen teweeg brengen. Zo ook deze bijdrage, die met twee bolletjes gemarkeerd is (middelmatige moeilijkheidsgraad). Het klassieke handelreizigersprobleem Het handelsreizigersprobleem (Eng: travelling salesman problem) is een klassieker. Bij dit probleem is een aantal steden gegeven samen met de onderlinge afstanden tussen deze steden. Gevraagd is de kortste route te vinden die alle steden aandoet en eindigt waar het begonnen is. Het handelsreizigersprobleem wordt vaak als voorbeeld genomen van een probleem waarvoor (nog) geen ''snel' algoritme bestaat. Om met zekerheid de kortste handelsroute langs [latex]n[/latex]…

[ Lees meer ]

De zeven bruggen van Koningsbergen

In de achttiende eeuw had de Russische stad Koningsbergen (vanaf 1946 omgedoopt tot Kaliningrad) gelegen aan de monding van de Pregel, zeven bruggen zoals te zien is op figuur 1. Het klassieke probleem van Koningsbergen verwijst naar deze bruggen. Dit probleem gaat als volgt: Is het mogelijk om een wandeling door Koningsbergen te maken, precies

[ Lees meer ]

Het kunstgalerijprobleem

In kunstgalerijen met dure kunstvoorwerpen is er permanente camerabewaking nodig. Hoeveel camera's zijn hier minstens voor nodig? Dit probleem, bekend als het kunstgalerijprobleem of het museumprobleem, werd in 1973 voor het eerst geformuleerd door Viktor Klee. Bewakingscamera's in een museum kunnen in elke richting kijken maar ze kunnen niet van positie veranderen. Om het museumprobleem te vereenvoudigen nemen we aan dat camera's puntgroot zijn en dat ze in het kleinste hoekje van een kamer kunnen gemonteerd worden. Verder veronderstellen we dat er geen objecten of personen in het museum aanwezig zijn die het cameratoezicht kunnen belemmeren. Het kunstgalerijprobleem mag opgevat…

[ Lees meer ]

Verrassende wiskunde

In deze loep komen allerlei problemen aan bod waarvan de uitkomst ons op een of andere manier verrast. Het niveau van de onderwerpen bestrijkt zowel de eerste, tweede als derde graad. Bij sommige problemen blijkt het eerste antwoord dat in je opkomt bij nader inzien totaal fout te zijn. Enkel met een kritische blik op het eindantwoord of een goed onderbouwde, wiskundige redenering kun je anderen (en jezelf!) overtuigen dat het eindresultaat anders is. Sommige problemen sluiten rechtstreeks aan bij de leerstofonderdelen. Zo past een teken-activiteit met vierhoeken in de eerste graad. Een kansspel dat op een verrassende manier leidt tot een fractaal, kan zowel bij rijen als bij kansrekening aan bod komen. Een onverwacht limietgeval hoort dan weer thuis bij de regel van de l'Hospital in de derde graad. Andere problemen in deze loep staan eerder los van de leerstof wiskunde in het secundair onderwijs, maar zijn daarom niet minder interessant. Zoals de reden waarom het lijkt alsof je vrienden op Facebook gemiddeld meer vrienden hebben dan jezelf, en waarom het verkeer soms vlotter kan doorrijden door een welbepaalde straat te verwijderen. In deze loep kunnen de stukjes onafhankelijk van elkaar gelezen worden.

[ Lees meer ]