Schaken is Wiskunde ? Notities (6)
Hans Meijer - 15 May 2010
"Schaken is wiskunde (6)" door Hans Meijer In mijn vorige column "Schaken is wiskunde (5)" heb ik een probleem van Noam Elkies besproken dat hij in "New directions in enumerative chess problems" (2005) publiceerde. Hieronder geef ik een tweede probleem (met een extra pion op a6) uit dit artikel. Het is nauw verwant aan het eerste.  N.D. Elkies (2003) De vraag is ook hier wat is de n-de term van de reeks die het aantal manieren waarop wit in exact n-zetten schaakmat kan forceren weergeeft? We negeren de 50-zetten regel en de regel dat het remise is als de stelling drie keer herhaald wordt. We zien dat in dit probleem de witte koning tussen a1 en b1 pendelt en dat de zwarte koning heen en weer wandelt langs de velden c8-d8-e8-f8. Aan het slot van de zettenreeks zet wit zwart met Pd7 mat. Als we dit probleem vergelijken met het "loper-probleem" uit mijn vorige column zal het meteen duidelijk zijn dat ook hier de Fibonacci rij het antwoord op de gestelde vraag is: 1, 1, 2, 3, 5, 8, 13, ... met mat in 1, 2, 3, 4, 5, 6, 7, ... zetten. Tot zover is er niets nieuws onder de zon. Een onderzoeker probeert echter altijd iets verder te kijken of, als hij of zij in de olie zit, iets dieper te boren. Dit zoeken leidde naar onderstaande stelling. In deze stelling staat ook veld g8 de zwarte koning voor zijn wandelingen ter beschikking. De voor de hand liggende vraag is uiteraard wat nu het antwoord op bovenstaande vraag is.  J.W. Meijer (2010; naar Elkies) Zoals gebruikelijk bij een onderzoek beginnen we met enkele voorbeelden van zetten reeksen: (a) 1.Pd7# en a(1) = 1; (b) 1.Kb1 Kd8 2.Pd7 # en a(2) = 1; (c) 1.Kb1 Kd8 2.Ka1 Ke8 3.Pd7# en 1.Kb1 Kd8 2.Ka1 Kc8 3.Pd7# en a(3) = 2; (d) 1.Kb1 Kd8 2.Ka1 Ke8 3.Kb1 Kf8 4.Pd7# en 1.Kb1 Kd8 2.Ka1 Ke8 3.Kb1 Kd8 4.Pd7# en 1.Kb1 Kd8 2.Ka1 Kc8 3.Kb1 Kd8 4.Pd7# en a(4) = 3.
In "Schaken is wiskunde (5)" heb ik u aangeraden het boekje "Introductory Graph Theory" van Gary Chartrand (1985) te kopen en ik ga er vanuit dat het inmiddels menige salontafel siert. Uw gasten zien dan meteen dat ze niet bij zomaar iemand op bezoek zijn. Op de pagina's 218-220 is te lezen hoe we de verschillende wandelingen met lengte n van de zwarte koning kunnen berekenen.  Graaf G voor de wandelweg van de zwarte koning Dit gaat als volgt. We representeren de velden waarover de zwarte koning heen en weer wandelt met graaf G. De verzameling van de knopen van graaf G is V(G): {v1=c8, v2=d8, v3=e8, v4=f8, v5=g8}. De verbindingsmatrix A van graaf G is A = [[0,1,0,0,0], [1,0,1,0,0], [0,1,0,1,0], [0,0,1,0,1], [0,0,0,1,0]]. Voor het bepalen van de verschillende wandelingen met lengte n van de zwarte koning van vi naar vj moeten we de n-de macht van matrix A, d.w.z. A^n, berekenen. De elementen van de A^n(i,j) matrix representeren namelijk het aantal verschillende vi-vj wandelingen met lengte n in G. Zo representeert A^n(1,3) het aantal verschillende wandelingen met lengte n van veld c8 naar e8. Het totale aantal wandelingen van de zwarte koning met lengte n van c8 naar c8, d8, e8, f8 en g8 is a(n) = A^n(1,1) + A^n(1,2) + A^n(1,3) + A^n(1,4) + A^n(1,5). Met het wiskunde pakket Maple (zie maplesoft.com) vinden we hiervoor de reeks 1, 2, 3, 6, 9, 18, 27, 54, 81, 162, 243, 486, 729, ... , hetgeen A038754 in de OEIS is (oeis.org/classic/A038754). Voor de reeks wit geeft mat in exact n zetten moeten we aan deze reeks als eerste term nog een 1 toevoegen. De reeks die we zoeken is dus 1, 1, 2, 3, 6, 9, 18, 27, 54, ... met mat in 1, 2, 3, 4, 5, 6, 7, 8, 9, ... zetten. De termen van deze reeks kunnen we voor n => 2 met de formules a(2n-2)=3^(n-2) en a(2n-1)=2*3^(n-2) berekenen. Waar vroeger het met de hand manipuleren van matrices slavenarbeid was is het manipuleren van matrices met Maple een waar genoegen. Werk van dagen verricht Maple in luttele seconden. Net als op het schaakbord vind je met wat rommelen soms iets fraais. Zo stelt de reeks a(n) =A^n(1,1) + A^n(1,2) + A^n(1,3) + A^n(1,4) de wandelingen met lengte n van de zwarte koning naar de velden c8, d8, e8 en f8 voor. Deze reeks staat niet in de OEIS, maar tot mijn verbazing staat de reeks b(n) = a(n) - 1 er wel in. Het is de merkwaardige reeks A048328: 1, 2, 4, 8, 13, 26, 40, 80, 121, 242, 364, ... (oeis.org/classic/A048328). De termen van deze reeks blijken repetities van dezelfde cijfers (repdigits) in het drietallig stelsel te zijn. In het drietallig stelsel beschikken we over de cijfers 0, 1 en 2. Ook in dit stelsel hangt de specifieke waarde van een cijfer af van zijn positie in een getal. Zo is 13 [tientallig] = 9 + 3 + 1 = 1*3^2 +1*3^1 + 1*3^0 = 111 [drietallig], 80 [tientallig] = 54 + 18 + 6 + 2 = 2*3^3 + 2*3^2 + 2*3^1 + 2*3^0 = 2222 [drietallig]. In het drietallig stelsel ziet bovenstaande reeks er als volgt uit: 1, 2, 11, 22, 111, 222, 1111, 2222, 11111, 22222, ... . Tot slot kunnen we ons de vraag stellen wat er gebeurt als we het zwarte paard op h8 van het bord verwijderen. De verzameling van de knopen van graaf G, d.w.z. de velden waarover de zwarte koning wandelt, is nu V(G): {v1=c8, v2=d8, v3=e8, v4=f8, v5=g8, v6=h8}. De verbindingsmatrix van G is A = [[0,1,0,0,0,0], [1,0,1,0,0,0], [0,1,0,1,0,0], [0,0,1,0,1,0], [0,0,0,1,0,1], [0,0,0,0,1,0]]. Het aantal verschillende wandelingen met lengte n van de zwarte koning wordt bepaald door a(n) = A^n(1,1) + A^n(1,2) + A^n(1,3) + A^n(1,4) + A^n(1,5) + A^n(1,6). Dit leidt naar reeks 1, 2, 3, 6, 10, 19, 33, 61, 108, 197, 352, 638, 1145, ... . Voor de-mat-in-n-zetten reeks voegen we hier nog een 1 als eerste term aan toe en zo komen we uit bij A028495 in de OEIS (oeis.org/classic/A028495). Bovenstaande leidt tot de volgende hypothese: Als we voor dit eenvoudige probleem al een beroep moeten doen op grafen- en matrixtheorie dan heb ik een sterk vermoeden dat de wiskunde voor vrijwel alle iets ingewikkelder schaakproblemen nog uitgevonden moet worden. |
