Kies een positief geheel getal, zeg $n$. We gaan de getallen $k \in {1, 2, 3, \dots n}$ tweemaal in een rij plaatsen zó dat de afstand tussen de twee $k$'s precies $k$ is. Een dergelijke rij noemen we een Skolemrij. Zo is $[1, 1]$ een voorbeeld van een Skolemrij. Maar ook $[1, 1, 3, 4, 2, 3, 2, 4]$ is een Skolemrij. De enen staan immers op afstand $1$ van elkaar, de tweeën op afstand $2$, de drieën op afstand $3$ en de vieren op afstand $4$.

Opgave 1 Maak ook een Skolemrij van lengte $10$ voor de getallen $1$ t/m $5$.

We schrijven een programma om met brute force het aantal Skolemrijen te bepalen voor een gegeven $n$. We maken gebruik van itertools. Itertools is een heel praktisch stukje gereedschap. Wij gebruiken permutations, daarmee kun je een verzameling elementen in alle mogelijke volgordes (permutaties) plaatsen. Bijvoorbeeld voor ${1,2,3}$ geeft permutations de uitkomst ${[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]}$. We gaan nu aan de slag met het programma.

Maar we kijken nog eerst even naar de oplossing bij $n = 4$. Dat was: $[1, 1, 3, 4, 2, 3, 2, 4]$. Je doorloopt deze rij van voor naar achter. Je komt eerst een één tegen, daarna de drie, daarna de vier en ten slotte de twee. Dat je onderweg ook nog een één tegenkomt, is nu even niet relevant. Want we willen weten wat de volgorde is van de verschillende getallen. En die is $[1, 3, 4, 2]$. We laten nu zien hoe je met de permutatie $[1, 3, 4, 2]$ weer de bovengenoemde oplossing kunt vinden. Plaats eerst een lege oplossingsrij: $[0, 0, 0, 0, 0, 0, 0, 0]$.

We gaan eerst de twee enen plaatsen. De eerste één komt vooraan, de tweede één komt 1 verderop, dus: $[1, 1, 0, 0, 0, 0, 0, 0]$.

Nu plaatsen we de twee drieën: De eerste drie komt op de eerste vrije plek en de volgende drie komt 3 verderop, dus: $[1, 1, 3, 0, 0, 3, 0, 0]$.

Daarna plaatsen we de vier. We zoeken naar de eerste vrije plek (dus 0). Hier plaatsen we de vier en 4 verderop volgt de andere vier. $[1, 1, 3, 4, 0, 3, 0, 4]$.

Ten slotte plaatsen we de tweeën. $[1, 1, 3, 4, 2, 3, 2, 4]$.

Niet elke permutatie levert op deze maniereen oplossing. Bijvoorbeeld bij de permutatie $[1, 2, 3, 4]$ gaat het mis.

Het idee achter de brute force aanpak (dat wil zeggen we gaan alle mogelijkheden langslopen) is dat we alle permutaties van ${1, 2, 3, \dots, n}$ langslopen. Als we een zekere permutatie bekijken, dan gaan we in een lege rij van lengte $2n$ de getallen invullen, zoals we dat hierboven hebben beschreven.

Bekijk het programma via de knop [Bekijk oplossing] onderaan deze pagina.

Opgave 2 Ga na dat bij de permutatie $[1, 2, 3, 4]$ geen oplossing is. Opgave 3 We hebben $n = 2$ en $n = 3$ overgeslagen. Het blijkt dat er geen oplossingen zijn voor $n = 2$ en $n = 3$. Pas het hierboven beschreven algoritme toe (werk met pen en papier) om na te gaan dat er geen oplossingen zijn.

Dan ben je natuurlijk benieuwd wat de resultaten zijn. Tot en met $9$ zijn de berekeningen goed uit te voeren op een computer met het programma. We vinden:

$1$ : 1
$2$ : 0
$3$ : 0
$4$ : 6
$5$ : 10
$6$ : 0
$7$ : 0
$8$ : 504
$9$ : 2656

Opmerkelijk zijn de nullen bij $2$, $3$, $6$ en $7$.

Opgave 4 Kun je nagaan waarom er geen oplossingen zijn voor $2$, $3$, $6$ en $7$? Zouden er ook voor andere rijen mogelijk geen oplossingen zijn?

In het volgende nummer plaatsen we de oplossing van deze laatste opgave. 

Meer weten?
Op internet kun je veel meer vinden over deze Skolemrijen. Je kunt een zoekopdracht uitvoeren in de OEIS (Online Encyclopedia of Integer Sequences). Tik in 1, 0, 0, 6, 10, 0, 0, 504 en je vindt A004075 Number of Skolem sequences of order n. Op die pagina vind je ook weer allerlei andere verwijzingen.

 

 

Bekijk oplossing