Werkwinkel Permutatiepuzzels Karsten Naert UGent — Vakgroep Wiskunde
6 november 2013
1 / 33
Over mij. . . I I
Assistent en doctoraatsstudent Taken: I I I
Onderzoek Onderwijs ‘Dienstverlening’
I
[email protected]
I
http: //cage.ugent.be/~kn/permutatiepuzzels_hds.pdf
2 / 33
Wiskunde is: I
Abstractie maken van de werkelijkheid
I
Redeneren met deze abstracte gegevens
(Zie ook: http://www.wiskunde.ugent.be/kiezen/wat.php) Toegepast op puzzels: I
abstraheren = achterwege laten van details
I
redeneren = meer te weten komen over de puzzel, met als ultiem doel hem op te lossen
Doelstelling: leerlingen laten kennis maken met een vorm van wiskunde waarin rekenen een andere rol speelt dan zij gewoon zijn. (Zie verderop: rekenen met cykels.)
3 / 33
De Gevangene van Benda I I I
Een episode van ‘Futurama’ Professor Farnsworth bouwt een machine die mensen toestaat hun geesten van lichaam te verwisselen. . . Maar de machine kan maar eenmaal gebruikt worden op elk paar mensen!
Vraag Een aantal mensen is van hartelust van lichaam veranderd maar wil graag terug naar het eigen lichaam. Hoe lossen we dit op?
4 / 33
Definitie van permutatiepuzzels Een puzzel, waarbij de toestand waarin hij zich bevindt, kan omschreven worden door een bepaalde permutatie (dit is het veranderen van de volgorde) van delen ervan. De puzzel wordt opgelost door een paar basiszetten in de juiste volgorde uit te voeren
5 / 33
Voorbeelden van permutatiepuzzels I
De 15-puzzel
I
De Rubik’s Cube
I
De Hongaarse Ringen
... en vele andere voorbeelden.
6 / 33
Voorbeelden van permutatiepuzzels I
De 15-puzzel
I
De Rubik’s Cube
I
De Hongaarse Ringen
... en vele andere voorbeelden.
6 / 33
Voorbeelden van permutatiepuzzels I
De 15-puzzel
I
De Rubik’s Cube
I
De Hongaarse Ringen
... en vele andere voorbeelden. 6 / 33
Voorbeelden van permutatiepuzzels I
De 15-puzzel
I
De Rubik’s Cube
I
De Hongaarse Ringen
... en vele andere voorbeelden. 6 / 33
Is geen permutatiepuzzel: De square-1 puzzel:
7 / 33
De 15-puzzel Doel van de puzzel: de 14 en 15 omwisselen:
8 / 33
De onthutsende waarheid: Stelling De 15-puzzel kan niet worden opgelost!
Bewijs I
Stap 1: doe alsof er een oplossing zou zijn
I
Stap 2 (a): beredeneer extra informatie over deze oplossing
I
Stap 2 (b): . . . beredeneer n´ og meer informatie
I
Stap 3: vind een strijdigheid.
I
Conclusie: er bestaat geen oplossing.
Details op volgende dia’s
9 / 33
Het bewijs stap 1 I
We doen alsof er een oplossing is.
I
n is het aantal zetten van deze oplossing.
I
We willen meer informatie over n.
Suggesties? Idee¨en?
10 / 33
Het bewijs stap 2(a) We voeren een schaakbordkleuring uit:
Wat is Wat is I Wat is I Wat is I ... I Wat is Conclusie? I I
de de de de
kleur kleur kleur kleur
van van van van
het het het het
lege lege lege lege
vakje vakje vakje vakje
bij bij bij bij
zet zet zet zet
0? 1? 2? 3?
de kleur van het lege vakje bij zet n? 11 / 33
Het bewijs stap 2(b) Notatie We gebruiken de notatie (0, i) om te zeggen: een zet die het lege vakje (met nummer 0) en het vakje i (met nummer i) van plaats verwisselt. Of nog: het vakje i verschuift en neemt de plaats van het lege vakje, waar het vakje i was, komt nu een leeg vakje We kunnen de oplossing nu noteren als volgt (0, a1 )(0, a2 )(0, a3 ) . . . (0, an )
12 / 33
Intermezzo! We abstraheren de situatie: de zet (0, a1 ) wordt nu een abstracte permutatie van twee elementen. We kunnen de ‘zet’ ook ‘uitvoeren’ of laten werken op andere objecten dan de 16 vakjes van de puzzel! Als we dezelfde zetten uitvoeren op andere objecten, moet de eindsituatie hetzelfde zijn!
13 / 33
Het bewijs, stap 2(b) — vervolg De volgende reeks zetten lost het probleem op: (0, a1 )(0, a2 )(0, a3 ) . . . (0, an ) Ook de ‘zet’ (14, 15) lost het probleem op! Dus we zullen onze n zetten uitvoeren op een ander object...! 1 0 ... 0 0 1 . . . 0 .. .. . . . . . . .. 0 0 ...
1
Op de kolommen van de 16 × 16-eenheidsmatrix. De ‘oplossing’ uitvoeren = de zet (14, 15) uitvoeren.
14 / 33
Het bewijs, stap 2(b) — vervolg Voorbeeld: we voeren de zet (0, 15) uit op de 16 × 16-eenheidsmatrix. De kolommen zijn genummerd met (1, 2, . . . , 15, 0). 0 ... 0 1 0 ... 0 0 .. . . .. . . . . .. .. . . . .. .. (0,15) . . . −→ 0 . . . 1 0 0 . . . 0 1 0 ... 0 1 0 0... 1 0
Vraag Wat gebeurt er met de determinant?
15 / 33
Het bewijs, stap 2(b) — vervolg Elke zet verandert het teken van de determinant. (0, a1 )(0, a2 )(0, a3 ) . . . (0, an ) = (14, 15) Rechterlid: na ´e´en zet is de determinant = −1. Linkerlid: I
De determinant na zet 0?
I
De determinant na zet 1? (Dus na (0, a1 ))?
I
De determinant na zet 2? (Dus na (0, a1 )(0, a2 ))?
I
...
I
De determinant na zet n?
Conclusie voor n?
16 / 33
Het bewijs stap 3 Stel dat een oplossing bestaat in n zetten: I
Dan is n even — redenering met schaakbordkleuring
I
Dan is n oneven — redenering met teken determinant
Conclusie?
17 / 33
Vervolgvraag voor de 15-puzzel Hoeveel legale configuraties (waarbij lege vakje rechtsonder staat) zijn ‘bereikbaar’ ? (Eenvoudig theoretisch maximum: 15!.)
Antwoord: 15! = 653 837 184 000 2
Bewijs: Niet zo eenvoudig! Een schets: I I
Bewijs dat oneven permutaties onmogelijk zijn Bewijs dat elke even permutatie bereikt kan worden: I I
bewijs dat enkele basispermutaties mogelijk zijn bewijs dat elke even permutatie met deze basispermutaties kan worden gemaakt 18 / 33
Vervolgvraag voor de 15-puzzel Hoeveel configuraties zijn er in het geheel bereikbaar? (Lege vakje niet noodzakelijk rechtsonder.)
19 / 33
Groepentheorie Citaat Groepentheorie laat iets werken op iets en vergelijkt het resultaat met wat gebeurt wanneer datzelfde werkt op iets anders, of iets anders werkt op hetzelfde Deel van de abstracte algebra. We beperken ons tot de permutatiegroepen!
20 / 33
Permutaties Definitie Is X = {1, 2, . . . , n} een verzameling van n verschillende objecten, dan is een permutatie een manier om deze in een andere volgorde te zetten. De permutatie is de afbeelding (zelfs bijectie) waarmee de nieuwe volgorde bereikt wordt en niet de nieuwe volgorde als dusdanig.
21 / 33
Cykelnotatie Voorbeelden I
Stel dat X = {A, B, C } drie objecten bevat, dan is de afbeelding A → B, B → A en C → C een permutatie. Notatie: (A, B)(C ) of zelfs (A, B). Lees als: A gaat naar B, B gaat naar A en C gaat naar zichzelf.
I
Stel dat X = {A, B, C } drie objecten bevat, dan is de afbeelding A → B, B → C en C → A een permutatie. Notatie: (A, B, C ). Lees als: A gaat naar B, B gaat naar C en C keert terug naar A.
I
De permutatie A → B, B → A, C → D en D → C van {A, B, C , D} wordt genoteerd met (A, B)(C , D).
22 / 33
Rekenen met de cykelnotatie I
Gegeven twee permutaties π en σ kunnen we πσ ‘uitrekenen’: doe eerst π en dan σ; dus ook bekend als σ ◦ π. We noemen πσ het product van de permutaties π en σ.
I
Bijvoorbeeld: (1, 2)(2, 3) = (1, 3, 2).
I
We hebben de notatie e voor de identieke permutatie (die niks doet) en π −1 voor de inverse permutatie van π. Merk op dat ππ −1 = π −1 π = e.
I
Wat is het effect van π −1 σπ ? [Antwoord: ‘op σ doen wat π zegt’ !]
23 / 33
De Hongaarse ringen
38 bolletjes = veel = te veel.
24 / 33
De Hongaarse ringen ’Eenvoudige’ variant met 10 bolletjes
Merk op: het wordt moeilijker door de bolletjes te nummeren (10 nummers versus 4 kleuren). Basiszetten: (1, 2, 3, 4, 5, 6)
(1, 10, 3, 9, 8, 7) 25 / 33
De Hongaarse ringen Betekenis basiszet (1, 10, 3, 9, 8, 7): 1 → 10 → 3 → 9 → 8 → 7 → 1 We vergeten de puzzel! I
We beschouwen de basiszetten als permutaties.
I
We proberen zoveel mogelijk permutaties te maken met de basispermutaties door te rekenen met cykels.
I
Tot we over voldoende nieuwe permutaties beschikken om tot een oplossing te komen.
26 / 33
De Hongaarse ringen Als x = (1, 2, 3, 4, 5, 6)
y = (1, 10, 3, 9, 8, 7)
Dan is (2, 10) = yx −1 y −1 x 2 yx −1 y −1 x −1 y 2 xy −3 xyx −1 yxyx −1 y −1 Dus we kunnen 2 en 10 verwisselen. (En de rest vasthouden!) Dit is helemaal niet evident om te vinden! (Maar het is voor een computer zeer eenvoudig.)
27 / 33
De Hongaarse ringen Nu redeneren om de puzzel verder op te lossen: I
We kunnen 2 en 10 verwisselen, en de andere elementen vasthouden.
I
Dus we kunnen elke twee elementen verwisselen, en de andere vasthouden.
I
Dus we kunnen elke mogelijke permutatie bereiken.
Dus aantal mogelijke posities = 10! = 3 628 800!
28 / 33
Het valt niet mee om deze permutatie te vinden... snapbaar alternatief? (1, 2, 3) = xy 2 xy 2 xy 2 x Aantonen dat we met a = (1, 2, 3) en b = (1, 2, 3, 4, 5, 6) ook (1, 2) kunnen maken? Idee¨en? Suggesties?
29 / 33
Het valt niet mee om deze permutatie te vinden... snapbaar alternatief? (1, 2, 3) = xy 2 xy 2 xy 2 x Aantonen dat we met a = (1, 2, 3) en b = (1, 2, 3, 4, 5, 6) ook (1, 2) kunnen maken? Idee¨en? Suggesties? (Oplossing: (12) = b 2 ab 2 ab)
29 / 33
Epiloog: Groepentheorie Doel: I
‘Axiomatische’ opbouw van deze vaststellingen.
I
Verwerven van diepere inzichten. . .
I
. . . die leiden tot meer indrukwekkende resultaten. (Rubik’s cube?)
Definitie Een permutatiegroep G bestaat uit een verzameling permutaties van een verzameling X = {1, 2, . . . , n} met de volgende eigenschappen: I
a, b ∈ G =⇒ ab ∈ G
I
a ∈ G =⇒ a−1 ∈ G
We zeggen ook dat de permutatiegroep G werkt op de verzameling X. 30 / 33
Groepentheorie Als G een groep is en H ⊆ G , dan is H een deelgroep van G als H zelf een permutatiegroep is. We noteren H ≤ G .
Opgave Als G een permutatiegroep is, die werkt op X , en x ∈ X , dan is Gx de verzameling van elementen die x vasthouden. Bewering: Gx ≤ G .
31 / 33
Groepentheorie Stelling (Lagrange) Stel dat G een (permutatie)groep is en H ≤ G . Noem h het aantal elementen van H en g het aantal elementen van G . Dan is h een deler van g . (Of nog: h | g .)
Bewijs
32 / 33
Groepentheorie Als x ∈ X , dan gebruiken we de notatie x G voor ‘de verzameling van alle y ∈ Y waar de groep G het element x naartoe kan sturen’.
Stelling (Baanformule) |G | = |Gx | · |x G |
33 / 33
