title: Topswops
text: 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
  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  t/m . De gepermuteerde rij wordt genoteerd als .
  
  Topswops
  Voor het topswops probleem wordt het volgende algoritme toegepast:
   Bekijk het eerste getal in de rij (dit is ).
   Pak de eerste  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  is.
  
  De uiteindelijke configuratie van de rij getallen begint altijd met een . Andere namen voor dit probleem zijn het deterministic pancake problem, topswops, topswaps, reverse card shuffle en fannkuch.
  
  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 .
  
  Stelling:  is begrensd door .
  
  Bewijs (Herbert S. Wilf): Gegeven een rij getallen  t/m  in een gegeven volgorde. Als voorbeeld beschouwen we . We zijn met name geïnteresseerd in getallen die 'op de juiste plaats in de rij staan', dat zijn hier: . We definiëren het Wilf-getal dan als .
  
  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 , 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  zal altijd op de juiste plaats staan. En omdat de som van de Wilf-getallen van de eerste  getallen altijd strikt kleiner is dan die van  zal het Wilf-getal altijd stijgen (met ten minste 1 per iteratiestap). 
  
  Het maximale Wilf-getal is ook eenvoudig te krijgen, en dat is . Door het bovenstaande bewijs iets te verfijnen kan worden aangetoond dat de genoemde bovengrens ook echt een bovengrens is voor het aantal iteraties. 
  
  Stelling:  is begrensd door het e Fibonaccigetal.
  
  Bewijs (Murray S. Klamkin): Stel dat gedurende het algoritme het eerste getal  in het algoritme in totaal  verschillende waarden aanneemt.
  
  Claim: .
  
  Bewijs: Dit wordt bewezen via wiskundige inductie. Stel , dit betekent dat het algoritme direct stopt (dus ). Zodoende geldt  en aangezien  is de claim bewezen.
  
  Stel nu dat . De  verschillende getallen die  aanneemt, worden als volgt geordend: . We zeggen dat het grootste getal  voor het eerst vooraan staat in de rij in iteratie  van het algoritme. Noem . Dan geldt er in de e iteratie dat  en tevens dat . De resterende iteraties van het algoritme zullen altijd  behouden. Dus  kan nu ten hoogste  waarden aannemen. Uit inductie volgt nu dat  en dat . 
  
  Stel nu dat we de getallen  en  zouden verwisselen in iteratie . Dan  en is het algoritme afgelopen; . Tevens hebben zowel  als  nooit op positie  gestaan tenzij .
  
  Stel . Dan geldt er dan  omdat  ten hoogste  verschillende waarden aanneemt. Dus volgt dat .
  
  Stel . Dan geldt er dan  omdat  ten hoogste  verschillende waarden aanneemt. Zodoende volgt uit de claim dat . Dit bewijst de stelling. 
  
  Daarnaast is recentelijk bewezen door Morales en Sudborough dat de ondergrens voor  een kwadratische functie in  is. Zodoende zijn de echte waarden van  tot op heden onbekend. Wel zijn er verscheidene pogingen gedaan om ondergrenzen te vinden, zoals door A. Pepperdine. 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.
  
  Het is nog steeds een open vraagstuk of dit probleem NP-moeilijk is.
  
  Topdrops
  Een vergelijkbaar probleem is topdrops, waarin dezelfde speelkaarten worden gebruikt. Ook in dit probleem wordt de eerste kaart bekeken (noem deze ). Pak vervolgens de eerste  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
  In deze variant wordt de onderste kaart van de stapel bekeken (wederom ). Vervolgens worden de eerste  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.
  
  Botdrops
  De laatste variant is botdrops waarin de onderste kaart van de stapel wordt bekeken (weer ). Nu worden de onderste  kaarten van de stapel omgewisseld.
  
  Referenties
  
  Externe links
  OEIS: pagina 375 (topswops)
  OEIS: pagina 376 (topswops die gesorteerd eindigt)
  Rosetta code: Topswops berekenen in verschillende programmeertalen
  Topswopscompetitie om het maximale aantal iteraties te berekenen
  
  Recreatieve wiskunde
  Wiskundig vraagstuk