Tårnene i Benares

2013-01-15 09.16.23

Sommetider er jeg uhyggeligt lang tid om at opdage noget indlysende. Det var faktisk først i den uge, der nu snart er forbi, at jeg opdagede det: den store mosaik, der pryder en af facaderne på Selma Lagerlöfs Vej 300, hvor Institut for datalogi holder til, må være en illustration af tårnene i Hanoi, der retteligt bør kaldes for tårnene i Benares. Mange, der har fulgt kurser i diskret matematik eller algoritmeteori, har set dette lille puslespil. Vores bygning (der er designet af Friis og Moltke og faktisk minder mig lidt om en anden af deres bygninger, nemlig Fjerritslev Gymnasium, hvorfra jeg blev student) er nu ikke vores oprindelig. Den blev oprindelig brugt af KMD, så allerede dengang må man have tænkt over tårn-puslespillets forbindelse til programmering.

Selv læste jeg for første gang om tårnene i Alle tiders tal, en populærvidenskabelig bog om matematik fra Politikens forlag. Det var en bog, jeg pløjede igennem igen og igen, da jeg gik i folkeskolen. Allerede dengang vidste jeg at tårnene i Benares (som bogen kaldte spillet) var en historie, som skyldes den franske matematiker Edouard Lucas. I 1883 lancerede han under pseudonymet N. Claus de Siam fortællingen om et tempel i Benares i Indien, hvor der står tre små diamantnåle. På nål nr. 1 var oprindelig lagt 64 skiver af guld, den ene mindre i diameter end den anden. Et hold præster er travlt beskæftiget med at flytte skiverne over på nål nr. 3 én ad gangen, idet de kun må flytte en skive over på en skive med større diameter. Når nålene er flyttet over på nål nr. 3, går verden under. (Alt dette lyder lidt som en beskæftigelsesministers ønskedrøm, ikke?)

Hvorfor er tårnene i Benares endt med at blive kaldt for tårnene i Hanoi? Måske fordi N. Claus de Siam skulle forestille at være på universitetet i Hanoi; Vietnam var dengang kolonien Fransk Indokina. Forvirringen er formodentlig sket i oversættelsen fra les tours de Hanoï, der nemlig både kan betyde “tårnene fra Hanoi” og “tårnene i Hanoi”.

Ligesom de regulære udtryk er tårnene i virkeligheden en forbilledlig illustration af en lang række beslægtede begreber – her inden for datalogi og diskret matematik. Algoritmen, der løser flytteproblemet, kan beskrives rekursivt – og den rekursive algoritme giver anledning til rekurrensligninger, der bestemmer algoritmens tidskompleksitet (målt i antal flytninger). Et bud på løsningen til ligningerne kan bevises at være korrekt ved brug af matematisk induktion – og man opdager at tidskompleksiteten er eksponentiel i antallet af skiver. Så langt når de fleste.

Men der er mere, meget mere at sige om tårnene. Man opdager, at tårnspillet er selv-similært i den forstand at spillet med n skiver rummer to kopier af spillet med n-1 skiver og at spil-grafen for tårn-spillet derfor er en approksimant til Sierpinskis trekant. Den optimale løsning (dvs. den strategi, der anvender færrest flytninger) svarer til en Hamilton-sti i spil-grafen. Og man kan repræsentere løsningen til spillet ved brug af de såkaldte Gray-koder (dem har Donald Knuth skrevet en grundig introduktion til). MathWorld og Wikipedia er gode steder at læse mere til en start.

Men én gåde er stadig uopklaret, i al fald for mig: Forestiller mosaikken virkelig tårnene i Benares, eller er det mig der opdager et “ansigt i tapetet”?

(Visited 125 times, 1 visits today)
Loading Facebook Comments ...

Skriv et svar