Net als goeie goocheltrucs kunnen vernuftige denkpuzzels nieuwe wiskundige inzichten blootleggen of interessante vragen poneren. Dat was althans een belangrijke drijfveer in het werk van Martin Gardner (1914-2010). Zijn naam is zowat synoniem geworden met de legendarische Mathematical Games columns in het tijdschrift Scientific American. De eerste uit de reeks verscheen in 1957, en hoewel het al meer dan 40 jaar geleden is dat de laatste verscheen, zijn ze een legende geworden in de uitgeverswereld. Maandelijks schreef Gardner met al zijn mathemagische vaardigheden en de vingervlugheid van een goochelaar een stuk over betoverende wiskunde, waarmee hij een immens lezerspubliek van over de hele wereld in de ban hield. De columns staan vandaag de dag dan ook nog steeds model voor het duidelijk en elegant aanbrengen van nieuwe en boeiende wiskundige ideeën, zonder te vervallen in techniciteiten.
Veel artikels van de immer productieve Martin Gardner vallen onder de noemer "recreatieve wiskunde", maar hij besprak ook ontzettend graag gloednieuwe concepten met bijdragen van 's werelds meest creatieve geesten. Zelfs columns die enkel voor de fun geschreven leken te zijn, bleken een inspiratie voor baanbrekend onderzoek dat geleid heeft tot ontwikkelingen met een grote wetenschappelijke, technologische of maatschappelijke impact. Dit succes is des te opmerkelijker omdat Gardner zelf geen wiskundige opleiding genoten heeft. In zijn memoires Undiluted Hocus-Pocus (Princeton, 2013) schreef hij hierover:
One of the pleasures in writing the column was that it introduced me to so many top mathematicians, which of course I was not. Their contributions to my column were far superior to anything I could write, and were a major reason for the column's growing popularity. The secret of its success was a direct result of my ignorance. Even today my knowledge of math extends only through calculus, and even calculus I only dimly comprehend. As a result, I had to struggle to understand what I wrote, and this helped me write in ways that others could understand.
We belichten een wistjedatje dat opdook in één van de Mathematical Games columns die Martin Gardner samen schreef met de wiskundige Ross Honsberger. Leg een aantal speelkaarten in een rechthoekig rooster.
Herschik de speelkaarten op elke rij van het rooster, zodat ze van klein naar groot gerangschikt zijn. Hierbij hou je enkel rekening met de numerieke waarde van de speelkaarten.
Doe nu hetzelfde met de kaarten in elke kolom van het rooster.
Verrassend genoeg verstoort deze laatste stap de eerste niet — op elke rij liggen de kaarten nog steeds van klein naar groot gerangschikt. Heb je enig idee hoe dat komt?
Opgave
Bovenstaand trucje werkt voor alle objecten die kunnen gesorteerd worden. Voor de eenvoud zullen we het bij gehele getallen houden. Een voorbeeld: \[ \begin{array}{rrrrrr} 2 & 12 & 2 & 4 & 6 & 12\\ 9 & 11 & 3 & 4 & 1 & 6\\ 13 & 2 & 5 & 9 & 1 & 1\\ 13 & 2 & 5 & 10 & 11 & 9 \end{array} \,\, \stackrel{\text{rijen sorteren}}{\longrightarrow} \,\, \begin{array}{rrrrrr} 2& 2& 4& 6& 12& 12\\ 1& 3& 4& 6& 9& 11 \\ 1& 1& 2& 5& 9& 13\\ 2& 5& 9& 10& 11& 13 \end{array} \,\, \stackrel{\text{kolommen sorteren}}{\longrightarrow} \,\, \begin{array}{rrrrrr} 1& 1& 2& 5& 9& 11 \\ 1& 2& 4& 6& 9& 12 \\ 2& 3& 4& 6& 11& 13 \\ 2& 5& 9& 10& 12& 13 \end{array} \]
Definieer een klasse Rooster waarmee rechthoekige roosters van gehele getallen kunnen voorgesteld worden. Bij het aanmaken van een nieuw rooster (Rooster) moet één argument doorgegeven worden. Als er een string (str) wordt doorgegeven, dan stelt die de locatie voor van een tekstbestand waarin het rooster beschreven wordt. Elke rij van het rooster wordt beschreven op een afzonderlijke regel. Elke regel bevat de getallen op de corresponderende rij, gescheiden door één of meer spaties of tabs. Als een reeks (list of tuple) wordt doorgegeven, dan bevat die de rijen van het rooster, waarbij elke rij wordt voorgesteld als een reeks (list of tuple) met de gehele getallen (int) op die rij. In beide gevallen moet het rooster minstens één rij en één kolom hebben, en moet elke rij evenveel getallen bevatten. Als dat niet het geval is, dan moet een AssertionError opgeworpen worden met de boodschap ongeldig rooster.
Elk rooster (Rooster) moet een getter (of objecteigenschap) kleinste hebben die het kleinste getal (int) in het rooster teruggeeft, en een getter (of objecteigenschap) grootste die het grootste getal (int) uit het rooster teruggeeft.
Als er een rooster $$r$$ (Rooster) wordt doorgegeven aan de ingebouwde functie str, dan moet die een stringvoorstelling (str) van rooster $$r$$ teruggeven. Daarin moet elk getal rechts uitgelijnd worden over $$p$$ posities, waarbij $$p$$ gelijk is aan het aantal karakters dat nodig is om het breedste getal uit het rooster uit te schrijven. De kolommen van het rooster moeten in de stringvoorstelling van elkaar gescheiden worden door één enkele spatie.
Voorts moet je op een rooster $$r$$ (Rooster) minstens deze methoden kunnen aanroepen:
-
Een methode isgesorteerd met twee optionele parameters dalend en kolommen waaraan een Booleaanse waarde (bool) kan doorgegeven worden (standaardwaarde: False). De methode moet een Booleaanse waarde (bool) teruggeven die aangeeft of alle rijen (kolommen = False) of alle kolommen (kolommen = True) van rooster $$r$$ van klein naar groot (dalend = False) of van groot naar klein (dalend = True) gerangschikt zijn.
-
Een methode sorteer met twee optionele parameters dalend en kolommen waaraan een Booleaanse waarde (bool) kan doorgegeven worden (standaardwaarde: False). De methode moet de getallen op elke rij (kolommen = False) of op elke kolom (kolommen = True) van rooster $$g$$ van klein naar groot (dalend = False) of van groot naar klein (dalend = True) rangschikken, en een verwijzing naar rooster $$r$$ teruggeven.
Als twee roosters $$r$$ en $$s$$ (Rooster) niet hetzelfde aantal rijen hebben, dan moet de som $$r + s$$ een AssertionError opwerpen met boodschap aantal rijen is verschillend. Anders moet de som $$r + s$$ resulteren in een nieuw rooster (Rooster) dat gevormd wordt door de kolommen van rooster $$s$$ achter die van rooster $$r$$ te plaatsen.
Als twee roosters $$r$$ en $$s$$ (Rooster) niet hetzelfde aantal kolommen hebben, dan moet het verschil $$r - s$$ een AssertionError opwerpen met boodschap aantal kolommen is verschillend. Anders moet het verschil $$r - s$$ resulteren in een nieuw rooster (Rooster) dat gevormd wordt door de rijen van rooster $$s$$ onder die van rooster $$r$$ te plaatsen.
Voorbeeld
In deze interactieve sessie gaan we ervan uit dat het tekstbestand rooster.txt in de huidige directory staat.
>>> rooster = Rooster('rooster.txt')
>>> rooster.grootste
16
>>> rooster.kleinste
1
>>> print(rooster)
16 3 2 13
5 10 11 8
9 6 7 12
4 15 14 1
>>> rooster.isgesorteerd()
False
>>> rooster.isgesorteerd(kolommen=True)
False
>>> print(rooster.sorteer())
2 3 13 16
5 8 10 11
6 7 9 12
1 4 14 15
>>> rooster.isgesorteerd()
True
>>> rooster.isgesorteerd(kolommen=True)
False
>>> print(rooster.sorteer(kolommen=True))
1 3 9 11
2 4 10 12
5 7 13 15
6 8 14 16
>>> rooster.isgesorteerd()
True
>>> rooster.isgesorteerd(kolommen=True)
True
>>> print(rooster.sorteer(dalend=True))
11 9 3 1
12 10 4 2
15 13 7 5
16 14 8 6
>>> rooster.isgesorteerd()
False
>>> rooster.isgesorteerd(dalend=True)
True
>>> print(rooster.sorteer(kolommen=True, dalend=True))
16 14 8 6
15 13 7 5
12 10 4 2
11 9 3 1
>>> rooster.isgesorteerd(kolommen=True)
False
>>> rooster.isgesorteerd(kolommen=True, dalend=True)
True
>>> rij = Rooster([[17, 18, 19, 20]])
>>> print(rooster - rij)
16 14 8 6
15 13 7 5
12 10 4 2
11 9 3 1
17 18 19 20
>>> kolom = Rooster([[-21], [-22], [-23], [-24]])
>>> print(kolom + rooster)
-21 16 14 8 6
-22 15 13 7 5
-23 12 10 4 2
-24 11 9 3 1
>>> print(rooster - rij)
16 14 8 6
15 13 7 5
12 10 4 2
11 9 3 1
17 18 19 20
>>> print(kolom + rooster)
-21 16 14 8 6
-22 15 13 7 5
-23 12 10 4 2
-24 11 9 3 1
>>> Rooster([[1], [2, 3], [4, 5, 6]])
Traceback (most recent call last):
AssertionError: ongeldig rooster
>>> Rooster([])
Traceback (most recent call last):
AssertionError: ongeldig rooster
>>> Rooster([[]])
Traceback (most recent call last):
AssertionError: ongeldig rooster
>>> rooster - kolom
Traceback (most recent call last):
AssertionError: aantal kolommen is verschillend
>>> rooster + rij
Traceback (most recent call last):
AssertionError: aantal rijen is verschillend