Hanoitårnet - Løsning

Fysisk institutt og ILS, UiO, Andersen og Øgrim,1998
Fysikkforsøk for videregående skoler

Del G: Spill og leker

G01 Informatikk

Hanoi - Cardan og sjakkbrettet

Stikkord:
2-tallsystemet
Informatikk Vi har tatt med disse forsøkene selv om det ikke dreier seg om fysikk; men det er ikke langt unna, og vi syns de er artige.

Både Hanoitårnet og Cardans ringer er brukt som øvingsoppgaver i dataprogrammering. Det skal være forholdsvis lett å lage programmer som løser problemene.

Utstyr:
Sjakkbrett
Noe å lage hanoitårn med, f eks 5 ulike mynter. eller stableleker
Hanoitårnet
Da verden ble skapt, satte guden tre store diamantstolper i et tempel, som kanskje var i Hanoi. På en av pinnene trædde hun 64 solide gullskiver; den aller største underst og så ble de mindre og mindre oppover. Munkene i templet ble så satt til å flytte skivene over til en av de andre stolpene. De måtte bare flytte en skive om gangen, bare fra en stolpe til en annen, men alltid sånn at en mindre skive lå oppå en som var større. I det øyeblikket munkene ble ferdige med dette arbeidet, ville verden forgå. Når kommer det til å skje?

Det er gjort grundige studier av dette problemet, og dere kan finne det behandlet mange steder på WEBnettet. Antall trekk blir N = 2⁶⁴ - 1.

Hvis munkene flytter 1 skive/s, er de nok ikke kommet halvveis ennå, selv om vi regner nokså høy alder for vår klode. En antydning av hvordan man flytter brikkene følger seinere i manus. Man kan jo øve seg med bare 3 eller 4 eller kanskje 7 skiver på tre pinner. Man kan også bruke passende stableleker for barn. Hanoitårn med 7 ringer kan man kanskje finne i noen leketøysforretninger.
En annen historie går ut på at det var indiske guder som satte i gang dette spillet. Det var skaperen Brahma som lagde en pyramide med 42 mindre og mindre steiner oppå hverandre. Prestene flytter så en stein hver dag, enten til Vishnu eller til Shiva. Prestene måtte ikke legge en stor stein oppå en mindre.. Når hele pyramiden er flyttet over til Shiva, er verdens undergang der. Hvis dette er den sanne historia, så er vi kanskje allerede kommet halvveis til verdens ende, som kommer etter (2⁴² - 1) døgn, dvs etter ca 4 billioner år (europeiske billioner).

Sjakkbrettet
Problemet med hanoitårnet minner om den indiske historien med de 64 rutene på sjakkbrettet.. Det var en kar som utførte en stordåd og som derfor ble lovet ett riskorn for den første ruta, 2 korn for rute 2, 4 for den neste, 8 for den neste osv. På den 64. ruta blir det 2⁶³ riskorn, man alt i alt
2⁶⁴ - 1,
altså på det aller nærmeste dobbelt så mange. Det er flere riskorn enn noen fyrste noen gang har kunnet samle
.

Cardans ringer
Her er det 7 ringer på hver sin pinne, trædd inni

hverandre på underfundig måte, gjennom en bøyle og ned i et bunnstykke. Det gjelder å skille ringsystemet fra bøylen og å sette det sammen igjen. Hver av disse oppgavene tar 85 trekk, til sammen 170, mens antall trekk med 7 brikker for Hanoitårnet er 127. Det er kanskje litt vanskeligere å sette opp de rette matematiske uttrykkene for Cardanspillet enn for hanoitårnet.

Vi har hatt to cardanspill fra 1940-åra, ett ble kjøpt i en hobbybutikk, ett er hjemmelaga. Vi har ellers ikke sette dem i butikker i seinere år.

Neste forsøk Tilbake til innholdsfortegnelser

G02 Del G 3. avdeling Indeks

Løsning av Hanoitårnet

Her skal vi greie oss med 5 brikker på de 3 pinnene.

R står for rød pinne, S for svart og H for hvit.

Brikkene er nummerert fra 1 til 5. 1 er minst, 5 størst.

Vi starter med alle brikkene på H; den største brikken nederst og så er de mindre oppover. Brikkene skal flyttes en om gangen til R i overensstemmelse med regelen om at en brikke aldri må ligge på en som er mindre.

På et tidspunkt i spillets gang må man legge 5 nederst på R. Før man kan få til det, må de 4 minste ligge på S.
Det betyr at 4 ligger nederst på S, men før vi kunne få den dit, måtte alle de minste 3 ligge på R.
Før 3 kunne komme på R, må de 2 minste ligge på S,
men før 2 kan legges på S, må 1 flyttes til R.

Vi starter altså med 1 til R og gjør følgende trekk:

1 Brikke 1 H ® R (Fra hvit til rød)

2 2 H ® S
3 1 R ® S Antall trekk 3

4 Brikke 3 H ® R

5-7 De 2 brikkene på S må over
på R, det tar som vi har sett,
3 trekk 4 Totalt 7 trekk

8 Brikke 4 H ® S

9-15 De 3 brikkene på R må over
på S, det tar 7 trekk 8 15

16 Brikke 5 H ® R

17-31 De 4 brikkene på S må over
på R, det tar 15 trekk 16 I alt 31 trekk

Det minste antall trekk for å flytte 5 brikker fra en pinne til en annen er:

31 = 2⁵ - 1.

Den generelle formelen for n brikker er: 2ⁿ - 1.

Hvis n = 64, får vi antall trekk: 2⁶⁴ - 1 = 1,8· 10¹⁹

Løsning av Cardans ringspill

Vi starter med alle ringene på bøylen.

Ring nr 1 kan du alltid få av eller på. Alle de andre blir hindret av at pinnen ringen sitter på går gjennom ringen bakenfor.

Når du har tatt av ring 1, kan du ikke ta av ring 2.
For å få av ring 2, må ring 1 være på. Når den er det, kan du sørge for å få ring to forover og opp over bøylen. Deretter senker du ringen ned gjennom bøylen.

For alle ringene, unntatt 1, gjelder det at man kan bare ta dem av hvis ringen foran er på. For å få av ring 7 f eks må ringene 1-5 være av, men ring 6 må være på. Hvis du har ringspillet foran deg, kan du sikkert overbevise deg selv om at dette er riktig.

Nå kan vi legge en plan for å få av alle 7 ringene:

For å få av nr 7, må nr 6 være på samtidig som 1-5 er av. Altså må nr 5 av.

For å få av nr 5, må 4 være på, mens 1-3 må være av. Altså må nr 3 være av.

For å få av 3, må nr 2 være på.

Start:
Ta av 1, ta så av 3.
Men så må vi ha av 1 og 2 også, og det betyr nr 1 på igjen, nr 2 av og så nr 1 av. Da sitter vi igjen med 4 - 7 på.
Nå tar vi av 5, og så fortsetter vi baklengs til vi ha fått av alle ringene.

Hvis systemet består av bare 1 ring, går det med 1 trekk får å få den løs.

Hvis systemet har 2 ringer, kan vi ikke få 2 av hvis 1 allerede er av.

Vi må starte med å ta av ring 2, så ring 1, i alt 2 trekk.

Hvis systemet har 3 ringer, kan vi bare få av ring 3 hvis ring 2 også er på, men bare ring 2. Vi starter altså med ring 1, så ring 3. Så på med ring 1, av med 2 og så av med 1, i alt 5 trekk.

Sånn fortsetter vi. For å få av ring 7, må vi ha kommet fram til at 6 og 7 er aleine på, altså med nr 5 av. Men før vi kan få av 5, må 4 være på foran 5 uten at 3 er på. For å få av 3 osv

Her er en liste over sammenhengen mellom antall ringer og minste antall trekk:

Antall ringer, n: 1 2 3 4 5 6 7
Antall trekk, T: 1 2 5 10 21 42 85

Hvis n er et odde tall, er: T_n = (2ⁿ⁺¹ - 1)/3

Hvis n er et partall, er: T_n = (2ⁿ⁺¹ - 2)/3

For et partall n er: 2 T_n = T_n+1 - 1

Eller kanskje foretrekker du uttrykket:

2 T_2n = T_2n+1 - 1

Neste forsøk Tilbake til innholdsfortegnelser

G02 Del G 3. avdeling Indeks

Stikkord: 2-tallsystemet Informatikk	Vi har tatt med disse forsøkene selv om det ikke dreier seg om fysikk; men det er ikke langt unna, og vi syns de er artige. Både Hanoitårnet og Cardans ringer er brukt som øvingsoppgaver i dataprogrammering. Det skal være forholdsvis lett å lage programmer som løser problemene.
Utstyr: Sjakkbrett Noe å lage hanoitårn med, f eks 5 ulike mynter. eller stableleker	Hanoitårnet Da verden ble skapt, satte guden tre store diamantstolper i et tempel, som kanskje var i Hanoi. På en av pinnene trædde hun 64 solide gullskiver; den aller største underst og så ble de mindre og mindre oppover. Munkene i templet ble så satt til å flytte skivene over til en av de andre stolpene. De måtte bare flytte en skive om gangen, bare fra en stolpe til en annen, men alltid sånn at en mindre skive lå oppå en som var større. I det øyeblikket munkene ble ferdige med dette arbeidet, ville verden forgå. Når kommer det til å skje? Det er gjort grundige studier av dette problemet, og dere kan finne det behandlet mange steder på WEBnettet. Antall trekk blir N = 2⁶⁴ - 1. Hvis munkene flytter 1 skive/s, er de nok ikke kommet halvveis ennå, selv om vi regner nokså høy alder for vår klode. En antydning av hvordan man flytter brikkene følger seinere i manus. Man kan jo øve seg med bare 3 eller 4 eller kanskje 7 skiver på tre pinner. Man kan også bruke passende stableleker for barn. Hanoitårn med 7 ringer kan man kanskje finne i noen leketøysforretninger. En annen historie går ut på at det var indiske guder som satte i gang dette spillet. Det var skaperen Brahma som lagde en pyramide med 42 mindre og mindre steiner oppå hverandre. Prestene flytter så en stein hver dag, enten til Vishnu eller til Shiva. Prestene måtte ikke legge en stor stein oppå en mindre.. Når hele pyramiden er flyttet over til Shiva, er verdens undergang der. Hvis dette er den sanne historia, så er vi kanskje allerede kommet halvveis til verdens ende, som kommer etter (2⁴² - 1) døgn, dvs etter ca 4 billioner år (europeiske billioner).
	Sjakkbrettet Problemet med hanoitårnet minner om den indiske historien med de 64 rutene på sjakkbrettet.. Det var en kar som utførte en stordåd og som derfor ble lovet ett riskorn for den første ruta, 2 korn for rute 2, 4 for den neste, 8 for den neste osv. På den 64. ruta blir det 2⁶³ riskorn, man alt i alt 2⁶⁴ - 1, altså på det aller nærmeste dobbelt så mange. Det er flere riskorn enn noen fyrste noen gang har kunnet samle .
	Cardans ringer Her er det 7 ringer på hver sin pinne, trædd inni hverandre på underfundig måte, gjennom en bøyle og ned i et bunnstykke. Det gjelder å skille ringsystemet fra bøylen og å sette det sammen igjen. Hver av disse oppgavene tar 85 trekk, til sammen 170, mens antall trekk med 7 brikker for Hanoitårnet er 127. Det er kanskje litt vanskeligere å sette opp de rette matematiske uttrykkene for Cardanspillet enn for hanoitårnet. Vi har hatt to cardanspill fra 1940-åra, ett ble kjøpt i en hobbybutikk, ett er hjemmelaga. Vi har ellers ikke sette dem i butikker i seinere år.

Neste forsøk	Tilbake til innholdsfortegnelser
G02	Del G	3. avdeling	Indeks