2014 DOMINANTIE OP EEN SCHAAKBORD Jonas Vantrappen & Stijn Wierinckx Heilige- Drievuldigheidscollege Leuven Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Inhoud Inleiding......................................................................................................................................................... 2 Het begrip dominantie .................................................................................................................................. 3 Dominantie met torens ................................................................................................................................. 3 Dominantieonderzoek .............................................................................................................................. 3 Dominantie met lopers ................................................................................................................................. 5 Dominantieonderzoek .............................................................................................................................. 5 Dominantie met koningen ............................................................................................................................ 6 Dominantieonderzoek .............................................................................................................................. 6 Dominantie met paarden .............................................................................................................................. 7 Het dominantieprobleem ......................................................................................................................... 7 Dominantie met dames ................................................................................................................................ 9 Het dominantieprobleem ......................................................................................................................... 9 Dominantie met de beginstukken op een 8x8 schaakbord ........................................................................ 11 Efficiëntie ................................................................................................................................................ 12 Hypothese: torens in de hoeken ............................................................................................................. 13 Dominantie voor 6x6 schaakbord ........................................................................................................... 14 Combinatie 1: koning, 2 paarden en 2 lopers ......................................................................................... 14 Combinatie 2: koning, 2 paarden, een loper en de dame ...................................................................... 15 Positie 1 ............................................................................................................................................... 15 Positie 2 ............................................................................................................................................... 15 Positie 3 ............................................................................................................................................... 16 Positie 4 ............................................................................................................................................... 16 Positie 5 ............................................................................................................................................... 16 Positie 6 ............................................................................................................................................... 17 Besluit ..................................................................................................................................................... 17 Eindwoord ................................................................................................................................................... 18 1 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Inleiding Er was eens, in een prachtig land heel ver hier vandaan, een land waar zelfs de dieren konden spreken, een konijn. Het konijn heette Kasparov en had een wit-zwart geruite vacht. Armoede en werkloosheid kende men niet in dit land, dus had Kasparov zijn leven lang, tot aan zijn welverdiende pensioen, een rustig maar bevredigend jobje gehad in de bankensector. Verleden jaar echter was de tijd voor Kasparov gekomen. De tijd om op pensioen te gaan. Dit pensioen heeft zijn leven grondig veranderd. Het toeval wou dat Kasparov een mooie digitale tv had waarop hij allerhande programma’s kon bekijken. Gepensioneerde konijnen zijn net als gepensioneerde mensen en doen weinig andere dingen dan lezen en tv kijken. Op een dag was Kasparov weer eens bezig met van het ene kanaal naar het andere te zappen tot plots zijn aandacht werd getrokken door een schaaktoernooi. Kasparov kende dit spel vaag van uit zijn kindertijd, maar was er sinds toen niet meer mee in aanraking gekomen. Nu echter werd zijn fascinatie plotsklaps getrokken door dit prachtige spel. Kasparovs mateloze interesse voor wiskunde en zijn drang om te ontdekken en onderzoeken deed hem binnen de 5 minuten naar de winkel lopen en terugkomen met een splinternieuw schaakbord. Gedaan met lezen, gedaan met tv kijken. Vanaf nu zou Kasparov zich met niets anders bezighouden dan schaken. Zo kwam Kasparov terecht in de wereld van het schaken. Een wereld die nooit eindigt en waar altijd nieuwe dingen ontdekt kunnen worden. Na wat potjes tegen zichzelf te hebben geschaakt, was de tijd rijp om het pad van de wijsheid op te gaan: het pad van de wiskunde. Schaken is een spel waarvan we talloze wiskundige aspecten kunnen ontdekken. Kasparov was echter vooral geïnteresseerd in het domineren. Domineren? Domineren houdt in dat het mogelijk is om na één zet een bepaalde tegel te bereiken met een bepaald schaakstuk. Één vraag echter liet Kasparov niet met rust. Wanneer hij ’s avonds naar bed ging, wanneer hij ’s ochtends onder de douche stond, wanneer hij ’s middags de tafel dekte. Dag in dag uit. Hij werd er niet door losgelaten. Deze vraag luidde als volgt: Is het mogelijk om met de 8 beginstukken van een schaakspel het volledige 8x8-schaakbord te domineren? Hij startte zijn onderzoek en schreef het neer in zijn dagboek. Wij – Stijn Wierinckx en Jonas Vantrappen – zijn de nederige vinders van dit prachtige werk en we vonden het wel de moeite waard om te publiceren. 2 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Het begrip dominantie Liefste dagboek, Is het mogelijk om met de 8 normale stukken van een schaakspel het volledige 8x8 schaakbord te domineren? Deze vraag laat me niet los. Voor ik mijn onderzoek kan beginnen, is het noodzakelijk om een goede en duidelijke definitie van dominantie op een schaakbord te hebben. In de inleiding werd als definitie gegeven: ‘dat het mogelijk is om na 1 zet elke tegel op het schaakbord te bereiken.’ Een degelijke definitie maar niet bevredigend genoeg. Als we heel het veld volzetten met 64 paarden, dan kunnen we ook na 1 zet elke tegel op het schaakbord bereiken. Dit is wel domineren, maar niet het domineren dat interessant is voor dit onderzoek. Wat voor mij belangrijk is, is de kleinste dominerende verzameling, en het aantal stukken dat deze bevat. Dit aantal stukken noemen we het dominantiegetal. Voordat ik mijn levensvraag probeer te beantwoorden, is het aangewezen om te beginnen met het begrip dominantie verder uit te spitten en elk stuk eerst apart te bekijken. Dominantie met torens Liefste dagboek, De toren kan beschouwd worden als het simpelste schaakstuk. Het kan zich over een onbepaald aantal velden zowel horizontaal als verticaal verplaatsen. Perfect om mee te beginnen als opwarmertje. Dominantieonderzoek Het dominantieprobleem met torens is ideaal om het probleem te schetsen. Het is duidelijk dat men om een 8x8 schaakbord te domineren minstens 8 torens nodig heeft. Indien men minder torens zou gebruiken, is er een rij en kolom waarop geen toren staat. Het hele bord is dus niet gedekt of gedomineerd. Algemeen kan men dus stellen dat om een nxn schaakbord te domineren men minstens n torens nodig heeft. 3 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Het is duidelijk dat er enorm veel verschillende dominante opstellingen zijn, we kunnen zelfs het exacte aantal berekenen. Bij een nxn schaakveld weten we dat we minstens n torens nodig hebben om een dominante opstelling te bekomen. Bovendien moeten zowel alle n kolommen als alle n rijen een toren bevatten. We kunnen dus stellen dat het aantal manieren waarop n torens kunnen worden geplaatst (waarbij er één in elke kolom staat) gelijk is aan . Dit geldt eveneens voor het aantal manieren dat n torens kunnen worden geplaatst als er telkens één in elke rij staat. Het aantal verschillende manieren is dan . Dit is echter niet correct, we hebben namelijk een aantal opstellingen dubbel geteld. Deze opstellingen zijn de opstellingen waarbij er een toren in elke kolom staat en een toren in elke rij. Er zijn n! van deze opstellingen, aangezien er n velden zijn om een toren in de eerste kolom te plaatsen en n-1 velden om een toren in de tweede kolom te plaatsen (in een andere rij dan de eerste toren). Indien we zo de 8 kolommen afgaan en de aantallen vermenigvuldigen, komen we op n! opstellingen. Het totaal aantal mogelijkheden is dus . Voor een 8x8 bord komt dit neer op 33 514 112 verschillende dominante opstellingen. 4 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Dominantie met lopers Liefste dagboek, Dominantie met torens heeft geen geheimen meer voor mij. Daarom besloot ik me vandaag aan dominantie met lopers te zetten. Lopers en torens zijn namelijk bijna hetzelfde. Neem nu de witveldige loper en kijk naar de volgende afbeelding. We kunnen de witte velden van de eerste figuur hertekenen als de tweede figuur. Eigenlijk is de loper dus gewoon een toren die op een eigenaardig veld staat! Dominantieonderzoek Laten we nu het dominantieprobleem bekijken op een 8x8 bord. De afbeelding hierboven laat ons zien dat een loper zich gedraagt als een toren, en dus ook hetzelfde dominantiegetal heeft. In de afbeelding zien we dat er een rechthoekig 4x5 veld gedekt moet worden. Als dit gedekt is, zijn alle witte velden gedekt. Ons bewijs van de torens zegt dat we voor een 4x5 veld 4 torens nodig hebben. Bijgevolg hebben we om alle witte velden te domineren juist 4 lopers nodig. Aangezien er perfecte symmetrie tussen de witte en zwarte velden bestaat, hebben we ook 4 lopers nodig voor alle zwarte velden. Doordat 4+4=8, hebben we 8 lopers nodig om een 8x8 veld te domineren. Voor een nxn veld stuitte ik op een klein probleempje. Er is namelijk een verschil tussen een even of een oneven n. Dus is het het makkelijkste om het bewijs op te splitsen in twee delen. Voor een even n kunnen we heel gemakkelijk het bewijs van een 8x8 veld veralgemenen. We krijgen namelijk altijd na het ‘trukje’ waarbij we 45° draaien en lopers tot torens omvormen, een x veld, waarvoor we lopers nodig hebben om het volledig te domineren. Bij een even n is er een mooie symmetrie, en ( ) ( ) , dus ons dominantiegetal is n. Voor een oneven n werkt de redenering op exact dezelfde manier, alleen moeten we hem opsplitsen en twee keer uitvoeren. We kunnen n schrijven als 2k + 1. Een van de twee kleuren zal dan in het midden een (k+1)x(k+1) veld bevatten en dus k+1 lopers nodig hebben. De andere kleur zal in het midden een (k)x(k) veld bevatten en slechts k lopers nodig hebben. (k+1) + k = 2k + 1 = n. Ik kwam dus zeer mooie resultaten uit voor het dominantiegetal van lopers. Een nxn veld heeft n lopers nodig om gedomineerd te worden. Prachtig! 5 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Dominantie met koningen Liefste dagboek, Vandaag was ik heel erg enthousiast toen ik begon aan mijn werk. Ik ging namelijk dominantie met koningen bekijken. In mijn ogen het belangrijkste stuk op het veld. Het stuk dat altijd beschermd moet zijn en zelf bijna nooit moet aanvallen. Ik dacht dat dit wel heel speciale resultaten zou opleveren. Mijn bevindingen waren helaas ronduit teleurstellend. Koningen zijn best saai... Dominantieonderzoek Zoals gewoonlijk begon ik met een 8x8 bord. Al snel had ik door dat 1 koning optimaal 9 velden dekt, namelijk het vierkant waarin hij in het midden staat. Het makkelijkste is dus om het 8x8 veld op te delen in allemaal vierkantjes van 3 op 3 en telkens in het midden een koning te plaatsen. Op deze manier heb je 9 koningen nodig om een 8x8 veld te domineren. Piece of cake. Op een nxn veld waren de resultaten bijna frustrerend. Voor een 9x9 veld heb je ook 9 koningen nodig, en dan ziet het er mooi uit, zelfs perfect. Voor een 7x7 veld heb je echter ook de volle 9 koningen nodig. Algemeen betekent dit dat we voor een nxn bord telkens een veelvoud van 3, zo dicht mogelijk, maar toch groter dan n, moeten zoeken. Dit veelvoud delen we door drie en hiervan nemen we het kwadraat. Het veelvoud van 3 is er doordat een koning 3 velden in de breedte of hoogte kan dekken, het kwadraat is er omdat we altijd een vierkant hebben, waardoor we dus de zijde moeten kwadrateren. Stel n = 3k, dan is het dominantiegetal k² Stel n = 3k – 1, dan is het dominantiegetal k² Stel n = 3k – 2, dan is het dominantiegetal k² 6 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Dominantie met paarden Liefste dagboek, Het paard heb ik altijd het meest interessante schaakstuk gevonden, heel leuk dus voor een dominantieonderzoek. Een paard kan zich verplaatsen door één veld horizontaal of verticaal en vervolgens twee velden voorwaarts of achterwaarts naar links of naar rechts te gaan. Van bovenaan gezien lijkt de paardzet op een L. Eigenlijk kunnen we de paardzet ook vergelijken met het omgekeerde van de damezet. Het dominantieprobleem Paardzet Damezet Net als bij de torens ga ik onderzoeken hoe en met hoeveel paarden men een veld kan domineren. Uiteraard zal dit verschillen van schaakbord tot schaakbord. Hieronder een overzicht van de verschillende nxn schaakborden voor n=3 tot n=10. (Het is onmogelijk om een 2x2 veld te domineren aangezien een paard zich niet kan verplaatsen binnen deze kleine ruimte). Zoals enigszins te verwachten viel, zijn de dominante opstellingen van paarden vaak zeer symmetrische vormen. Verder valt op dat voor n groter dan 5 het dominantiegetal steeds met 2 vergroot. Ook is het opvallend dat bij het 3x3 schaakbord het middelste paard eigenlijk geen enkel veld dekt, het stuk is echter wel nodig om het middelste veld te ‘dekken’. 7 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Vanaf het 11x11 schaakbord wordt alle symmetrie echter overboord gegooid. Hierdoor wordt het heel erg moeilijk om nog een optimale dominante opstelling te vinden. Toch zijn er al enkele doorbraken geweest: in 1971 vond Bernard Lemaire de optimale dominante opstelling voor het 11x11 schaakbord en in 1987 vonden Eleanor Hare en Stephen Hedetniemi een algoritme om het dominantiegetal voor rechthoekige schaakborden te berekenen. De dominantie van paarden op een schaakbord is dus een onopgelost probleem binnen de wiskunde. De dominante opstelling voor het 11x11 schaakbord, gevonden door Bernard Lemaire 8 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Dominantie met dames Liefste dagboek, Het mooiste heb ik voor het laatste bewaard. De dame, het schaakstuk dat het beste van de toren en de loper combineert. Zeer interessant voor dominantie, maar ook zeer ingewikkeld. Zo ingewikkeld dat ik geen verregaand onderzoek ga voeren naar het nxn veld, maar het beperkt ga houden, en vooral naar een 8x8 veld ga kijken. Het dominantieprobleem Om een dominante opstelling met dames voor een 8x8 veld te vinden, moeten we best eerst gewoon wat proberen. Al snel vind je opstellingen waarbij je maar 5 dames nodig hebt om het hele bord te domineren. Bijvoorbeeld onderstaande opstellingen. Op deze manier zijn er maar liefst 4860 oplossingen. Vooral opvallend zijn de eerste twee oplossingen, omdat deze de mogelijkheid lijken te geven om een – zo lijkt – optimale uitbreiding te geven naar het nxn veld. Laten we eerst de eerste opstelling een beetje beter bestuderen. We nemen een nxn veld met een dominante opstelling waarbij alle dames op de witte diagonaal staan. We noemen K de verzameling van alle kolommen (en rijen) die geen dame bevatten. Neem nu kolom (of rij) i en j in K. Aangezien i en j in K zitten, bevatten ze geen dame. Tegels (i,j) en (j,i) moeten schuin gedekt worden, want in hun rij of kolom staat geen dame. De diagonaal is helemaal wit, dus tegels (i,j) en (j,i) moeten ook wit zijn, anders kunnen ze niet schuin gedekt worden. Hieruit volgt dat de som van i en j even moet zijn. Dit geldt voor eender welke i en j in K, dus álle getallen in K moeten ofwel allemaal even ofwel allemaal oneven zijn. Een combinatie is niet mogelijk. De dame die tegel (i,j) en (j,i) dekt, moet zich ook op de diagonaal bevinden, en nog specifieker, op tegel ( , ). Dit betekent dat voor alle lege kolommen i en j, de kolom die zich precies ertussen bevindt, niet leeg is. Zulk verschijnsel noemt men een middelpuntvrije verzameling, een verzameling waar voor elke twee getallen die hij bevat, hun middelpunt niet in de verzameling zit. Hieruit kunnen we concluderen dat K een willekeurige middelpuntvrije verzameling van 1, 2, 3, ..., n is (voor een nxn bord). Heel leuk, maar helaas bij grotere schaakborden niet de opstelling met het minste dames. 9 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Nu is het de beurt aan het tweede voorbeeld. Merk op dat deze opstelling ook een 10x10 bord zou domineren, namelijk als we onderaan en rechts nog een rij bijvoegen. Nog leuker wordt het als je naar de volgende afbeelding kijkt! Voor een 15x15 bord hebben we slechts 9 dames nodig! Deze opstelling ziet er vrij perfect uit! We hebben echter weer pech. Ookal lijkt deze methode zo mooi, als we verder gaan naar een 21x21 bord, zijn er constructies die minder dames nodig hebben dan de 13 in deze constructie. Nog uren zou ik verder kunnen gaan over dames; bovengrenzen, ondergrenzen, ... ik zou nog gerust 20 pagina’s kunnen vullen, maar dat is niet waar dit onderzoek om draait. Ik heb elk stuk apart bekeken. Tijd om alles samen te voegen en te kijken of we hier mooie dingen uit kunnen halen. 10 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Dominantie met de beginstukken op een 8x8 schaakbord Liefste dagboek, Na enkele inleidende onderzoeken kan ik eindelijk beginnen aan het echte werk. Het betreft een dominantieonderzoek van de combinatie van de 8 verschillende schaakstukken die men aan het begin van een schaakspel ter beschikking krijgt: 2 paarden, 2 lopers, 2 torens, een koningin en de koning. Ik laat de pionnen buiten beschouwing omdat ze niet interessant zijn voor een dominantieonderzoek. Om wat voeling te krijgen met deze nieuwe vorm van dominantie ga ik meteen met de praktijk aan de slag. Hoe kan ik heb hele schaakbord opvullen? Intuïtief heb ik het gevoel dat de torens in de hoeken geplaatst moeten worden. Zo ‘verkleinen’ ze het bord namelijk tot een 6x6 schaakbord waardoor er nog maar 36 velden gedomineerd moeten worden. Dit lijkt op het eerste zicht een haalbare opdracht. Op dit moment heb ik nog een heel machtig wapen achter de hand: de dame. Met behulp van de dame kan ik het schaakbord zelfs verkleinen tot een 5x5 bord, waarbinnen een diagonaal reeds gedekt is. Ik heb nu dus nog een koning, 2 paarden en 2 lopers over. Na heel wat puzzelen ben ik er in geslaagd om een dominante opstelling te vinden. Straffer nog: er zijn zelfs meerdere dominante opstellingen. Dit had ik eerlijk gezegd niet verwacht. Hieronder drie dominante opstellingen, er zijn er wellicht meer. Doordat het vinden van deze dominante opstellingen al bij al vlot verlopen is, vraag ik me af of het niet mogelijk is om het dominantiegetal (8) te verkleinen. Met andere woorden: is het mogelijk om een bepaald stuk niet te gebruiken en toch het hele schaakbord te domineren? Om het dominantiegetal te kunnen bepalen, gaan we onderzoeken of we het 8x8 schaakbord kunnen domineren met 7 beginstukken. Na wat puzzelen merken we dat dit niet evident is. Dit onderzoek vraagt dan ook een meer structurele en theoretische aanpak. 11 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Efficiëntie Om dit onderzoek tot een goed einde te kunnen brengen heb ik nood aan een nieuw begrip. Ik heb namelijk nood aan een manier om het intuïtieve gevoel waarmee je een bepaald schaakstuk op een veld plaatst te verklaren. Dit begrip noem ik efficiëntie. De efficiëntie van een schaakstuk is het aantal velden dat het stuk dekt (in een bepaalde opstelling) over het aantal velden dat dit stuk in haar meest optimale positie dekt. Ik kan dus stellen dat de blauwe koning in nevenstaande opstelling een efficiëntie heeft van 4/9. De koning dekt namelijk 4 velden (inclusief het eigen veld), terwijl hij in zijn optimale positie 9 velden dekt. De groene koning daarentegen heeft een efficiëntie van 9/9 = 1. Hij bevindt zich namelijk op een van zijn meest efficiënte posities. We merken dus dat we een koning best niet op de rand van het schaakbord plaatsen. Dit verklaart o.a. waarom het dominantiegetal van koningen voor een 7x7, 8x8 en 9x9 veld gelijk is. Bij het 7x7 veld zijn er namelijk maar 4 koningen met een efficiëntie van 1, de 5 andere staan op de rand en hebben een efficiëntie van 3/9. Bij het 8x8 veld zijn er opnieuw 4 koningen met een efficiëntie van 1, de andere 5 hebben een efficiëntie van 6/9. Bij het 9x9 veld hebben alle koningen echter een efficiëntie van 1. Met behulp van het begrip efficiëntie ga ik proberen aantonen dat het niet mogelijk is om met minder dan de 8 beginstukken een schaakbord te domineren. Om dit te bewijzen zal ik eerst aantonen dat de torens hoogst waarschijnlijk in de hoeken moeten, we houden dan een 6x6 bord over. Als dit 6x6 veld niet kan gedomineerd worden door 5 van de overblijvende stukken, kan het 8x8 schaakbord niet gedomineerd worden met 7 of minder beginstukken. Het dominantiegetal is dan 8. 12 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Hypothese: torens in de hoeken Als elk stuk op haar meest efficiënte positie zou staan dan kunnen de schaakstukken samen 89 velden dekken. Dit zou – puur theoretisch – betekenen dat we 1 of 2 stukken zouden kunnen laten vallen om de 64 velden te kunnen dekken. Hypothese: De twee torens (of een dame) moeten telkens in een hoek, zodat we een 6x6 veld krijgen. Aantal velden dat een stuk op haar meest efficiënte positie kan dekken Paard (x2) Koning Loper (x2) Toren (x2) Dame Totaal Als we de efficiëntie van een stuk nu anders bekijken: niet in functie van het aantal velden dat het maximaal kan dekken, maar in functie van het aantal velden dat het stuk op de rand van het schaakbord kan dekken. We kunnen dit laterale efficiëntie noemen. Paard (x2) Koning Toren (x2) Loper (x2) Dame Totaal 9 9 10 11 20 89 Overzicht laterale efficiëntie Meest efficiënt Niet in hoek 4 4 5 5 15 4 4 4 16 8 67 37 Stel dat de torens (of dame) niet in de hoek staan: We moeten 28 zijkanten dekken en we kunnen er – theoretisch – 37 dekken. Dit betekent dat we maar 9 velden mogen ‘verliezen’ en dat elk stuk dus op een voor zichzelf zeer (lateraal) efficiënte positie moet staan. Indien we dit toepassen op het schaakbord merken we dat het mogelijk is om alle randvelden te dekken zonder de torens in de hoeken te plaatsen. Het is volgens mij echter onmogelijk om de rest van het veld te domineren met deze opstellingen. Neem bijvoorbeeld nevenstaande opstelling. Alle randvelden zijn gedekt, maar het volledige schaakbord is duidelijk niet gedomineerd. Om effectief te bewijzen dat de torens in de hoeken moeten, zijn we verplicht om 5040 mogelijkheden af te gaan. Een combinatie van Paard Paard Toren Toren Koning Koningin Loper Loper waarbij we beginnen bij de eerste van de rij en elk schaakstuk telkens zo plaatsen dat het zo veel mogelijk zijkanten dekt. Als we dan geen dominante opstelling tegenkomen na 5040 opstellingen, is bewezen dat de torens in de hoek moeten. Ik stel echter voor dat we ons niet aan zo’n sisyfusarbeid ten prooi gaan werpen, maar gewoon veronderstellen dat de hypothese correct is. 13 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Dominantie voor 6x6 schaakbord Aangezien we (beargumenteerd) veronderstellen dat de torens in de hoeken staan, houden we een 6x6 schaakbord over. Indien we dit bord kunnen opvullen met 5 van de overige stukken, is het dominantiegetal 7 en dus kleiner dan 8. De overige stukken zijn: Dame, 2 lopers, 2 paarden en de koning Hieruit kunnen we 4 verschillende combinaties van 5 stukken halen: 1) 2) 3) 4) 2 paarden, 2 lopers en de koning 2 paarden, een loper, de dame en de koning Een paard, 2 lopers, de dame en de koning 2 paarden, 2 lopers en de dame Het komt er nu op aan om voor elk van deze combinaties te onderzoeken of hiermee een 6x6 bord gedomineerd kan worden. Combinatie 1: koning, 2 paarden en 2 lopers De eerste combinatie is de combinatie zonder dame. De afwezigheid van de dame zorgt ervoor dat de combinatie slechts 21 randvelden kan dekken. Dit is erg weinig aangezien er op een 6x6 veld 20 randvelden zijn. Elk stuk zal dus op een zeer (lateraal) efficiënte positie moeten staan, er mag namelijk maar 1 veld ‘verloren’ gaan. Laterale efficiëntie Meest efficiënt Paard (x2) 4 Koning 5 Loper (x2) 4 Totaal 21 Het lijkt dus niet waarschijnlijk dat het veld gedomineerd zal kunnen worden, toch zullen we het eens proberen. We weten dat de koning schuin naast een hoek moet staan, indien hij daar niet zou staan dan zou hij een laterale efficiëntie hebben van 3/5, waardoor er 2 velden verloren gaan. Het zou dus al niet meer mogelijk zijn om het hele veld te domineren. Na de koning plaatsen we een paard. Dit paard kunnen we opnieuw maar op één positie zetten om geen veld te verliezen en dus 4 velden te dekken. Nu is er echter geen enkele positie meer over waar ofwel een paard, ofwel een loper op haar meest efficiënte positie staat. Aangezien we nog 3 stukken moeten plaatsen zullen we dus meer dan één veld verliezen, waardoor het 6x6 veld niet gedomineerd kan worden met deze combinatie van beginstukken. Koning Paard 1 14 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Combinatie 2: koning, 2 paarden, een loper en de dame Met deze combinatie lijkt het al een stuk haalbaarder om het veld te domineren. De dame kan dan ook veel meer velden dekken dan een loper. Toch brengt deze dame ook wel enkele problemen met zich mee. Om dit te illustreren onderscheiden we 6 gevallen. Deze 6 gevallen zijn de 6 verschillende posities dat de dame kan innemen op het 6x6 schaakbord. Positie 1 In nevenstaande afbeelding is te zien dat de dame al heel veel velden dekt. Er is echter ook te zien dat er heel wat velden ‘geïsoleerd’ zijn: ze liggen tussen reeds gedekte velden. Nu plaatsen we de koning, rechtsonder op positie F3 lijkt de meest voor de hand liggende plaats. De koning kan daar namelijk 6 ongedekte velden dekken. Met andere woorden: de efficiëntie van de koning is op die positie het grootst. Helaas merken we dat we met de overblijvende stukken (2 paarden en een loper) de resterende velden niet kunnen dekken. We merken zelfs dat eender waar we de koning plaatsen, de resterende velden nooit gedekt kunnen worden met de overblijvende stukken. Het is dus onmogelijk om het schaakbord te domineren als de dame op positie 1 staat. Positie 2 Als de dame op positie 2 staat, krijgen we te maken met hetzelfde probleem. De vier velden bovenaan rechts kunnen enkel gedekt worden door ofwel een paard en een loper ofwel de koning. Veronderstel dat we de velden dekken met de koning, dan hebben we nog een loper en twee paarden over om de resterende velden te dekken. Opnieuw is het duidelijk dat dit niet lukt. De dame kan dus niet op positie 2 staan. Dame Koning 15 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Positie 3 Indien de dame op positie 3 staat, krijgen we een mooi patroon, de dame dekt net als op de vorige posities al heel wat velden. We gaan op dezelfde manier te werk als bij de vorige posities. We merken dat de 3 velden bovenaan rechts (en onderaan links) enkel gedekt kunnen worden met een loper en een paard, of een koning. Stel dat we de 3 velden bovenaan rechts dekken met een paard en een loper (dan moet de koning de 3 velden onderaan links dekken). We krijgen dan nevenstaande opstelling. Het paard moet sowieso op 5F staan, terwijl de loper op F7, E6, D5, C4 of B3 moet staan. Het maakt echter niet uit op welke van deze 5 posities de loper staat. Dame Paard Loper We hebben nu dus nog een koning en een paard over om de overblijvende velden te domineren. Het is opnieuw duidelijk dat dit niet mogelijk is. We kunnen het schaakbord dus niet domineren met 7 stukken indien de dame op positie 3 staat. Positie 4 Op positie 4 dekt de dame al heel wat minder velden (doordat ze op de rand staat). We krijgen hierdoor rechtsonder een groep van 5 ongedekte velden. Deze velden moeten door de koning gedekt worden, indien de koning ergens anders zou staan, dan zouden we 2 paarden en een loper nodig hebben om de velden te dekken. Het is duidelijk dat de koning dan nooit de resterende velden zou kunnen dekken. Indien de koning dus wel rechtsonder staat, moeten de resterende velden gedomineerd worden met 2 paarden en een loper. Na wat proberen merken we al snel dat het opnieuw onmogelijk is om de resterende velden te domineren. Dame Koning De dame kan dus niet op positie 4 staan. Positie 5 De werkwijze bij positie 5 is opnieuw analoog aan de vorige posities. De zes velden bovenaan rechts die niet door de dame worden gedekt, kunnen enkel worden gedekt met een loper en een paard, of met een koning. Als we de velden opvullen met de loper en een paard, krijgen we nevenstaande opstelling. Opnieuw merken we dat de resterende stukken (paard en koning) de overblijvende velden niet kunnen dekken. Indien we de koning bovenaan rechts plaatsen merken we dat ook nu de overblijvende stukken de resterende velden onmogelijk kunnen domineren. Het is dus onmogelijk om het gehele 8x8 schaakbord te domineren met de huidige combinatie van beginstukken als de dame op positie 5 staat. Dame Paard Loper 16 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Positie 6 Als het mogelijk is om het schaakbord te domineren met 7 beginstukken dan moet de dame wel op positie 6 staan. De dame verdeelt het bord dan in een 5x5 schaakbord met een diagonaal. Er zijn dus geen geïsoleerde velden, de diagonaal zorgt er wel voor dat er twee gelijke helften ontstaan. De koning moet dus binnen een van deze velden liggen of op de diagonaal van de dame. Indien we deze posities afgaan, merken we al snel dat het onmogelijk is om met de resterende stukken (2 paarden en een loper) de ongedekte velden te domineren. Besluit We kunnen besluiten dat het onmogelijk is om met de combinatie van 2 paarden, een loper, de dame en de koning het 6x6 schaakbord te domineren. Bijgevolg kunnen we het 8x8 schaakbord niet domineren met 2 torens, 2 paarden, een loper, de dame en de koning aangezien we veronderstellen dat de torens in de hoeken moeten staan. Voor de twee overblijvende combinaties is het bewijs analoog. Het is bij deze combinaties dus ook niet mogelijk om het 8x8 schaakbord te domineren. Hieruit volgt dat het onmogelijk is om met een combinatie van 7 beginstukken het 8x8 bord te domineren. Het bewijs is echter niet sluitend, we hebben namelijk verondersteld dat de torens sowieso behoren tot de combinatie van 7 beginstukken en dat ze in de hoeken van het bord staan. We kunnen dus niet uitsluiten dat er toch een dominante opstelling is. Deze opstelling heeft dan ofwel maar 1 toren, ofwel staan de torens niet in de hoeken van het bord. 17 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Eindwoord Liefste dagboek, Voila, het werk zit er op. Lang heb ik mij bezig gehouden met de geheimen van dominantie, zo lang dat dominantie nu zelfs geen geheimen meer heeft. Door de grondige voorbereidingen die ik heb getroffen, verliep het echte onderzoek zeer vlot. Zo vlot dat ik zelfs een opstelling heb gevonden met de 8 schaakstukken waarbij het volledige schaakbord gedomineerd wordt. Helaas was een sluitend bewijs vinden dat het niet lukt met slechts zeven stukken heel wat moeilijker. Het probleem is dat alles van elkaar afhangt, en het bijna onmogelijk is om alle stukken samen in een wiskundig model te gieten. Door het begrip efficiëntie heb ik veel werk kunnen besparen, maar nog altijd was het meer proberen dan bewijzen. Alhoewel, wiskundig bewijzen draait erom dat mensen overtuigd moeten worden, zei ooit een wijze man. Daarin ben ik denk ik wel geslaagd. 18 Jonas Vantrappen Stijn Wierinckx 6WeWIi 2014 Bronnen WATKINS, J., Wiskunde op een schaakbord, eerste druk, Veen Magazines B.V., 2007, p. 107-133. 19
© Copyright 2024 ExpyDoc
