Subtrahera en kvadrat

Subtrahera-en-kvadrat (även kallad take-a-square ) är ett matematiskt subtraktionsspel för två spelare . Det spelas av två personer med en hög med mynt (eller andra polletter) mellan sig. Spelarna turas om att ta bort mynt från högen och tar alltid bort ett kvadratantal som inte är noll . Spelet spelas vanligtvis som ett vanligt spelspel, vilket innebär att spelaren som tar bort det sista myntet vinner. Det är ett opartiskt spel , vilket innebär att uppsättningen av drag som är tillgängliga från vilken position som helst inte beror på vems tur det är. Solomon W. Golomb krediterar uppfinningen av detta spel till Richard A. Epstein .

Exempel

Ett normalt spel som börjar med 13 mynt är en vinst för den första spelaren förutsatt att de börjar med en subtraktion på 1:

spelare 1: 13 - 1*1 = 12

Spelare 2 har nu tre val: subtrahera 1, 4 eller 9. I vart och ett av dessa fall kan spelare 1 se till att siffran 2 inom några få drag skickas vidare till spelare 2:

spelare 2: 12 - 1*1 = 11 spelare 2: 12 - 2*2 = 8 spelare 2: 12 - 3*3 = 3 spelare 1: 11 - 3*3 = 2 spelare 1: 8 - 1*1 = 7 spelare 1: 3 - 1*1 = 2 spelare 2: 7 - 1*1 = 6 eller: 7 - 2*2 = 3 spelare 1: 6 - 2*2 = 2 3 - 1*1 = 2

Nu måste spelare 2 subtrahera 1, och spelare 1 gör sedan samma sak:

spelare 2: 2 - 1*1 = 1 spelare 1: 1 - 1*1 = 0 spelare 2 förlorar

Matematisk teori

I exemplet ovan representerar siffran "13" en vinnande eller "het" position, medan siffran "2" representerar en förlorande eller "kall" position. Med tanke på en heltalslista med varje heltal märkt "hett" eller "kallt", är spelets strategi enkel: försök att skicka vidare ett "kallt" nummer till din motståndare. Detta är alltid möjligt förutsatt att du får ett "hett" nummer. Vilka nummer som är "heta" och vilka som är "kalla" kan bestämmas rekursivt :

siffran 0 är "kall", medan 1 är "het"
om alla siffror 1 .. N har klassificerats som antingen "varma" eller "kalla", då
- talet N+1 är "kallt" om bara "heta" tal kan nås genom att subtrahera en positiv kvadrat
- talet N+1 är "hett" om minst ett "kallt" tal kan nås genom att subtrahera en positiv kvadrat

Med hjälp av denna algoritm kan en lista med kalla siffror enkelt härledas:

0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, … (sekvens A030193 i OEIS )

En snabbare dela och erövra algoritm kan beräkna samma sekvens av tal, upp till valfri tröskel $n$ , i tiden $O(n\log ^{2}n)$ .

Det finns oändligt många kalla nummer. Ännu starkare måste antalet kalla nummer upp till någon tröskel $n$ vara åtminstone proportionell mot kvadratroten av $n$ , för annars skulle det inte finnas tillräckligt många för att ge vinnande drag från alla de heta siffrorna. Kalla tal tenderar att sluta på 0, 2, 4, 5, 7 eller 9. Kalla värden som slutar med andra siffror är ganska ovanliga. Detta gäller särskilt för kalla nummer som slutar på 6. Av alla över 180 000 kalla nummer mindre än 40 miljoner slutar bara ett på 6: 11 356.

Inga två kalla tal kan skilja sig åt med en kvadrat, för om de gjorde det skulle en flytt från det största av de två till det mindre vinna, vilket motsäger antagandet att de båda är kalla. Därför, enligt Furstenberg–Sárközy-satsen , är den naturliga tätheten för de kalla talen noll. Det vill säga, för varje $\epsilon >0$ , och för alla tillräckligt stora ${\displaystyle n} , är$ bråkdelen av siffrorna upp till $n$ som är kalla mindre än ${\ displaystyle \epsilon }$ . Mer starkt, för varje $n$ som finns

O(n/(\log n)^{{\frac {1}{4}}\log \log \ log \log n})

kalla nummer upp till $n$ . Den exakta tillväxthastigheten för de kalla talen förblir okänd, men experimentellt verkar antalet kalla positioner upp till en given tröskel $n$ vara ungefär $n^{0,7}$ .

Tillägg

Spelet subtrahera-en-ruta kan också spelas med flera siffror. Vid varje tur väljer spelaren att göra ett drag först ett av siffrorna och subtraherar sedan en kvadrat från det. En sådan "summa av normala spel" kan analyseras med hjälp av Sprague-Grundy-satsen . Detta teorem säger att varje position i spelet subtrahera-en-kvadrat kan mappas till en ekvivalent nim-högstorlek . Optimalt spel består av att flytta till en samling tal så att nim-summan av deras ekvivalenta nim-högstorlekar är noll, när detta är möjligt. Den ekvivalenta nim-högstorleken för en position kan beräknas som det minsta exkluderade värdet av de ekvivalenta storlekarna på positionerna som kan nås med ett enda drag. För subtrahera-en-kvadratpositioner med värdena 0, 1, 2, ... är de ekvivalenta nim-högstorlekarna

0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 2, 3, 4, … (sekvens A014586 i OEIS ).

I synnerhet är en position för subtrahera-en-kvadrat kall om och endast om dess ekvivalenta nim-högstorlek är noll.

Det är också möjligt att spela varianter av detta spel med andra tillåtna drag än kvadratsiffrorna. Till exempel definierade Golomb ett analogt spel baserat på Moser–de Bruijn-sekvensen , en sekvens som växer i en liknande asymptotisk hastighet som kvadraterna, för vilken det är möjligt att lättare bestämma uppsättningen av kalla positioner och definiera en lättberäknad optimal flyttstrategi.

Ytterligare mål kan också läggas till för spelarna utan att vinstvillkoren ändras. Till exempel kan vinnaren ges en "poäng" baserat på hur många drag det tog att vinna (målet är att få lägsta möjliga poäng) och förloraren får målet att tvinga vinnaren att ta så lång tid som möjligt att nå seger. Med detta ytterligare par av mål och ett antagande om optimalt spel av båda spelarna, är poängen för startpositionerna 0, 1, 2, ...

0, 1, 2, 3, 1, 2, 3, 4, 5, 1, 4, 3, 6, 7, 3, 4, 1, 8, 3, 5, 6, 3, 8, 5, 5, 1, 5, 3, 7, … (sekvens A338027 i OEIS ).

Misère spel

Subtrahera-en-ruta kan också spelas som ett misère -spel, där spelaren som ska göra den sista subtraktionen förlorar. Den rekursiva algoritmen för att bestämma "heta" och "kalla" siffror för misère-spelet är densamma som för det vanliga spelet, förutom att för misère-spelet är siffran 1 "kall" medan 2 är "het". Det följer att de kalla siffrorna för misère-varianten är de kalla siffrorna för det normala spelet skiftat med 1:

Misère spelar "kalla" nummer: 1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35, 40, 45, ...

Se även