Oplossingen van prijsvraag "Wie is de slimste bezoeker?"
Eind september verscheen op deze site de rubriek "Wie is de slimste bezoeker van onze site?", met daarop een drietal prijspuzzels. Als regelmatige bezoeker en liefhebber van programmeren heb ik mij op de opgaven gestort, al was het kunnen programmeren naar mijn mening niet noodzakelijk om voor elk een oplossing te vinden.
Als uitgekozen winnaar (waarvoor dank!) is mij gevraagd om de oplossingen van de puzzels te presenteren, alsmede enkele toelichtingen.
Senioren
Puzzel 1: De sprong van het paard
1. Plaats het paard op c4 en nummer dit veld met een 1. Maak een sprong met het paard en nummer het veld met een 2. Ga zo door tot het laatst overgebleven veld en geef dit het nummer 64.
2. Het paard mag een veld slechts eenmaal aandoen.
3. Sommeer de getallen op iedere rij en op iedere lijn.
4. De uitkomst van de som van iedere rij en van iedere lijn moet exact hetzelfde zijn, jullie kunnen vast wel uitrekenen hoe groot deze som dan moet zijn.
In een zeker opzicht was dit misschien de makkelijkste. Het eerste dat men moet weten is dat een vierkant van n bij n vakjes met daarin de getallen 1 t/m n*n, zodanig dat alle rijen en kolommen dezelfde som hebben, een magisch vierkant wordt genoemd (in het Engels: magic square). Daarbij moet wel aangetekend worden dat bij een magisch vierkant ook de diagonalen dezelfde som moeten hebben. Weet men verder dat een route waarbij het paard elk veld één keer aandoet in het Engels een knight’s tour heet, dan beschikt men over de zoektermen waarmee een antwoord snel gevonden kan worden op internet.
Het blijkt dat er al half-magische paardentoeren zijn gevonden in het tijdperk voor de computers. In 2003 is met de computer vastgesteld dat er geen paardentoeren zijn die volledig magisch zijn, d.w.z. waarbij de diagonalen ook tot dezelfde som (260) optellen. Er zijn wel 2240 half-magische paardentoeren, of 140 onequivalente oplossingen (zie deze site). Als men een oplossing heeft, is het immers mogelijk om het bord/vierkant een kwartslag of een halve slag te draaien. Ook spiegeling heeft geen effect op de magie. Verder is het ook mogelijk om de paardentoer om te draaien: alle getallen veranderen dan van x in 65-x, waarna alle rijen en kolommen nog steeds tot 260 optellen. Zodoende bestaan er van elke oplossing 16 equivalente varianten, en 16*140 = 2240.
Zelf heb ik me toch eerst op eigen houtje in de puzzel verdiept. Om te beginnen meende ik mij te herinneren dat er een keer in Schaak Magazine een kort stukje heeft gestaan over dit soort vierkanten. Ik heb ernaar gezocht maar kon het niet vinden. Ook ontdekte ik dat er een nummer ontbreekt in mijn archief. Zul je net zien…
Ik heb wat opgezocht over methodes om paardentoeren te vinden en magische vierkanten te maken, maar ik vond niks dat aan elkaar gekoppeld kon worden. Een snel in elkaar geflanst programma dat willekeurige paardentoeren maakte in de hoop dat er een halfmagisch zou zijn, was ook gedoemd te mislukken. Alle mogelijkheden systematisch afgaan leek op het eerste gezicht veel te lang te duren, omdat er voor bijna elke sprong meerdere opties zijn, zodat het aantal varianten exponentieel groeit. Toen ik echter vond dat het al eens was gedaan, besloot ik er toch voor te gaan.
Het belangrijkste voor een efficiënt algoritme is om zo snel mogelijk door te hebben wanneer een incomplete paardentoer geen kans meer maakt om een volledige toer te worden, of om een halfmagisch vierkant op te leveren. De betreffende tak in de zoektocht kan dan afgebroken worden. Komt het paard bijvoorbeeld op c2, dan moet het paard vervolgens wel naar a1, anders kan het er nooit meer naartoe en vandaan (tenzij a1 het eindveld is). Evenzo, als het paard bijvoorbeeld toe is aan sprong 40, terwijl er een rij is waarin de nog lege velden met gemiddeld minder dan 40 gevuld moeten worden om tot 260 te komen, dan is verder zoeken ook niet nodig.
Uiteindelijk kwam ik tot een programma dat alle mogelijkheden afgaat gegeven een begin- en eindveld. Het kostte mijn computer iets meer dan een week om alles met c4 als beginveld af te gaan. Daarbij zijn vijf biljoen virtuele paardensprongen uitgevoerd. De teller stopte op 28 oplossingen, waarvan twee paar symmetrisch equivalent zijn ten opzichte van elkaar.
Daarna ben ik maar gelijk doorgegaan met alle andere mogelijke begin- en eindvelden (wegens symmetrieën was het niet nodig om écht alles af te gaan); dat duurde nog eens drie weken op twee processoren. Mijn conclusie is dezelfde als die van 2003: er zijn 140 oplossingen waarvan geen enkele volledig magisch is.
Toch zijn er wel oplossingen, 41 in totaal, waarbij de twee diagonalen samen tot 520 optellen. Ook met c4 als beginveld zijn er dergelijke oplossingen:
|
47 |
34 |
63 |
20 |
49 |
22 |
11 |
14
|
|
62 |
19 |
48 |
35 |
10 |
13 |
50 |
23
|
|
33 |
46 |
17 |
64 |
21 |
52 |
15 |
12
|
|
18 |
61 |
36 |
45 |
16 |
9 |
24 |
51
|
|
59 |
32 |
1 |
8 |
37 |
44 |
53 |
26
|
|
4 |
7 |
60 |
29 |
56 |
25 |
38 |
41
|
|
31 |
58 |
5 |
2 |
43 |
40 |
27 |
54
|
|
6 |
3 |
30 |
57 |
28 |
55 |
42 |
39
|
De diagonaal a1-h8 telt op tot 264 en a8-h1 tot 256. Wat bijzonder is aan deze oplossing is dat de diagonalen een zekere structuur hebben:
a1+c3 = b2+d4 = e5+g7 = f6+h8 = 66
a8+c6 = b7+d5 = e4+g2 = f3+h1 = 64
Dit is bovendien een oplossing waarbij het paard vanaf het eindveld (d6) terug kan naar het beginveld. Dit is een zogenaamde closed tour (gesloten toer). Van de in de totaal 140 oplossingen zijn er 63 met deze eigenschap.
Bovenstaande oplossing heeft nóg een ander kenmerk dat door maar liefst 45 oplossingen gedeeld wordt: als men kijkt naar de velden 1 t/m 4, 5 t/m 8, 9 t/m 12, enzovoort, dan ziet men dat elke vier telkens in hetzelfde "kwadrant" zitten (met de kwadranten bedoel ik de vier segmenten die je krijgt door het bord in de lengte en de breedte in tweeën te delen). Bovendien vormen elke vier velden een kleine "cykel": het paard kan van veld 4 naar 1, van 8 naar 5, van 12 naar 9, enzovoort.
Er is nog een andere mooie eigenschap die 15 (onequivalente) oplossingen laten zien (maar geeneen met c4 als beginveld). Hier is een voorbeeld:
|
7 |
42 |
55 |
26 |
39 |
10 |
23 |
58
|
|
54 |
27 |
8 |
41 |
24 |
57 |
38 |
11
|
|
43 |
6 |
25 |
56 |
9 |
40 |
59 |
22
|
|
28 |
53 |
44 |
5 |
60 |
21 |
12 |
37
|
|
45 |
4 |
49 |
32 |
13 |
36 |
17 |
64
|
|
52 |
29 |
46 |
3 |
20 |
61 |
14 |
35
|
|
1 |
48 |
31 |
50 |
33 |
16 |
63 |
18
|
|
30 |
51 |
2 |
47 |
62 |
19 |
34 |
15
|
Hier is te zien dat elk paar horizontaal aan elkaar grenzende velden (alternerend) optelt tot 49 of 81. Men zie:
a1+b1 = a3+b3 = a5+b5 = a7+b7 = c2+d2 = c4+d4 = … = g6+h6 = g8+h8 = 81
a2+b2 = a4+b4 = a6+b6 = a8+b8 = c1+d1 = c3+d3 = … = g5+h5 = g7+h7 = 49
Ik heb alle oplossingen bijeengebracht op onderstaande site, daar kunt u alles bekijken en filteren naar wens.
Puzzel 2: Niet aanvallûûh!
Teken een schaakbord van 5 bij 5 velden.
Plaats alle schaakstukken (behalve de pionnen) op dit schaakbord.
Nu moeten de schaakstukken zo worden geplaatst dat geen van de zwarte stukken een wit stuk aanvalt en geen van de witte stukken een zwart stuk aanvalt.
Deze puzzel was in zekere zin ook makkelijk omdat er zo veel oplossingen zijn. Ook zelf vond ik na enig proberen een oplossing, voordat ik het toch een leuke uitdaging vond om een computer alles zo efficiënt mogelijk af te laten gaan. De teller bleef hier staan op 3171. Ook hier geldt dat er symmetrieën zijn: elke oplossing kan gedraaid en gespiegeld worden, en tevens kunnen de witte en de zwarte stukken van plaats wisselen, zonder dat dit de correctheid van de oplossing beïnvloed. Dit geeft weer 16 varianten. Er zijn echter oplossingen die van zichzelf symmetrisch zijn, zodat deze minder equivalente varianten hebben. Het totaal met alle varianten inbegrepen is 50428 (al durf ik niet uit te sluiten dat er misschien een foutje in mijn programma zit).
Ik licht een paar oplossingen eruit:
Dit is de enige oplossing met een dubbele symmetrie: de stelling is symmetrisch ten opzichte van spiegeling langs de verticale as, maar ook de opstellingen van de witte en zwarte stukken zijn symmetrisch ten opzichte van elkaar.
Deze oplossing is symmetrisch ten opzichte van de diagonaal a1-e5. Op de lopers na staan tevens de witte en zwarte stukken hetzelfde.
Voor de meeste schakers zal de voorkeur toch uitgaan naar een oplossing waarbij de lopers van beide kleuren op velden van verschillende kleur staan. Hiervan zijn er 269, waarvan 23 met een symmetrische opstelling. Hier is er een van:
Bij deze oplossing staan ook de paarden op verschillende kleuren velden. Tevens staan toren, loper en paard telkens op dezelfde manier gegroepeerd. Wat bovendien bijzonder is is dat geen van beide partijen in de gegeven stelling schaak kan geven; dat is vrij uniek (al weet ik niet hoe uniek).
Ook hiervan heb ik alle oplossingen ondergebracht op een site:
Puzzel 3: Vier dames en een paard
Pak een gewoon schaakbord, vier dames en een paard. Zet deze stukken zodanig op het schaakbord dat alle velden door deze stukken worden bestreken of door deze stukken worden bezet.
Dit zal voor de puzzelaar lastig zijn geweest. Hoe overziet men immers snel of alle velden bestreken worden? Bovendien was er maar één oplossing.
Voor een programmeur was deze puzzel echter de makkelijkste; er zijn immers "slechts" 38 miljoen manieren waarop vier dames en een paard op het bord geplaatst kunnen worden, dus alles afgaan is een fluitje van een cent.
De oplossing is:
Uiteraard kan deze oplossing ook weer gedraaid en gespiegeld worden.
Ik was trouwens al eens een soortgelijke opgave tegengekomen; toen betrof het echter vier dames en een loper. Ik heb dit ook nog even door de computer gehaald, maar deze variant blijkt maar liefst 49 (onequivalente) oplossingen te hebben. Bij geen daarvan staan overigens alle stukken gedekt. Hier is een interessante oplossing:
Junioren
Puzzel 1: Rechthoeken en vierkanten
Hoeveel verschillende rechthoeken en vierkanten bevat een schaakbord? Er zijn bijvoorbeeld 64 vierkantjes van 1×1, maar slechts één van 8×8. De kleinste rechthoeken die niet vierkant zijn, hebben zijden van 1×2 respectievelijk 2×1. De grootste rechthoeken die niet vierkant zijn hebben zijden van 7×8 respectievelijk 8×7.
Dit was een kwestie van het bedenken van een goede methode om alle mogelijkheden te tellen. Voor de rechthoeken is het bijvoorbeeld mogelijk om het aantal mogelijkheden voor de lijnen en de rijen apart van elkaar te tellen, en dan te vermenigvuldigen.
Een rechthoek van 1 veld breed kan op 8 verschillende lijnen geplaatst worden. Een rechthoek van 2 velden breed kan op 7 manieren geplaatst worden (a-b, b-c, …, g-h). Voor een rechthoek van 3 velden breed zijn er 6 opties, enzovoort, tot er uiteindelijk maar één optie is voor een rechthoek van 8 velden breed. Het totale aantal opties voor wat betreft de lijnen komt daarmee op 8+7+…+1 = 36.
Voor de rijen geldt natuurlijk precies hetzelfde. Het totale aantal mogelijke rechthoeken is dan 36*36 = 1296.
Voor de vierkanten is een soortgelijke redenatie mogelijk. Er zijn 8*8 vierkanten van 1 bij 1. Een 2 bij 2 vierkant kan op 7*7 manieren geplaatst worden: er zijn 7 opties voor de lijnen en 7 voor de rijen. Dit gaat zo door. Er zijn 2*2 vierkanten van 7 bij 7 en tot slot één van 8 bij 8. Het totaal is dus 8*8 + 7*7 + … + 1*1 = 204.
Puzzel 2: Paarden
Hoeveel paarden zijn er minstens nodig om elk veld van het schaakbord te bezetten of te beheersen?
Er is een oplossing met 12 paarden:
Het is echter lastig om te bewijzen dat het niet met 11 paarden of nog minder kan. Het ligt nog wel intuïtief voor de hand om te stellen dat er sowieso een paard op b3 of c2 moet staan, omdat a1 gedekt moet worden. Dat kan natuurlijk ook met een paard op a1, maar die dekt vanaf daar slechts twee velden. Evenzo komen er nog drie paarden op b6/c7, f2/g3 en f7/g6. Maar ja, hoe moeten die ten opzichte van elkaar staan, en zijn nog eens 7 paarden echt niet toereikend? Ik zou niet weten hoe je daar een sluitend bewijs van zou kunnen geven.
Ik kan wel programmeren, en op basis daarvan verzekeren dat 12 het minimum is. Bovendien is bovenstaande configuratie de enige oplossing (afgezien van de gespiegelde versie, uiteraard).
Voor het geval dat de velden waarop de paarden staan niet meetellen, is het minimum trouwens 14.
Puzzel 3: Mat in drie
De oplossing is eenvoudigweg:
1.d4
a) 1…Kg4 2.e4+ Kh4 3.g3#
b) 1…Kh5 2.Dd3 Kg4 (Kh4) 3.Dh3#
Tot zover de oplossingen en mijn bevindingen. Ik hoop dat deze prijsvraag in 2013 een vervolg krijgt!
Jeugd puzzel 2, "paarden". Van programmeren heb ik niet veel verstand, van bewijzen een beetje.
(1) Er zijn minstens 3 paarden nodig om a1-b1-a2-b2 te bezetten of bestrijken. Stel dat het met 2 paarden kan. Dan staan ze niet beiden op een van die 4 velden; er kan er ook niet 1 op staan, omdat je dan met 1 paard velden van verschillende kleur moet bestrijken. Dus moeten die vier velden door 2 paarden worden bestreken. Dat kan niet, omdat er twee paarden nodig zijn om a1 en b2 te bestrijken (en die kunnen niet a2/b1 bestrijken, dat zijn velden van de ander kleur).
(2) Een paard dat een van de velden a1-b1-a2-b2 bezet of bestrijkt staat in het kwadrant a1-d1-d4-a4.
(3) Uit (1) en (2) volgt dat het in kwadrant a1-d1-d4-a4 minstens drie paarden staan.
(4) Natuurlijk geldt (3) voor alle kwadranten, dus er zijn minstens twaalf paarden nodig.
QED.
Heel mooi!!