Antwoord op: Veertien Vijftien
Het is onmogelijk om deze puzzel op te lossen. Alle mogelijke configuraties van de 15 blokjes en de lege plaats kunnen verdeeld worden in twee groepen. Elke configuratie in één van deze groepen is via verschuivingen bereikbaar vanuit elke andere configuratie in dezelfde groep, maar niet vanuit de andere groep. De gewenste eindconfiguratie (alle blokjes in de juiste volgorde met de lege plaats weer rechtsonder) en de gegeven beginconfiguratie zitten niet in dezelfde groep. Het is echter wél mogelijk om alle blokjes in de juiste volgorde te plaatsen met de lege plaats linksboven (zie de tweede vraag bij de puzzel)!
Een bewijs hiervoor kan worden geleverd op basis van de zogenaamde pariteit van elke configuratie: een configuratie is even of oneven. Deze pariteit blijft behouden bij alle toegestane zetten.
We leggen eerst uit hoe de pariteit van een configuratie wordt bepaald. Daarna zullen we bewijzen dat de pariteit bij alle toegestane zetten behouden blijft.
De pariteit van een configuratie wordt bepaald door de som van N1 en N2. Hierbij is N2 het nummer van de rij waarin de lege plaats zich bevindt (genummerd van 1 tot 4). N1 is het aantal getallenparen waarvan de getallen in de verkeerde volgorde staan. N1 wordt als volgt bepaald:
- Zet alle getallen van de blokjes in een rij (van links naar rechts en van boven naar beneden).
- Bekijk alle 105 mogelijke getallenparen in deze rij (alle mogelijke combinaties van twee getallen).
- N1 is het aantal getallenparen waarvan de getallen in de verkeerde volgorde staan.
Een voorbeeld. Stel dat de huidige configuratie van de blokjes als volgt is:
| 1 | 2 | 3 | 4 |
| 5 | 6 | 9 | 7 |
| 11 | 8 | 12 | 10 |
| 13 | 14 | 15 |
Nu zetten we de getallen in een rij: 1, 2, 3, 4, 5, 6, 9, 7, 11, 8, 12, 10, 13, 14, 15.
Om te bepalen voor welke getallenparen de getallen in de verkeerde volgorde staan, kijken we voor elk getal in de rij welke getallen rechts van dat getal kleiner zijn. Zo vinden we dat voor 5 van de 105 getallenparen de getallen in de verkeerde volgorde staan: (9, 7), (9, 8), (11, 8), (11, 10) en (12, 10). Dus N1 = 5.
De lege plaats in dit voorbeeld bevindt zich in rij 4, dus N2 = 4.
De pariteit van de configuratie in dit voorbeeld is daarom oneven, omdat N1 + N2 = 5 + 4 = 9.
Nu zullen we bewijzen dat de pariteit niet verandert bij het maken van een toegestane zet. Er zijn twee soorten zetten mogelijk: een blokje kan worden verschoven in horizontale of verticale richting.
Bij een horizontale verschuiving (zie het voorbeeld in de afbeelding hieronder) blijven zowel N1 als N2 gelijk. De volgorde van de blokjes verandert immers niet, en ook de lege plaats blijft in dezelfde rij. Een horizontale zet heeft dus geen invloed op de pariteit.
| X | → | ||
Bij een verticale verschuiving (zie het voorbeeld in de afbeelding hieronder) komt de lege plaats één rij hoger of lager terecht. N2 neemt daardoor met 1 toe of af. N1 zal met 1 of 3 toenemen of afnemen. Wanneer de getallen in een rij staan, zitten er namelijk altijd precies drie getallen ingesloten tussen de oude en de nieuwe positie van het verschoven blokje. Er kunnen alleen wijzigingen optreden in de getallenparen waarin zowel het verschoven blokje (X) als één van de ingesloten getallen (a, b en c) voorkomt. Alle andere getallenparen blijven ongewijzigd. In het voorbeeld hieronder, waarin blokje X een rij omlaag wordt geschoven, neemt de waarde van N2 toe met 1. De waarde van N1 neemt voor elk van de drie getallenparen (X, a), (X, b) en (X, c) toe of af met 1 (zie de tabel hieronder).
| X | a | ||
| b | c | ↓ | |
| Situatie vóór verschuiving | Bijdrage aan N1 vóór verschuiving | Bijdrage aan N1 na verschuiving | Verandering van N1 | ||
|---|---|---|---|---|---|
| X > a | X > b | X > c | |||
| nee | nee | nee | 0 | 3 | +3 |
| ja | nee | nee | 1 | 2 | +1 |
| nee | ja | nee | 1 | 2 | +1 |
| ja | ja | nee | 2 | 1 | -1 |
| nee | nee | ja | 1 | 2 | +1 |
| ja | nee | ja | 2 | 1 | -1 |
| nee | ja | ja | 2 | 1 | -1 |
| ja | ja | ja | 3 | 0 | -3 |
Omdat zowel N1 als N2 met een oneven waarde verandert, wijzigt de waarde van N1 + N2 met een even waarde. Hierdoor blijft de pariteit van N1 + N2 ook bij een verticale verschuiving gelijk.
De pariteit van de gegeven beginconfiguratie (met de getallen 14 en 15 verwisseld en de lege plaats rechtsonder) is oneven (omdat N1 + N2 = 4 + 1 = 5). De pariteit van de gevraagde eindconfiguratie (alle getallen in de juiste volgorde en de lege plaats rechtsonder) is even (omdat N1 + N2 = 4 + 0 = 4). Het is daarom onmogelijk om door het verschuiven van de blokjes van de gegeven beginconfiguratie tot de gevraagde eindconfiguratie te komen.
De pariteit van de configuratie waarin alle getallen in de juiste volgorde staat en de lege plaats zich linksboven bevindt, is echter wel oneven (omdat N1 + N2 = 1 + 0 = 1). Deze configuratie is dus wel vanuit de gegeven beginconfiguratie te bereiken.
Terug naar de puzzel