Topswops

Topswops (en de varianten Topdrops, Bottomswops en Bottomdrops) zijn wiskundige problemen die zijn bedacht door de Britse wiskundige John Conway in 1973. In tegenstelling tot veel andere werken van Conway zijn deze problemen nog niet grondig geanalyseerd door de wetenschappelijke gemeenschap. Enkele bekende wiskundigen die een bijdrage hebben geleverd zijn Martin Gardner en Donald Knuth.

Formulering[bewerken | brontekst bewerken]

In alle vier varianten gaat Conway uit van een pak speelkaarten. Omdat slechts de getalwaarden relevant zijn, wordt vaak een van de kleuren van een kaartspel gebruikt. Wiskundig gezien is dit equivalent met een rij gehele getallen van $1$ t/m $N$ . De gepermuteerde rij wordt genoteerd als $A[1],...,A[N]$ .

Topswops[bewerken | brontekst bewerken]

Voor het topswops probleem wordt het volgende algoritme toegepast:

Bekijk het eerste getal in de rij (dit is $A[1]$ ).
Pak de eerste $A[1]$ kaarten van de stapel.
Verwissel deze kaarten van volgorde en plaats ze boven op de stapel terug.
Herhaal stap 1, 2 en 3 totdat het eerste getal een $1$ is.

De uiteindelijke configuratie van de rij getallen begint altijd met een $1$ . Andere namen voor dit probleem zijn het deterministic pancake problem, topswops, topswaps, reverse card shuffle en fannkuch.^[1]^[2]^[3]

De probleemformulering van Conway is nu als volgt:

Welke initiële configuratie leidt tot het maximale aantal 'swaps' voordat het algoritme termineert?

In de literatuur zijn verscheidene pogingen gedaan om een bovengrens te vinden voor het aantal iteraties $f(N)$ .

Stelling: $f(N)$ is begrensd door $2^{N-1}$ .

Bewijs (Herbert S. Wilf^[2]): Gegeven een rij getallen $1$ t/m $N$ in een gegeven volgorde. Als voorbeeld beschouwen we $7,2,11,8,5,13,6,1,9,10,3,12,4$ . We zijn met name geïnteresseerd in getallen die 'op de juiste plaats in de rij staan', dat zijn hier: $2,5,9,10,12$ . We definiëren het Wilf-getal dan als $2^{(2-1)}+2^{(5-1)}+2^{(9-1)}+2^{(10-1)}+2^{(12-1)}=2833$ .

Claim: na iedere iteratie van het algoritme stijgt het Wilf-getal.

Bewijs: Voor ieder getal dat op de juiste plaats stond, en groter was dan het getal $A[1]$ , blijft de invloed op het Wilf-getal onveranderd. De overige getallen die wel op de juiste plaats stonden, zullen in het algemeen niet meer op de juiste plaats staan. Echter, het getal $A[1]$ zal altijd op de juiste plaats staan. En omdat de som van de Wilf-getallen van de eerste $A[1]-1$ getallen altijd strikt kleiner is dan die van $A[1]$ zal het Wilf-getal altijd stijgen (met ten minste 1 per iteratiestap). $\square$

Het maximale Wilf-getal is ook eenvoudig te krijgen, en dat is $2^{N+1}-1$ . Door het bovenstaande bewijs iets te verfijnen kan worden aangetoond dat de genoemde bovengrens ook echt een bovengrens is voor het aantal iteraties. $\square$

Stelling: $f(N)$ is begrensd door het $N+1$ e Fibonaccigetal.

Bewijs (Murray S. Klamkin^[4]): Stel dat gedurende het algoritme het eerste getal $A[1]$ in het algoritme in totaal $k$ verschillende waarden aanneemt.

Claim: $f(N)\leq F_{k+1}$ .

Bewijs: Dit wordt bewezen via wiskundige inductie. Stel $k=1$ , dit betekent dat het algoritme direct stopt (dus $f(N)=0$ ). Zodoende geldt $A[1]=1$ en aangezien $F_{2}=1$ is de claim bewezen.

Stel nu dat $k\geq 2$ . De $k$ verschillende getallen die $A[1]$ aanneemt, worden als volgt geordend: $d_{1}<...<d_{k}$ . We zeggen dat het grootste getal $d_{k}$ voor het eerst vooraan staat in de rij in iteratie $r$ van het algoritme. Noem $t=A[d_{k}]$ . Dan geldt er in de $(r+1)$ e iteratie dat $A[1]=t$ en tevens dat $A[d_{k}]=d_{k}$ . De resterende iteraties van het algoritme zullen altijd $A[d_{k}]=d_{k}$ behouden. Dus $A[1]$ kan nu ten hoogste $k-1$ waarden aannemen. Uit inductie volgt nu dat $f(N)-r\leq F_{k}$ en dat $d_{1}=1$ . $\square$

Stel nu dat we de getallen $d_{1}=1$ en $d_{k}$ zouden verwisselen in iteratie $r$ . Dan $A[1]=1$ en is het algoritme afgelopen; $f(N)=r$ . Tevens hebben zowel $d_{k}$ als $t$ nooit op positie $A[1]$ gestaan tenzij $t=1$ .

Stel $t=1$ . Dan geldt er dan $r\leq F_{k}$ omdat $A[1]$ ten hoogste $k-1$ verschillende waarden aanneemt. Dus volgt dat $f(N)\leq r+1\leq F_{k+1}$ .

Stel $t>1$ . Dan geldt er dan $r\leq F_{k-1}$ omdat $A[1]$ ten hoogste $k-2$ verschillende waarden aanneemt. Zodoende volgt uit de claim dat $f(N)\leq F_{k}+r\leq F_{k+1}$ . Dit bewijst de stelling. $\square$

Daarnaast is recentelijk bewezen door Morales en Sudborough dat de ondergrens voor $f(N)$ een kwadratische functie in $N$ is.^[1] Zodoende zijn de echte waarden van $f(N)$ tot op heden onbekend. Wel zijn er verscheidene pogingen gedaan om ondergrenzen te vinden, zoals door A. Pepperdine.^[5] Voor rijtjes met 17 of minder getallen is de exacte oplossing bekend. Grotere getallen hebben slechts ondergrenzen, zoals weergegeven in de figuren aan de rechterkant.

aantal getallen	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
maximale aantal iteraties	0	1	2	4	7	10	16	22	30	38	51	65	80	101	113	139	159

Het is nog steeds een open vraagstuk of dit probleem NP-moeilijk is.

Topdrops[bewerken | brontekst bewerken]

Een vergelijkbaar probleem is topdrops, waarin dezelfde speelkaarten worden gebruikt. Ook in dit probleem wordt de eerste kaart bekeken (noem deze $A[1]$ ). Pak vervolgens de eerste $A[1]$ kaarten van de stapel, wissel deze van volgorde en plaats ze vervolgens onder op de stapel (in plaats van bovenop bij topswops). In dit probleem is het mogelijk om in een oneindige lus terecht te komen. Als voorbeeld nemen we 2,1,3,4. Dan gebeurt er het volgende:

2 1 3 4
3 4 1 2
2 1 4 3
4 3 1 2
2 1 3 4

waarna het algoritme terug is bij de eerste stap.

Botswops[bewerken | brontekst bewerken]

In deze variant wordt de onderste kaart van de stapel bekeken (wederom $A[1]$ ). Vervolgens worden de eerste $A[1]$ kaarten van de stapel gewisseld. Zodoende gebeurt er vrijwel nooit iets, tenzij de laatste kaart van de rij het hoogste getal is. Deze variant van het probleem is oninteressant omdat de dynamica zo gelimiteerd is.^[2]

Botdrops[bewerken | brontekst bewerken]

De laatste variant is botdrops waarin de onderste kaart van de stapel wordt bekeken (weer $A[1]$ ). Nu worden de onderste $A[1]$ kaarten van de stapel omgewisseld.

Referenties[bewerken | brontekst bewerken]

↑ ^a ^b (en) Morales, Linda en Sudborough, Hal (2010). A quadratic lower bound for Topswops. Theoretical Computer Science 411 (44-46): 3965-3970. DOI: 10.1016/j.tcs.2010.08.011.
↑ ^a ^b ^c (en) Gardner, Martin (1987), Time Travel and Other Mathematical Bewilderments. W. H. Freeman & Co, New York, "6", pp. 76-82. ISBN 978-0716719250.
↑ (en) Knuth, Donald E. (2002), The Art of computer programming: Volume 4, Fascicle 2A: Generating all n-tuples. Addison-Wesley, 74, 119-120. ISBN 978-0201853933.
↑ (en) Klamkin, Murray S. (1990), Problems in Applied Mathematics: Selections from SIAM review. SIAM, 74, 115-117. ISBN 978-0898712599.
↑ (en) Pepperdine, Andy (1989). 73.23 Topswops. The Mathematical Association 73 (464): 131-133. DOI: 10.2307/3619674. “Een vernieuwde versie van het artikel is te vinden via https://www.pepsplace.org.uk/Trivia/Topswops/Topswops.pdf.”.

Externe links[bewerken | brontekst bewerken]

[Morales2010-1] (en) Morales, Linda en Sudborough, Hal (2010). A quadratic lower bound for Topswops. Theoretical Computer Science 411 (44-46): 3965-3970. DOI: 10.1016/j.tcs.2010.08.011.

[Gardner1987-2] (en) Gardner, Martin (1987), Time Travel and Other Mathematical Bewilderments. W. H. Freeman & Co, New York, "6", pp. 76-82. ISBN 978-0716719250.

[Knuth2002-3] (en) Knuth, Donald E. (2002), The Art of computer programming: Volume 4, Fascicle 2A: Generating all n-tuples. Addison-Wesley, 74, 119-120. ISBN 978-0201853933.

[Klamkin1990-4] (en) Klamkin, Murray S. (1990), Problems in Applied Mathematics: Selections from SIAM review. SIAM, 74, 115-117. ISBN 978-0898712599.

[Pepperdine1989-5] (en) Pepperdine, Andy (1989). 73.23 Topswops. The Mathematical Association 73 (464): 131-133. DOI: 10.2307/3619674. “Een vernieuwde versie van het artikel is te vinden via https://www.pepsplace.org.uk/Trivia/Topswops/Topswops.pdf.”.

[1]

[2]

[3]

[4]

[5]