Jeg graver lige lidt tilbage i gruppen... Det er vel også sjovt med noget
arkæologi, hva'?
"Jeppe Stig Nielsen" <mail@jeppesn.dk> wrote in message
news:3CA0D44C.3670108C@jeppesn.dk...
> Okay, nu opdager jeg at I spillede med at man kunne splitte en række
> op i to rækker ved at tage tændstikker midtfra. Så virker min vinder-
> taktik jo ikke.
>
> Det jeg skrev, gælder når man må tage et hvilket som helst antal tænd-
> stikker (ingen øvre grænse, men mindst én tændstik) fra én af rækkerne,
> og når en række aldrig kan splittes til to rækker ved at tage midtfra.
Det sjove er at nøjagtigt samme metode (XOR) kan anvendes, selvom man må
tage tændstikker fra midten og derved splitte en række i to!
Den slags spil har jeg desværre *spildt* bogstaveligt talt månedsvis på at
gruble over (spildt, fordi jeg ikke har fundet en endelig løsning
.
XOR-løsningen fandt jeg selv ud af i 1.g
. Det var simpelthen en af mine
bedste Ahaaa-oplevelser dels at opdage sammenhængen mellem de vundne spil
(hvad kendetegner dem), og dels så at finde ud af hvorfor det er XOR der må
være det rigtige.
Løsningen af Nim kan generaliseres til andre spil, af den type hvor en
position kan ses som "summen" (i en hvis forstand) af flere spil. De
forskellige bunker med tændstikker kan ses som seperate spil der er adderet.
Summen af to spil skal opfattes på følgende måde: I hvert træk kan spilleren
vælge at "trække" i det ene spil, eller i det andet spil, men ikke dem
begge. Taberen (/vinderen) er den spiller, som ikke har noget lovligt træk i
nogen af spillene. Denne spil-sum er selvfølgelig transitiv og kommutativ og
har et indlysende neutral-element (og alt det gælder så heldigvis også for
XOR
.
Et spil (eller rettere: en position) har et Nim-tal defineret på følgende
måde: Nim-tallet af den position hvor man ikke har noget lovligt træk
("0-spillet"), er 0. Nim-tallet af alle andre positioner er det mindste tal
(startende ved 0) som ingen "under-position" (decendant i spil-træet) har.
Man kan selvfølgelig også se at "0-spillet" ikke er et specialtilfælde: den
har ingen decendanter, så det mindste tal er her 0.
Nim-tallet for en bunke med tændstikker er sjovt nok lige præcis antallet af
tændstikker
Nim-tallet for TO bunker med tændstikker er sjovt nok XOR af antallene i
hver bunke.
Og mere generelt: Nim-tallet for "summen" af to spil (i ovennævnte forstand,
ikke nødvendigvis tændstikspillet) er altid XOR af Nim-tallene for de
enkelte spil.
Man har selvfølgelig lov til at lave denne definition for Nim-tal af at
spil. Men definitionen er jo kun interessant hvis man kan bruge den til
levere kamp til stregen med
.
Det interessante ved Nim-tallet er selvfølgelig, som i tændstikspillet, at
man skal aflevere en position med Nim-tal 0.
Undtagelse:
Man kan tænke sig to varianter:
(A) Spilleren uden et lovligt træk har tabt.
(B) Spilleren uden et lovligt træk har vundet.
(mine betegnelser).
Spil A er det simple: Her skal man altid aflevere en position med Nim-tal 0.
Spil B bliver nemt umådeligt kompliceret. Her er Nim-tallet ikke altid nok.
Når positionen bliver "simpel nok" er det ikke altid et "0-træk" der er det
rigtige.
Jeg nævnte at jeg har spildt månedsvis på at gruble over Nim-spil. Det jeg
specifikt har grublet over, er B-spil (idet jeg betragter A-spil som løst,
for så vidt at man kender Nim-tallene for de "irreducible" positioner). Det
ser ud til at man ikke kan nøjes med Nim-tal, eller alternativt at
Nim-tallene ikke skal være de naturlige tal, men en anden algebraisk
struktur.
Jeg har fundet eksempler på spil, hvor denne struktur bliver overordentlig
kompliceret, og jeg har langt fra fundet nogen generelle principper som man
kan bruge til alle Nim-spil. Jeg måtte finde på "Nimtal" såsom 0*, 1* som
har "næsten samme egenskaber" som 0 og 1, men ikke helt. Fx. var 2 + 2 = 0*
i visse B-spil
, og a+b*=(a+b)*, og a**=a*.
Til tændstik-spillet i variant (B) er det dog meget nemt: Såsnart der kun er
én bunke tilbage med mere end en tændstik, skal man efterlade et ulige antal
enlige tændstikker, men indtil da skal man spille som i variant (A).
Tændstik-spillet hvor man tillader at tage tændstikker midt i en række, har
præcis samme strategi som hvis dette ikke er tilladt - uanset om man spiller
variant A eller B.
Et simpelt Nim-spil, hvis B-variant giver komplicerede "Nim-tal" er
2-dimensionalt tændstikspil: Man spiller fx på ternet papir, og må sætte
krydser på ubrudt række (lodret eller vandret), lige så mange man vil
(mindst et ;). Den der sætter det sidste kryds har tabt.
Når to områder er blevet adskilt fra hinanden, kan man betragte spillet som
summen af de to områder. Så nu skal vi bare finde Nim-tal for sammenhængende
områder:
X: 1
XX: 2
XX: 3
X
(thi man kan frembringe spillene 1, 2 og 1+1=0, så det mindste man ikke kan
lave, er 3)
XX: 0
XX
(thi man kan frembringe 2 og 3, så 0 er det mindste man ikke kan lave).
Blokken
XX
XX
er den første der bliver problematisk i B-varianten, for den er ikke "helt"
ækvivalent med 0-spillet når man summer den sammen med andre spil. En
notation der måske kan bruges, er [2,3] i betydningen "har decendanter med
værdier 2 og 3". Jeg har ikke nogen rigtig konkret ide om hvad kriteriet er
for at to spil [a,b,...] og [j,k,...] er "ækvivalente" (dvs. kan altid
udskiftes med hinanden som komponenter i større spil, og bevarer vundet/tabt
værdien herved)
Jeg havde engang en hjemmeside om dette emne, hvor jeg også havde nogle
beviste sætninger, og en "conjecture", men den er desværre gået tabt til de
evige bitmarker :).
Lad os lige for sjovs skyld se på det spil, der oprindeligt blev spurgt om:
Man må tage 1, 2 eller 3 tændstikker. Jamen, så er Nim-tallet for positionen
med n tændstikker bare (n mod 4)
0 giver 0
1 giver 1, fordi vi kan lave 0-position
2 giver 2, fordi vi kan lave 0- og 1-position
3 giver 3, fordi vi kan lave 0, 1 og 2
4 giver 0, fordi vi kan lave 1, 2 og 3
5 giver 1, fordi vi kan lave 2, 3 og 0
osv.
Det tal kan så kun bruges i A-varianten.
Mvh. Bjarke