SciLogs International .com.be.es.de

Recentste blogposts RSS

De kwadratuur van de sudoku

02. Februari 2009, 09:21

Gastbijdrage door Paul Levrie.

Hoewel de titel van deze boekenblog misschien niet echt de lading dekt, kunnen we hem toch wel verantwoorden (zie verder). Het boek dat ter bespreking voorligt (zie verder) is van de hand van Peter Higgins. Het gaat over grafentheorie. Zoals je misschien wel weet is deze tak van de wiskunde ontstaan bij Leonhard Euler (Bazel, 15 april 1707 – Sint-Petersburg, 18 september 1783) toen die in 1736 het probleem van de zeven bruggen van Königsberg oploste. De stad Königsberg (nu Kaliningrad) ligt aan beide zijden van de rivier de Pregel en op twee eilandjes in de rivier. De verschillende delen van de stad zijn met elkaar verbonden via zeven bruggen.

konigsberg

Het gestelde probleem was het volgende: kan je een wandeling maken door Königsberg en daarbij elke brug precies eenmaal oversteken? Euler bewees dat het niet kon. In de volgende figuur wordt de situatie schematisch voorgesteld.

graaf

Dit is een graaf. De lijnen (wegen/zijden/takken) stellen de bruggen voor. De gekleurde cirkels (knopen) de delen van de stad. Het is niet moeilijk om in te zien dat het probleem onoplosbaar is omdat in elke knoop een oneven aantal wegen aankomt. 

Dit probleem is verwant met het gas-water-elektriciteit-probleem en ook met het nog bekendere vierkleurenprobleem (waar diezelfde Robin Wilson die je in het vorige filmpje aan het werk ziet, een boek over heeft geschreven). En zo zijn er allerlei verbanden te leggen, die Higgins dan ook legt. Bijvoorbeeld met het Erdös-getal.
En ook met ... sudokus.

Peter Higgins is de uitvinder van de cirkel-sudoku waarvan je hier een voorbeeld ziet.

cirkelsudoku

De cirkel is opgedeeld in 5 ringen en in 10 cirkelsectoren. De bedoeling hier is dat je de lege vakjes opvult met de cijfers van 0 tot 9 op zo'n manier dat elk cijfer precies een keer voorkomt in elke ring, en dat elk cijfer ook precies een keer voorkomt in twee naast elkaar gelegen cirkelsectoren. Je vindt nog andere voorbeelden in het boek en op de website van Higgins.

Voor mensen die graag denkpuzzels oplossen: ook de bekende puzzel Instant Insanity wordt besproken in het boek.

instant insanity

Voor meer hierover kan je terecht hier, en hier. Op deze laatste site kan je zelf proberen.

En zo gaat het voort. Higgins slaagt erin al deze dingen en nog veel meer (o.a. ook de logische puzzels met eilandbewoners die altijd de waarheid spreken of altijd liegen, of het Die hard with a vengeance-probleem) met elkaar te verbinden, via de grafentheorie, en hij doet dit in feite zonder veel wiskunde. Wat toch wel een prestatie is.



winning ways
Peter M. Higgins, Nets, puzzles, and postmen, An exploration of mathematical connections.
Oxford University Press (2007).

Een boek over grafentheorie voor de geïnteresseerde leek, maar ook voor de connoisseur: Higgins eindigt met een hoofdstuk voor meer wiskundig aangelegde lezers. In dit hoofdstuk doorloopt hij het hele boek en gaat hij wat dieper in op de wiskunde die er bij komt kijken. Vandaar de dubbele score onderaan.

 

Formuledichtheid: Θ Ο Ο Ο ΟΘ Θ Ο Ο Ο
Moeilijkheidsgraad: Θ Θ Ο Ο Ο 
Score: Θ Θ Θ Θ Ο







Geschreven in Boekenrubriek | 0 Reacties | Vaste link | Afdrukken