Tårnene til Hanoï (opprinnelig Hanoi-tårnet ) er et puslespill som den franske matematikeren Édouard Lucas forestiller seg , og består i å flytte skiver med forskjellige diametre fra et "avgangstårn" til et "ankomsttårn." Passerer gjennom et "mellomliggende tårn" ”Tårn, og dette i et minimum av trekk, med respekt for følgende regler:
Det antas at denne siste regelen også respekteres i startkonfigurasjonen.
Det matematiske problemet med tårnene i Hanoi ble oppfunnet av Édouard Lucas . Den er utgitt i bind 3 av hans Récréations mathiques , publisert postumt i 1892 . Han kunngjør at dette problemet skyldes at en av vennene hans, N. Claus de Siam ( anagram av Lucas d'Amiens, Amiens er hans fødested), angivelig professor ved college i Li-Sou-Stian (anagram av Saint Louis , videregående skole der Lucas underviste).
Under tittelen " Brahmene faller " forteller Lucas at "N. Claus av Siam så på sine reiser for publisering av skrifter av den berømte Fer-Fer-Tam-Tam, i det store tempelet til Benares , au- under kuppelen som markerer verdens sentrum, tre diamantnåler, plantet i en brazen plate, en alen høy og størrelsen på en bies kropp. På en av disse nålene trådet Gud i begynnelsen av århundrene, 64 skiver av rent gull, den største hvilende på messingen, og de andre, mer og mer smale, lagt på toppen. Det er det hellige tårnet til Brahmâ . Natt og dag følger prestene hverandre på trinnene til alteret, opptatt med å transportere tårnet fra den første nålen til den tredje, uten å avvike fra de faste reglene som vi nettopp har angitt, og som ble pålagt av Brahma. Når det hele er over, vil tårnet og brahminene falle, og det vil være verdens ende! " .
Som vist nedenfor krever et spill på 64 plater minst 264 -1 trekk. Forutsatt at det tar 1 sekund å flytte en plate, som er 86.400 trekk per dag, vil spillet avsluttes etter cirka 213 billioner dager, noe som tilsvarer omtrent 584,5 milliarder år, eller 43 ganger den estimerte alderen i universet (13,7 milliarder dollar) år ifølge noen kilder).
Det er lett å vise ved induksjon at hvis n er antall skiver, tar det minst 2 n - 1 trekk for å oppnå endene, en mengde som øker veldig raskt med n . La A, B og C faktisk være tårnens tre steder; Vi angir med x n antall forskyvninger av skiver som er nødvendige for forskyvning av et komplett tårn. For å flytte et tårn med n skiver fra A til C, utfører vi disse tre trinnene:
Antall forskyvninger av disker verifiserer dermed forholdet mellom gjentakelse:
som gir bra
Vi kan vise at metoden beskrevet her gir den optimale sekvensen (den som krever færrest trekk), og at denne er unik. For å flytte tårnet på n skiver fra A til C, må vi nødvendigvis, på en eller annen gang, flytte den største disken fra A til C, og for å gjøre dette må vi ha stablet n -1 første poster i B .
Problemet med tårnene i Hanoi ses i algoritmisk ( programmering ), hvor det gir et eksempel på kraften og lesbarheten til programmer definert rekursivt (et annet eksempel er tresortering ). Faktisk fører oppløsningsmetoden til tidligere til en rekursiv algoritme , beskrevet nedenfor. Parametrene til Hanoi- prosedyren er:
Vi kan generalisere den rekursive oppløsningen i tilfelle der diskene i utgangspunktet er ordnet tilfeldig på de tre stedene, i stedet for stablet på den første (utgangsposisjonen er vilkårlig). Målet vil være å gruppere n diskene på destinasjonsstedet A. Vi nummererer n diskene fra 1 til n i rekkefølge av økende størrelse, og vi betegner med P k posisjonen til disken nummerert k . Vi starter fra følgende observasjon: det vil nødvendigvis være nødvendig på et eller annet tidspunkt å flytte den største disken fra P n til A. Den rekursive resonnementet ligner da på den forrige:
I motsetning til det spesielle tilfellet som er diskutert ovenfor, avhenger startplasseringen av skivene. Vi må også skille mellom tilfeller der disken n allerede er på rett sted (P n = A). I dette tilfellet ville det ikke være optimalt å følge den forrige metoden: det andre trinnet er unødvendig, og vi kan slå sammen det første og tredje trinnet ved å gruppere de første n -1-diskene direkte i A.
Den generaliserte algoritmen blir derfor:
procédure Hanoï-généralisé(n, A) si n ≠ 0 si Pn = A Hanoï-généralisé(n-1, A) sinon Hanoï-généralisé(n-1, I) Déplacer le disque de Pn vers A Hanoï-généralisé(n-1, A) fin-si fin-si fin-procédureMerk at den siste rekursive samtalen kan erstattes av en samtale til Hanoi- prosedyren i det spesielle tilfellet sett tidligere, siden alle n -1 første diskene blir stablet i I.
Med samme resonnement som ovenfor viser vi at denne algoritmen gir den unike optimale sekvensen. Vi kan uttrykke antall treff som en funksjon av antall n disker, deres arrangement og plasseringen A for ankomst: vi betegner det y n (A).
Vi har derfor følgende gjentakelsesforhold:
Vi kan da uttrykke y n (A) som en sum av krefter på 2, hvor et begrep blir lagt til hvis og bare hvis den tilsvarende disken er feilplassert:
hvor b k er 0 hvis disken k er godt plassert, 1 ellers.
I verste fall er alle diskene feilplassert. Det har vi da . Det er interessant å merke seg at den vanlige utgangssituasjonen er en av de verste tilfellene.
Det er også en iterativ prosedyre for å løse problemet med tårnene i Hanoi på en optimal måte. Den består i å gjennomføre følgende to bevegelser suksessivt, ved å betegne A, B, C de tre svingene (fra venstre til høyre):
og å fortsette disse to forskyvningene iterativt til hele tårnet er forskjøvet, idet den siste forskyvningen da er begrenset til den for den minste skiven på toppen av tårnet. Handlingen "flytt en annen disk" er entydig siden, bortsett fra den minste disken, bare en diskbevegelse er mulig.
I motsetning til den rekursive prosedyren, bruker den iterative prosedyren ingen memorisering av forskyvetreet som skal utføres, og krever bare å huske om vi må flytte den minste disken eller ikke, og i hvilken retning forskyvningene til den lille disken utføres ... Det gjør det også mulig når som helst å gå tilbake til utgangssituasjonen: det er tilstrekkelig å snu retningen den minste platen beveger seg i. Årsakene til at denne algoritmen løser problemet er imidlertid mindre tydelige enn for den rekursive algoritmen.
Vi kan forklare det ved å merke oss at i den optimale løsningen, beveger vi nødvendigvis den minste disken nøyaktig en gang i to, fordi å flytte den to ganger på rad ikke ville være optimal, og å flytte den andre disken to ganger på rad heller. Hvordan vi flytter denne mindre disken, gjenstår å avgjøre.
Anta at tårnet på n skiver først er på plassering A, og at vi ønsker å flytte det til sted C. Vi viser ved induksjon på n at iterasjonen av de to bevegelsene som er beskrevet tidligere gir den optimale sekvensen, hvis retningen der mindre disk flyttes er A → B → C → A (fra venstre til høyre) for jevn n , eller A → C → B → A (fra høyre mot venstre) for odde n . Faktisk :
Anta tårn nummerert 1, 2 og 3.
En forskyvning fra tårn n ° i til tårn n ° j er notert i + j.
Således betegner forskyvning 3 både forskyvning av tårn 1 mot tårn 2 og av tårn 2 mot tårn 1, men det er ingen mulig tvetydighet: den mindre skiven blir plassert på den større.
På samme måte betegner forskyvning 4 både forskyvning av tårn 1 mot tårn 3 og av tårn 3 mot tårn 1.
Og til slutt betegner forskyvning 5 både forskyvning av tårn 2 mot tårn 3 og av tårn 3 mot tårn 2.
Når antall disker er jevne, er bevegelsene som skal utføres 3,4,5,3,4,5,3,4,5 ... så mange ganger som nødvendig (sekvensen 3,4,5 gjentas ganger).
Når antall disker er merkelig, er forskyvningene som skal utføres 4,3,5,4,3,5, ... så mange ganger som nødvendig (4,3,5-sekvensen gjentas ganger og slutter med forskyvning fra tårn 1 til tårn 3).
Anta skivene farget svart i hvitt, vekselvis. For enkelhets skyld vil det også antas at basene til de tre stengene er farget svart eller hvitt. Basen som støtter det opprinnelige tårnet er farget i en annen farge enn den på den største platen, for å respektere fargevalg. De to andre basene er den ene svarte, den andre hvite. Diskene flyttes iterativt i henhold til følgende to regler:
Vi kan representere spillet Towers of Hanoi med en abstrakt graf , hvor hver toppunkt på grafen representerer et mulig arrangement av N-skivene på de tre svingene, en kant som forbinder to hjørner hvis det er en bevegelse av en disk som lar passere fra en ordning, representert av en av toppunktene, til den andre. Merkingen av hjørner er basert på platenes plassering i arrangementet den representerer: vi leser fra venstre mot høyre hvilket tårn hver plate tilhører, og starter med posisjonen til den største platen.
Diagrammet viser spilletreet med tre plater. Utgangsposisjonen er plassert ved ett toppunkt i trekanten, for eksempel AAA, og den endelige posisjonen er et annet toppunkt, BBB eller CCC. Kantens farge indikerer at platen skal bevege seg: rød for den minste platen, gul for mellomplaten og blå for den store platen.
Vi viser at grafen til Tårnene i Hanoi med N-skiver for alle N er identisk med den som er oppnådd fra et Pascal-trekant av rekkefølge 2 N , hvor vi forbinder de odde binomiale koeffisientene med en kant.
Tower of Hanoi-oppgaven brukes i psykologiforskning , spesielt gjennom problemløsning . Det brukes også som en nevropsykologisk test .
Denne oppgaven er sensitiv for frontale og prefrontale dysfunksjoner .
Denne testen tillater således evaluering av lederfunksjoner , som planlegging , arbeidsminne og inhibering .
Ytelsen ved Tower of Hanoi avhenger av funksjonene til hemming , arbeidsminnet , prosessminnet og intelligensvæsken .
Imidlertid inhibering krever undertrykkelse av aktiviteten av den primære motor cortex , av den høyre nedre frontal cortex og av motorområdet i tillegg. Den arbeidsminne betyr dorso-laterale delen til frontal cortex som gjør at den aktive manipulering og styreinformasjon. På samme måte korrelerer planlegging med aktivering av den dorsale delen av prefrontal cortex , parietal og premotor cortex og lillehjernen.
Vi forstår hvorfor Hanoi-tårnet er følsomt for frontale og prefrontale dysfunksjoner.
Denne testen er nær den fra Tower of London-testen så vel som den for Towers of Toronto.