Ketil Bergesen,

Høgskolen i Bergen

• Slå opp på side 69 og gjør oppgave 14 a-f, 16a,b,c og 21 - 26 ! De som blir fort ferdige kan prøve seg på de litt vanskeligere oppgavene på side 72…
• Må vi ….?

Høres det kjent ut ? Jeg har ført den "samtalen" på begge sider av kateteret selv. Men følelsen av å måtte dra eller bli dratt er ikke god. Når vi ser hvor dypt konsentrerte og engasjerte unger kan være gjennom spill, tenker jeg at det bør vies større plass i undervisninga.

Jeg vil her presentere et gammelt spill av tyrkisk opprinnelse, Nim, som jeg har brukt i klasserommet mange ganger. Vi skal se på forskellige varianter av spillet og kikke litt på matematikken bak det.

En variant av spillet er: Legg fyrstikker i hauger på 1, 3, 5, 7 som vist under. De to spillerne trekker ut fyrstikker annenhver gang etter følgende regel: Den som har tur kan ta ut så mange hun vil, men bare fra én haug. (neste gang må hun gjerne ta fra en annen haug, men bare fra den.)

Etter en del strev fant vi ut at det ikke lønte seg å begynne, og vi visste for eksempel at dersom man tok ut så det lå igjen 1, 2, 4, og 7 fyrstikker ville man vinne. Men hva om det

Prøv det gjerne ut før du leser videre!

Jeg fant ikke den vinnende strategi og "glemte" spillet. Ca. 20 år seinere fant jeg det igjen på internett, nettopp med tilfeldige antall for hvert spill. Interessen ble vekket på ny og påsken 2000 ble ikke barnas påske. Pappa responderte ikke på verdenen utenfor ham og hvis så var, var det med et seigt hmm. Men endelig var pappa kjempeglad og deltok i leiken ; Han hadde funnet løsningen !!

Det fins mange forenkla utgaver av spillet som kan gjøre det utfordrende for noen hver:

1. Legg noen få fyrstikker i en haug. Det er lov å ta ut en ad gangen.
   Vinner du hvis du begynner? Telling, partall, oddetall, reversering. Dette kan være utfordring stor nok for 5-6-åringen.
2. En haug med fyrstikker, men det er lov å ta ut 1 eller 2 fyrstikker ad gangen. Gangetabellen, divisjon med rest. Moduloregning. Barne og mellomtrinnet.
3. En haug der man må ta ut minst 1, maksimum n. Finn hvilke situasjoner det lønner seg å begynne i uttrykt ved n.
4. Flere hauger med fast spillebrett for eksempel 1, 3, 5, 7. Adskillig vanskeligere og passe for mellom eller ungomstrinnet.
5. Spillet henvist til pr. internettadresse.
6. Lag egne regler.

Vi skal se på det mest generelle spillet, nr. 5, og prøve å "knekke koden".

Et spørsmål til avklaring først:

Er det slik i situasjonen på bildet over at man alltid kan vinne dersom motstanderen begynner? Eller mer generelt, er det slik at gitt en vilkårlig startposisjon så kan du alltid vinne hvis du får bestemme hvem som skal begynne? Følgende utsagn er ikke uvanlig:
"I starten er det ikke så nøye hva man gjør, det er på slutten man må begynne å tenke".

Vi skal se at er nøye fra første trekk.

Før vi går videre trenger vi et felles språk. Når du har gjort et trekk står du kanskje til gevinst. Dersom en slik posisjon fins kaller vi den en vinner. Eksempelvis er følgende tre situasjoner vinnere:

1, 1. 2, 2 1, 2, 3.

Situasjoner med én bunke er lette: Alle er tapere, motstanderen tar ut alle og har vunnet.

Situasjoner med to bunker: En sikker vinner er situasjon 1) ; motstanderen må ta den nest siste og du den siste.

Enhver situasjon som kan gjøres om til 1, 1 i et trekk, for eksempel 1, 5 er følgelig en taper.

2, 2 derimot kan ikke gjøres om til 1, 1 i et trekk og er en vinner. Tilsvarende er alle situasjoner på formen n, n vinnere da man kan "kopiere" motstanderens trekk og holde "balansen" med like mange i hver haug. Før eller siden må motstanderen overlate deg en

null-k-situasjon.

Tilsvarende kan vi tenke om situasjoner med tre, fire,… mange hauger. Vi kan jobbe "i revers" og finne at for eksempel 1, 2, 3, 1, 4, 5, 1, 6, 7 og 2, 4, 6 alle er vinnere.

I kartleggingen av vinnerne så jeg et slags mønster, for eksempel er alle tre-bunkere på formen 1, 2n, 2n+1 vinnere. Det samme for 3, 4n+1, 4n+2 og for 6, 8n+3, 8n+5.

Vinnerne så ut til å gruppere seg på en måte som hadde med toerpotenser å gjøre.

Vi har følgende situasjon: 9, 11, 6 = 1+8, 1+2+8, 2+4. Dette er representert som rekker av 1-er, 2-er 4-er og 8-er-blokker under. Merk at vi har maksimalt én blokk av hver type i hver rad. For eksempel vil to 4-er blokker kunne limes sammen til en 8-er blokk.

Ordet "balanse" om situasjoner med to hauger ble brukt over. Dette er et nøkkelord generelt. Vi ommøblerer blokkene litt og får:

Balansestrek

Betrakt nå dette som en vekt der vi har som mål å etterlate oss balanse *), dvs vi vil ha like mange 1-er blokker 2-er-blokker osv. på hver side. Men husk, vi får bare ta ut fra en "hylle" (dvs rad) ad gangen. Vi har en ubalanse her, en 4-er blokk for mye på venstre side. Vi fjerner 4-er blokka og oppnår likevekt, dvs vi fjerner 4 fyrstikker fra haug 3 og får 2, 9, 11. Hva kjennetegner en slik likevekt? Jo, at det fins et partall antall 1-ere, 2-ere osv på hver side av balansestreken. Når det er motstanderens tur kan hun sage klosser og møblere som hun vil på samme hylle, men hun må fjerne minst én kloss/fyrstikk. Dette betyr at hun må fjerne en eller flere blokker på en hylle og siden det maksimalt finnes en av hver blokktype må hun for en eller annen blokktype etterlate seg et oddetall av denne typen, dvs ubalanse.

Vi har sett at vi kan aldri oppnå balanse i ett trekk med balanse som utgangspunkt. Hvis vi i tillegg kan vise at vi alltid kan oppnå balanse fra ubalanse er vinnerstrategien grei: Er det balanse når det er din tur, ta ut et vilkårlig , men lite antall fra en tilfeldig haug og håp at motstanderen gjør en feil. Er det ubalanse, skaff balanse, motstanderen må gi ubalanse igjen, du balanse osv…

Spørsmålet vi må besvare er altså følgende: Gitt ubalanse, kan vi alltid oppnå balanse? Svaret er ja og begrunnelsen er følgende: Hvis det finnes ubalanse så fins det minst en blokktype som det er oddetall av. Vi døper den største typen det er ubalanse av TOL. Vi går til en hylle der det fins en TOL, og sager den i mindre enheter. Da får vi en av hver mindre enhet og enda en 1-er til overs.

For eksempel er 64 = 32+16+8+4+2+1+1.

Det er nå balanse for TOL-størrelsen (og alle større blokker). For størrelsene under fyller vi de tomme plassene med passende sagbiter slik at det blir nøyaktig én av hver blokk på TOL-hylla. For hver blokkstørrelse skaffes balanse; Ta vekk en blokk dersom ubalanse for denne typen, la den ellers være.

Følgende situasjon er gitt 3, 5, 7, 28, 23. Vi skriver opp disse i en tabell som viser hvilke blokker som inngår for hvert tall.

Vi ser det er ubalanse i 8-er blokka og 2-er blokka. Tallet 28 er det eneste tallet som har en 8-er. Vi endrer tallene i denne raden slik at vi får partall som sum for hver blokk:

Det vi ønsker å stå igjen med er tallet x = 16+4+2 = 22, vi tar altså ut 28 - 22 = 6 fra haugen med 28 i og har skaffa oss balanse og dermed seieren.

Vi har sett at vi finner vinnerstrategien ved å betrakte binærutviklinga til tallene (tallene i totallsystemet). Kunne vi like gjerne ha brukt 3-tall-systemet eller enda bedre titallsystemet som vi er vant til å regne med? Hint: Da er det mulig å ha flere enn en av hver blokktype på en hylle.

Å finne en slik løsning på egenhånd er vanskelig. Men med ideene og billedlig-gjøringen skissert over vil det være lettere å geleide elevene mot å gjennomskue spillet.

Så håper jeg mange løper og kjøper fyrstikker med det samme! Måtte alle vinne!