26/03/2023
In deze zesde wiskunde tip geef ik eerst een oplossing voor de n vredelievende koninginnen op een n x n bord. Daarna laten we de schaakstukken en het schaakbord even voor wat het is, en gaan we het hebben over de gulden snede, een speciale verhouding van lijnstukken die in de natuur veel voorkomt en harmonie geeft in architectuur, mode, design, muziek enz. Er is een korte introductie en een opgave om een gulden snede en een gulden spiraal te construeren, met passer en lineaal. Daar wordt in de zevende tip uitgebreid op in gegaan.
De uitwerking van het koninginnen probleem staat hieronder. Mocht het niet goed leesbaar zijn, dan raad ik je aan je te abonneren op de nieuwsbrief, waar de tips als mail-attachments in verschijnen. Dit kan eenvoudig via de website:
www.tinekespelenmetwiskunde.nl
Je kunt ook een mailtje sturen naar [email protected]
De opgave is: Plaats 8 koninginnen op een schaakbord van 8 bij 8 zonder dat ze elkaar bedreigen.
Koninginnen kunnen horizontaal, verticaal en diagonaal over een willekeurige afstand elkaar slaan.
Om elkaar niet te bedreigen, mogen ze dus niet horizontaal, verticaal of diagonaal een andere koningin
kunnen bereiken.
Hierbij kun je verschillende technieken gebruiken, variërend van algebra tot het schrijven van een
computerprogramma.
Voor een deel is dit behandeld in tip 5.
We herhalen het hier kort:
Bij een bordje van 2 x 2 kun je geen twee koninginnen plaatsen zonder dat ze elkaar bedreigen.
En het gaat ook niet voor een bordje van 3 x 3 en drie koninginnen.
Voor een bord van 4 x 4 lukt het wel om vier koninginnen zo te plaatsen dat ze elkaar niet bedreigen.
Je kunt dan in de eerste kolom een koningin zetten in de tweede rij, en dit aanvullen met onbedreigde
koninginnen zodat je (2, 4, 1, 3) krijgt.
Hiermee is ook een schrijfwijze voor mogelijke oplossingen gegeven: in kolom 1 komt de koningin op de 2de plek, in kolom 2 op de 4de plek, in kolom 3 op de 1ste plek en in kolom 4 op de 3de plek. Je geeft van links naar rechts de plek van de koningin aan in een rij getallen van 1 t/m 4, zonder herhaling. Dat heet een permutatie van 1 t/m 4.
Voor een bord van n x n geeft iedere permutatie van 1 t/m n een plaatsing van de koninginnen zodat ze elkaar niet horizontaal of verticaal bedreigen. Er zijn n! verschillende permutaties voor een n x n bord, dus bijvoorbeeld voor een schaakbord van 8 x 8 zijn er 8! = 40320 mogelijkheden.
Omdat de permutaties afvallen die twee koninginnen op dezelfde diagonaal opleveren, worden dit er veel minder, maar het is een boel rekenwerk om deze permutaties uit te sluiten.
Hiervoor zijn computerprogramma's geschreven die de permutaties doorzoeken gebaseerd op zoekalgoritmes en backtracking.
Wij beperken ons hier tot het vinden van een oplossing voor een bord van n x n met n ≥ 4.
Een manier om een oplossing voor een bord van n x n te vinden, gaat als volgt:
- begin met de rij van even getallen kleiner of gelijk aan n:
(2, 4, ….n) voor even n, en (2, 4, ….n-1) voor oneven n
- zet daarna de oneven getallen kleiner of gelijk aan n in volgorde erachter:
(1, 3, …. n) voor oneven n, en (1, 3, … n-1) voor even n
- vorm zo de permutatie:
P= (2, 4, …n, 1, 3, …, n-1) voor even n en P = (2, 4, … n-1, 1, 3, … n) voor oneven n
Het is niet handig om met de oneven getallen te beginnen, en daarna de even getallen, want dan krijg je (1, 1) en (n, n) op dezelfde diagonaal, dus een conflict, als n even is.
Voor oneven n krijg je de gespiegelde, en dus dezelfde oplossing.
Zo krijg je een kandidaat voor een oplossing voor plaatsen van n koninginnen op het n x n bord.
Met paardensprongen tussen naastgelegen koninginnen, behalve wanneer je bij rij 1 bent aangekomen.
Voor n = 8 krijg je als kandidaat oplossing: (2, 4, 6, 8, 1, 3, 5, 7). Dit kan nog geen oplossing zijn in dit geval
want (2, 4) en (5, 1) liggen op dezelfde diagonaal. Maar lees vooral door.
We zullen laten zien dat als n geen veelvoud is van 6 met rest 2 of rest 3, dan bedreigen de koninginnen
elkaar niet diagonaal, en is P een oplossing voor het n x n bord.
Dit betekent dat we voor n = 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 18, 19, 23, 24, 25,….
een oplossing hebben gevonden.
Eerst geven we de posities van de koninginnen gebaseerd op P wanneer n even is:
P geeft de posities {(p, 2p) voor 1≤ p ≤½n} en {( (½n) + m, 2m-1 ) voor 1≤ m ≤½n}.
Punten (x1, y1) en (x2, y2) liggen op diagonaal als x2 – x1 = y1 – y2.
Twee punten: (p, 2p) en ((½n) + m, 2m-1) liggen op een diagonaal als (½n) + m – p = 2p – 2m + 1.
Dit betekent dat (½n) = -3m + 3p +1, waaruit volgt: n = 6(p-m) + 2, en n is een veelvoud van 6 met rest 2.
Voor n = 8 geeft p = 2 en m = 1 dat (2, 4) en (5, 1) op een diagonaal liggen.
Voor alle even n ≥ 4 die geen veelvoud zijn van 6 met rest 2, geeft P een oplossing.
Voor oneven n is de redenering vergelijkbaar:
P geeft de posities {(p, 2p) voor 1≤ p ≤½(n-1)} gevolgd door {(½(n-1) + m, 2m-1 ) voor 1≤ m ≤½(n-1) + 1}.
Twee punten: (p, 2p) en (½(n-1) + m, 2m-1 ) liggen op een diagonaal als:
½(n-1) + m – p = 2p – (2m – 1). Dit betekent dat ½(n-1) = 3p – 3m + 1.
Hieruit volgt: n – 1 = 6(p-m) + 2 dus n = 6(p-m) + 3, en n is een veelvoud van 6 met rest 3.
Voor alle oneven n > 4 die geen veelvoud zijn van 6 met rest 3, geeft P een oplossing.
Voor een bord van 8 x 8 levert de manier waarop we voor 4, 5, 6, en 7 een oplossing kregen een conflict op.
Immers (2, 4, 6, 8, 1, 3, 5, 7) geeft twee punten op dezelfde diagonaal: (2, 4) en (5, 1).
Dit kan opgelost worden door de volgorde van de oneven getallen te veranderen in 3, 1, 7, 5. Je wisselt 1 en 3 om, en je zet 5 achteraan, anders wordt koningin in kolom 7 bedreigd door de koningin in kolom 5.
Dit geeft als oplossing: (2, 4, 6, 8, 3, 1, 7, 5).
Dit recept werkt voor alle n waarbij deling door 6 een rest oplevert van 2: wissel 1 en 3 om, en zet 5 achteraan.
In het geval dat n een veelvoud van 6 is met 3 als rest, zul je iets meer moeten corrigeren: verplaats 2 naar het eind van de even lijst,
en verplaats 1 en 3 naar het eind van de oneven lijst.
Voor n = 9 geeft dit als oplossing: (4, 6, 8, 5, 7, 9, 1, 3).
Naast het vinden van een oplossing is het ook interessant te zoeken naar alle mogelijke oplossingen. Dit kan door een computerprogramma te schrijven dat alle permutaties systematisch doorzoekt, en ze goedkeurt als er geen diagonaal-conflict is.
Er zijn 12 fundamenteel verschillende oplossingen van het probleem (rotatie en reflectie niet meegeteld)
op een schaakbord van 8 x 8.
Dit en meer staat in:
https://gaz.wiki/wiki/nl/Eight_queens_puzzle
Voor de volgende tip verlaten we het schaakspel, en gaan we het hebben over de gulden snede. De gulden snede is de verhouding a/b van een lijnstuk dat verdeeld is in een kort stuk b en een lang stuk a, zo dat de verhouding van a tot b gelijk is aan de verhouding van de totale lengte tot a. Dus a : b = (a+b) : a. Hieruit kun je berekenen dat a : b ongeveer gelijk is aan 1,618. Deze verhouding is het gulden getal ҩ (phi).
Opgave: construeer de gulden snede met passer en lineaal, en probeer een gulden spiraal te maken.
Hier komen we in tip 7 uitgebreid op terug.
Gratis abonneren op deze nieuwsbrief kan eenvoudig op de website: www.tinekespelenmetwiskunde.nl
Of stuur me een mailtje: [email protected] dan krijg je een bevestigingsmail, en na je
bevestiging kom je op de mailinglist van de nieuwsbrief.