Topswops

Topswops (och varianterna Topdrops , Bottomswops och Bottomdrops ) är matematiska problem som utarbetades och analyserades av den brittiske matematikern John Conway 1973. I motsats till andra spel och problem som introducerats av Conway har dessa problem inte fått så mycket uppmärksamhet från det vetenskapliga samfundet. Två kända matematiker som har bidragit till problemet är Martin Gardner och Donald Knuth .

Ett Topswops-exempel med $N=5$ nummer. Algoritmen avslutas efter 7 iterationer.

Formulering

I varje variant av problemet använder Conway en kortlek . Eftersom de numeriska värdena för kortleken endast är relevanta används endast en färg . Detta motsvarar matematiskt en rad med heltal från $1$ till $N$ . En blandad hög med kort skrivs som $A[1],...,A[N]$ .

Topswops

För topswops används följande algoritm :

1. Tänk på det första kortet från högen (som är $A[1]$ )
2. Ta de första $A[1]$ korten från högen
3. Byt ut dessa kort och lägg dem tillbaka på högen
4. Upprepa steg 1, 2 och 3 tills det översta kortet är $1$

Den slutliga konfigurationen av raden börjar alltid med $1$ . Topswops - problemet heter ibland annorlunda, med namngivning inklusive deterministiskt pannkaksproblem , topswops , topswaps , omvänd kortblandning och fannkuch .

Problemet som formulerats av Conway är följande:

Vilken initial konfiguration leder till det maximala antalet 'swops' innan algoritmen avslutas?

I litteraturen finns det några försök att hitta nedre och övre gränser för antalet iterationer $f(N)$ .

Sats: $f(N)$ begränsas av $2^{N-1}$ .

Bevis av Herbert S. Wilf: Betrakta en permutation $A[1]$ till $A[N]$ av raden $1$ till $N$ . Som ett exempel betraktar vi $7,2,11,8,5,13,6,1, 9,10,3,12,4$ . Vi är särskilt intresserade av siffror som är i "rätt position". Dessa är: 2, 5, 9, 10, 12. Vi definierar Wilf-talet som $2^{(2-1)}+2^{(5-1)}+2^{(9-1)}+2^{(10-1)}+2^ {(12-1)}=2833$ .

Påstående: efter varje iteration av algoritmen ökar Wilf-talet.

Bevis: Vi utför en iteration av algoritmen. Varje nummer i 'rätt position' och större än $A[1]$ lämnar Wilf-talet oförändrat. De återstående siffrorna på "rätt position" kommer i allmänhet inte att vara på "rätt position" längre. Ändå $A[1]$ på rätt position. Och eftersom summan av de första $A[1]-1$ Wilf-talen alltid är mindre än Wilf-talet för $A[1]$ , det totala Wilf-talet ökar alltid (med minst 1 per iteration av algoritmen). $\square$

Det maximala Wilf-talet hittas när varje nummer är på rätt position. Så det maximala Wilf-talet är $2^{N+1}-1$ . Genom att förfina beviset kan den givna övre gränsen bevisas vara en verklig övre gräns för antalet iterationer. $\square$

Topswops: relationen mellan $N$ och $f(N)$ i en semi-logaritmisk graf . Den övre gränsen är lös, medan den nedre gränsen är ganska snäv.

Topswops: den förväntade relationen mellan $N$ och $f(N)$ i en dubbellogaritmisk graf . Datapunkterna i grafen är bara några permuterade rader och är lägre gränser för det verkliga värdet. Den övre gränsen är återigen mycket lös, medan den nedre gränsen är relativt snäv.

Sats: $f(N)$ begränsas av ${\displaystyle (N+1)}:$ e Fibonacci-talet .

Bevis av Murray S. Klamkin : Antag att under algoritmen tar det första talet $A[1]$ totalt $k$ distinkta värden.

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

Bevis: Vi bevisar påståendet genom matematisk induktion . För $k=1$ avslutas algoritmen direkt, därför $f(N)=0$ . Således $A[1]=1$ och eftersom $F_{2}=1$ är påståendet bevisat.

Vi tar nu några $k\geq 2$ . Alla $k$ -värden som $A[1]$ tar på, är ordnade och kan skrivas som: $d_{1}<...<d_{k}$ . Antag att det största värdet av dessa värden, som är $d_{k}$ , inträffar för första gången vid position $1$ under iterationen $r$ av algoritmen. Beteckna $t=A[d_{k}]$ . Under $(r+1)$ 'te iterationen vet vi att $A[1]=t$ och $A[d_{k}]=d_{k}$ . De återstående iterationerna kommer alltid att behålla $A[d_{k}]=d_{k}$ . Därför $A[1]$ nu ta på högst $k-1$ -värden. Med induktion för $k$ följer det att $f(N)-r\leq F_{k}$ och även att $d_{ 1}=1$ . $\square$

Antag att vi skulle byta ut $d_{1}=1$ och $d_{k}$ i iteration $r$ Sedan $A[1 ]=1$ och algoritmen avslutas; $f(N)=r$ . Under algoritmen är vi säkra på att både $d_{k}$ och $t$ aldrig har varit i position $A[1]$ , såvida inte ${\ displaystil t=1}$ .

Antag att $t=1$ . Då $r\leq F_{k}$ eftersom $A[1]$ tar på som mest $k-1$ distinkta värden. Så det följer att $f(N)\leq r+1\leq F_{k+1}$ .

Antag att $t>1$ . Då $r\leq F_{k-1}$ eftersom $A[1]$ tar på som mest $k-2$ distinkta värden. Med påståendet följer att $f(N)\leq F_{k}+r\leq F_{k+1}$ . Detta bevisar satsen. $\square$

Förutom dessa resultat har Morales och Sudborough nyligen bevisat att den nedre gränsen för $f(N)$ är en kvadratisk funktion i $N$ . De optimala värdena är dock fortfarande okända. Det har gjorts flera försök att hitta de optimala värdena, till exempel av A. Pepperdine. För rader med 17 eller färre nummer är den exakta lösningen känd. Större rader har bara nedre gränser, vilket visas till höger.

radlängd	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
maximalt antal iterationer	0	1	2	4	7	10	16	22	30	38	51	65	80	101	113	139	159

Det är ännu okänt om detta problem är NP-svårt .

Topdrops

Ett liknande problem är topdrops , där samma spelkort används. I det här problemet visas det första kortet i högen (och har värdet ${\displaystyle A[1]} )$ . Ta de första ${\displaystyle A[1]}-$ korten i högen, ändra ordningen och placera dem tillbaka på botten av högen (vilket står i kontrast till topswops , där korten är placerade överst). Detta problem tillåter oändliga loopar . Som ett exempel betraktar vi raden 2,1,3,4. Genom att tillämpa algoritmen erhålls följande sekvens:

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

varefter den ursprungliga raden återfinns.

Botswops

I denna variant tas det nedersta kortet i högen (och återigen benämns ${\displaystyle A[1]} )$ . Sedan byts de första $A[1]$ korten i högen. Om inte det nedersta kortet är det högsta kortet i högen händer ingenting. Detta gör problemet ointressant på grund av det begränsade beteendet.

Botardroppar

Den sista varianten är botdrops där det nedersta kortet i högen tas (återigen ${\displaystyle A[1]} )$ . I den här varianten byts de nedersta ${\displaystyle A[1]} korten.$

externa länkar

• OEIS : sida 375 (topswops)
• OEIS : sida 376 (topswops som hamnar sorterad)
• Rosetta-kod: Computing Topswops på flera programmeringsspråk
• Topswops-tävling för att beräkna det maximala antalet iterationer