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 Gardner1 (1914-2010). Zijn naam is zowat synoniem geworden met de legendarische Mathematical Games columns in het tijdschrift Scientific American2. De eerste uit de reeks verscheen in 1957, en hoewel het al meer dan 30 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.
In deze opgave belichten we een wistjedatje dat opdook in één van de Mathematical Games columns die Martin Gardner samen schreef met de wiskundige Ross Honsberger3. 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
Het bovenstaande trucje werkt voor alle objecten die kunnen gesorteerd worden. In deze opgave houden we het voor de eenvoud bij gehele getallen. Hieronder geven we daarvan 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. Deze klasse moet minstens de volgende methoden implementeren:
-
Een initialisatiemethode waaraan één enkel argument moet doorgegeven worden. Indien een string als argument wordt doorgegeven, dan moet die de locatie van een tekstbestand bevatten waaruit het rooster moet ingelezen worden. Elke regel van het tekstbestand moet de getallen van één rij uit het rooster bevatten, van elkaar gescheiden door één of meer spaties of tabs. Anderzijds kan als argument ook een lijst of een tuple van de rijen van het rooster doorgegeven worden, waarbij elke rij wordt voorgesteld als een lijst of een tuple van de getallen op die rij. In beide gevallen moet aan de methode een rooster van gehele getallen doorgegeven worden met minstens één rij en één kolom, waarbij geldt dat elke rij evenveel getallen bevat. Indien dit niet het geval is, dan moet de methode een AssertionError opwerpen met de boodschap ongeldig rooster.
-
Een methode grootste die het grootste getal uit het rooster teruggeeft.
-
Een methode kleinste die het kleinste getal uit het rooster teruggeeft.
-
Een methode __str__ die een stringvoorstelling van het rooster teruggeeft. In deze stringvoorstelling 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.
-
Een methode gesorteerd met twee optionele parameters dalend en kolommen waaraan een Booleaanse waarde kan doorgegeven worden (standaardwaarde: False). De methode moet een Booleaanse waarde teruggeven die aangeeft of de rijen (kolommen = False) of kolommen (kolommen = True) al dan niet 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 kan doorgegeven worden (standaardwaarde: False). De methode moet ervoor zorgen dat de getallen op elke rij (kolommen = False) of kolom (kolommen = True) van het rooster van klein naar groot (dalend = False) of van groot naar klein (dalend = True) gerangschikt worden. De methode moet een verwijzing teruggeven naar het object waarop de methode werd aangeroepen.
Zorg ervoor dat de operator + (plusteken) kan gebruikt worden om twee roosters (objecten van de klasse Rooster) samen te voegen tot een rooster dat gevormd wordt door de kolommen van het tweede rooster achter die van het eerste rooster te plaatsen. Het resultaat moet een nieuw object van de klasse Rooster zijn. Indien de twee roosters die samengevoegd worden niet hetzelfde aantal rijen hebben, dan moet een AssertionError opgeworpen worden met de boodschap aantal rijen is verschillend.
Zorg er ook voor dat de operator - (minteken) kan gebruikt worden om twee roosters (objecten van de klasse Rooster) samen te voegen tot een rooster dat gevormd wordt door de rijen van het tweede rooster onder die van het eerste rooster te plaatsen. Het resultaat moet een nieuw object van de klasse Rooster zijn. Indien de twee roosters die samengevoegd worden niet hetzelfde aantal kolommen hebben, dan moet een AssertionError opgeworpen worden met de boodschap aantal kolommen is verschillend.
Voorbeeld
Bij de onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand rooster.txt4 zich in de huidige directory bevindt.
>>> 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.gesorteerd()
False
>>> rooster.gesorteerd(kolommen=True)
False
>>> print(rooster.sorteer())
2 3 13 16
5 8 10 11
6 7 9 12
1 4 14 15
>>> rooster.gesorteerd()
True
>>> rooster.gesorteerd(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.gesorteerd()
True
>>> rooster.gesorteerd(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.gesorteerd()
False
>>> rooster.gesorteerd(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.gesorteerd(kolommen=True)
False
>>> rooster.gesorteerd(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